/
发布时间降序
2021-5-15学习笔记
图形学学习笔记: 前一阵看games101课程学习了一下图形学的基础知识,最近又开始学习WebGL,但学习WebGL时发现自己已经忘了之前games101听的内容,于是赶快来复习并记录一下笔记,防止再次忘记。该笔记采用知识点罗列记录的形式,并不引导学习。持续但不定期更新 声明:该笔记中所有坐标系均采用Games101课程中推荐的右手坐标系 * 齐次坐标: 齐次坐标(Homogeneous Coordinates),是图形学中用来描述点(Point)、向量(Vector,又称矢量,图形学中一般叫向量)及矩阵(Matrix)的记录方式。其存在的意义是,将像类似于平移(Translation)这种非线性变换转化为线性变化(Linear transform)。 其表现形式为增加一维坐标(w-coordinates),例如: - (请文中查看代码) - $2D\\_Vector = (x, y, 0)^T$ w-coordinates中坐标取值为1,向量取值为0的原因如下(符合数理逻辑): - vector + vector = vector - point - point = vector - point + vector = point 其中w-coordinates坐标不一定为1,可以为任何非零数。当取值为$w$时,例$(x, y, w)^T$可以理解为其代表的意义是$(\\frac{x}{w}, \\frac{y}{w}, 1)^T$,即坐标为$(\\frac{x}{w}, \\frac{y}{w})$的点。 在下文中将全部使用齐次坐标来描述向量、点、矩阵。 仿射变换: 仿射变换(Affine Transformation),是由齐次坐标中引申的含义,其代表一个线性变化加一个平移变换。例如下式中的缩放变换加一个平移变换: $$ \\left( \\begin{matrix} x^{\\prime}\\\\ y^{\\prime}\\\\ \\end{matrix} \\right) = \\left( \\begin{matrix} a& b\\\\ c& d\\\\ \\end{matrix} \\right) \\cdot \\left( \\begin{matrix} x\\\\ y\\\\ \\end{matrix} \\right) + \\left( \\begin{matrix} t_{x}\\\\ t_{y}\\\\ \\end{matrix} \\right) $$ 使用齐次坐标写上式为: $$ \\left( \\begin{matrix} x^{\\prime}\\\\ y^{\\prime}\\\\ 1\\\\ \\end{matrix} \\right) = \\left( \\begin{matrix} a& b& t_x\\\\ c& d& t_y\\\\ 0& 0& 1\\\\ \\end{matrix} \\right) \\cdot \\left( \\begin{matrix} x\\\\ y\\\\ 1\\\\ \\end{matrix} \\right) $$ 变换矩阵: 缩放矩阵: 缩放矩阵(Scale Matrix)描述一个缩放变换,使得原物体放大或缩小。 $$ \\mathbf{S}(s\x, s\y)= \\left( \\begin{matrix} s\_x& 0& 0\\\\ 0& s\_y& 0\\\\ 0& 0& 1\\\\ \\end{matrix} \\right) $$ 旋转矩阵: 旋转矩阵(Rotation Matirx)描述一个旋转变换,使得原物体绕某点或某轴旋转。 绕X轴旋转: $$ \\mathbf{R}_{x-axis}(\\alpha)= \\left( \\begin{matrix} 1& 0& 0& 0\\\\ 0& \\cos\\alpha& -\\sin\\alpha& 0\\\\ 0& \\sin\\alpha& \\cos\\alpha& 0\\\\ 0& 0& 0& 1\\\\ \\end{matrix} \\right) $$ 绕Y轴旋转: $$ \\mathbf{R}_{x-axis}(\\alpha)= \\left( \\begin{matrix} \\cos\\alpha& 0& \\sin\\alpha& 0\\\\ 0& 1& 0& 0\\\\ -\\sin\\alpha& 0& \\cos\\alpha& 0\\\\ 0& 0& 0& 1\\\\ \\end{matrix} \\right) $$ 绕Z轴旋转: $$ \\mathbf{R}_{z-axis}(\\alpha)= \\left( \\begin{matrix} \\cos\\alpha& -\\sin\\alpha& 0& 0\\\\ \\sin\\alpha& \\cos\\alpha& 0& 0\\\\ 0& 0& 1& 0\\\\ 0& 0& 0& 1\\\\ \\end{matrix} \\right) $$ 绕任意轴旋转: 该知识点为罗德里格斯旋转公式(Rodrigues' Rotation Formula),描述绕任意轴$axis\\_n$的旋转。 $$ \\mathbf{R}(\\mathbf{n},\\alpha)=\\cos(\\alpha)\\mathbf{I}+(1-\\cos(\\alpha))\\mathbf{n}\\mathbf{n}^T+\\sin(\\alpha) \\underbrace{ \\left( \\begin{matrix} 0& -n\z& n\y\\\\ n\z& 0& -n\x\\\\ -n\y& n\x& 0\\\\ \\end{matrix} \\right) }_\\mathbf{N} $$ 平移矩阵: 平移矩阵(Translation Matrix)描述一个平移操作,使得原物体向某一方向进行平移。 $$ \\mathbf{T}(t\x, t\y)= \\left( \\begin{matrix} 1& 0& t\_x\\\\ 0& 1& t\_y\\\\ 0& 0& 1\\\\ \\end{matrix} \\right) $$ MVP变换: MVP变换是图形学中常用的一种3D视图变换,其中MVP三者分别指的是Model, View, Projection,即“放置物体”,“放置相机/视图变换”,“投影变换”。其中Model变换没有什么要特别做的,即确定物体坐标或者说地点,接下来将着重介绍View和Projection两个部分。 $$ Point^{\\prime} = \\mathbf{M}\P\\cdot\\mathbf{M}\V\\cdot Point $$ 视图变换 View Transform: 视图变换主要要先确定相机(Camera)位置,然后使用一向量将相机移动至原点,同时将物体使用同样的向量进行移动(其实只有这一步需要实际操作)。在此之前,如果需要进行其他线性变换,例如旋转,要先进行其他线性变换。 投影变换 Projection Transform: 投影变换的操作将3D物体转化为2D图像。一般有两种投影变换,正交投影(Orthograohic projection)与透视投影(Perspective projection),其中正交投影运用在数学与工科较多,例如三视图、工图、几何制图等。 正交投影: 正交投影操作要将物体中心平移至原点,然后将其进行缩放,使得其在正交立方体(Canonical Cube)$-1, 1]^3$中,然后将z轴扔掉。公式如下: $$ M_{ortho}= \\left[ \\begin{matrix} \\frac{2}{r-l}& 0& 0& 0\\\\ 0& \\frac{2}{t-b}& 0& 0\\\\ 0& 0& \\frac{2}{n-f}& 0\\\\ 0& 0& 0& 1\\\\ \\end{matrix} \\right] \\left[ \\begin{matrix} 1& 0& 0& -\\frac{r+l}{2}\\\\ 0& 1& 0& -\\frac{t+b}{2}\\\\ 0& 0& 1& -\\frac{n+f}{2}\\\\ 0& 0& 0& 1\\\\ \\end{matrix} \\right] $$ 透视投影: 要做透视投影,就先要将空间中的视锥(Frustum)转换为长方体(Cuboid),之后再做一遍正交投影,即可得到2D图像。即$M\{presp}=M\{ortho}M\_{pres\\rightarrow ortho}$。 其中,将视锥Frustum转换为长方体Cuboid的公式如下(具体的推倒过程请看[Games101课程第四讲): $$ M_{presp\\rightarrow ortho} = \\left( \\begin{matrix} n& 0& 0& 0\\\\ 0& n& 0& 0\\\\ 0& 0& n+f& -nf\\\\ 0& 0& 1& 0\\\\ \\end{matrix} \\right) $$ 光栅化: 后面的坑以后再填(
2020-4-5杂记
Stories of Songs: 听过很多歌,也明白很多歌藏有他自己的故事。这篇文章里,我会把我理解的这些声音背后的故事写成小说,以记录此时所想。 歌曲背后的故事是怎样的或许只有创作者知道,这篇文章不是为了挖取真实的故事而写,而是为了记录自己对歌曲的理解而写。 不定时更新 Last dance lullaby: From Survive Said The Prophet 序: 每当想起这段往事我都语无伦次,曾经的我,究竟是陷入到了一段怎样的恋情中啊。 一: 十六岁那年,我盼望着夏天的蝉鸣快点到来,蝉鸣意味着赤日炎炎的假期,而假期意味着汗流浃背的摇滚show。 谁能想到,我在那场演出遇到了你。 还记得我们之间开始于一个问候,交换了电话号码, 随后一直在手机上保持联系,直到我们再次见面。 原本只是想交个朋友,但随着短信的积攒,我对你的情愫也慢慢积攒。 我最终还是改变了我的想法:我想成为能与你同床共枕、白头到老的那个人。 <br /> 你说,终有一天你会飞去加州生活。 我说,终有一天我会走遍世界巡演。 <br /> 你说:“不然,你随我环游世界,去到海角天涯吧!” 于是,我组建了自己的乐队,踏上了漫漫巡演路。 二: “时间正好,今天终于可以送她回家了”,刚排练完的我独自揣摩着时间。 再有四个月,你就要毕业了。你早就像是大学生一样,学会了逃课。 像这样的生活不会再有了吧。 高中生活的确枯燥,但是我必须承认,那段叛逆的时光,是人生中最后的美好岁月。 三: 今天是你的生日。我订了最后的航班回家,为了给你庆生。 生日会上我隆重的宣布,我得到了一份真正的工作。 这是为了搏取你的好感,用夜以继日的奔波换来的的成果。 但是我早就应该知道,这不是你想要的生活。 四: 十年的时间光阴似箭,从大阪到东京,我们的乐队专场卖空了所有的票。 每场演出都会去到不一样的城市,每个城市我都会与你分享独特的美景。 <br /> 后来我听说,你还是一如既往的标新立异。 不过你再也没有到处旅行,再也没有与那些混蛋约会。 我明白,你早就释怀,不再去想日思夜梦的环球旅行了。 <br /> 你终于又给我信息了,你说: 你终于找到值得托付终生的人,为了答谢上天恩赐,你开始去教堂祷告。 你找到了一份收益可观的工作,找到了一个遮风避雨的住处,过上了像普通人一样按时交税的生活。 你说,这就是你在加利福尼亚的生活。 当时我还在世界巡演的路上,我送给你了祝福,说着一定要去给你庆祝庆祝。 五: 尽管我再也没见过她,但我还是写了这首朗朗上口的歌。 “再见了,晚安了”。像这种,在那时的短信里习以为常的话语,只能在歌里唱给你听了。 我还期盼着最后的机会,为我保留你最后一支舞吧。 <br /> Sparkling Sky Lazer: From Fear, and Loathing in Las Vegas 留个坑,之后写
2020-4-5开发
记录一次React+TypeScript的开发历程: 之前一直使用Vue框架,这次打算学习一下React顺便学习一下TypeScript,于是就有了这个项目。在开发过程中遇到了一些问题,感觉这些坑或者说刚开始学不知道的要注意的点,是有必要记录下来的。 建立一个React + TypeScript + Sass + Webpack的项目: 初始化项目: 首先我们用$ yarn init初始化一个项目,这样我们就在项目根目录得到一个package.json文件,这个文件是项目配置文件,我们需要对他进行一些改动, 向其json中加入如下代码: (请文中查看代码) 上面的配置作用是:指定项目运行命令 下载依赖: 其次,我们把需要的包都下载下来: (请文中查看代码) 这些包都是干什么的呢? - 第一行:下载React相关 - 第二行:下载Babel相关 - 第三行:下载TypeScript - 第四行:下载TypeScript相关。 为什么要下载@types/xxx包? 你可能会遇到Could not find a declaration file for module 'xxx'的问题,这个问题是因为TypeScript还不认识相关包,要想让typescript认识他们,就要下载相应的@types/xxx包。 - 第五行:下载SaSS - 第六行:下载Webpack - 第七行:下载Webpack所需要的loader。 为什么要下载loader? 因为Webpack是由Node.js编写的项目打包工具,这就意味着它只能认识JavaScript文件,要想让他认识其他类型的文件,就要使用到这些loader包去加载、编译、解析。 项目的相关配置: 配置Webpack: 在项目根目录中新建一个webpack.config.js文件,内容如下: (请文中查看代码)Webpack相关知识 Webpack从项目入口开始检索依赖,将所有依赖性经过loader、编译之后,打包输出至出口文件 配置Babel: 在项目根目录中新建一个.babelrc文件,内容如下: (请文中查看代码)为什么要用Babel? Babel可以帮我们把typescript文件编译成javascript文件,并且能够实现对某些浏览器的兼容编译,即编译成置顶环境支持的语法,可以理解为一个polyfill机。 配置TypeScript: 在项目根目录中新建一个tsconfig.json文件,内容如下: (请文中查看代码) 开始开发: 在配置完项目之后,我们的项目结构应该是这样的 (请文中查看代码)也是相同的作用,不过只是它是npm的依赖文件。 首先我们需要一个public/index.html的入口文件,其内容如下: (请文中查看代码) 其次是src/index.tsx文件,即webpack中配置的项目入口文件,内容如下: (请文中查看代码) 而开发过程中的scss代码均保存为.scss文件,webpack就可以自动将其编译输出为css文件。 项目运行: 还记得之前在package.json中配置的运行命令,现在我们在项目根目录下运行: (请文中查看代码) 就可以让webpack监听项目目录,这样当文件发生变动时,webpack就可以自动将文件编译、打包、输出到./dist文件夹下。 这时我们打开public/index.html即可成功运行看到Hello World!字样,项目就运行成功了。 在项目中使用其他库: React-router: 下载依赖: (请文中查看代码) index.tsx代码: (请文中查看代码) 项目开发中遇到的坑: ReferenceError: regeneratorRuntime is not defined: 这是当你使用了async/await之后Babel产生的错误,解决这个错误只需要安装一个包,并且增加一些.babelrc配置就可以了。 (请文中查看代码) 在.babelrc文件中添加如下配置: (请文中查看代码) Module parse failed: Unexpected character '@': 没有添加css-loader/url-loader。 下载loader: (请文中查看代码) 在webpack.config.js中添加配置: (请文中查看代码) 另外,如果你在使用Next.js,注意要下载@zeit/next-css (请文中查看代码) 并在next.config.js中添加配置: (请文中查看代码) 如果有多个withXxx记得嵌套而不是并列: (请文中查看代码) React Input 输入中文的问题: 问题描述: 在Uncontrolled Component下的onInput/onChange事件无法键入中文 参考文章: [Controlled and uncontrolled component design pattern in React 解决方案: 1. 使用CompositionEvent。在onCompositionStart/onCompositionUpdate的时候开启锁,onCompositionEnd的时候关闭锁,并在onChange的handler中判断:只有在锁关闭的时候更改Value。参考文章: 中文输入法与React文本输入框的问题与解决方案 > Chrome 53以后的版本中,onChange事件被调整到了onCompositionEnd之后执行,那么就需要在onCompositionEnd中对Chrome浏览器进行特判,并执行onChangeHandler中的逻辑. 2. 将Uncontrolled Component替换为Controlled Component。这个方法最简单粗暴,也是最有效的。
2020-2-16学习笔记
个性化推荐算法LFM理论知识: LFM是监督学习的个性化推荐算法,其他的个性化推荐算法还有itemCF等。 建模公式: `(请文中查看代码)` 其中: - u 指 user , i 为 item - p(u,i) 代表user是否点击了item, 点击了值为1,否则值为0 - `(请文中查看代码)` 相乘为一值 - F是向量维度 损失函数: `$$ loss = \sum _{(u,i) \in D} \big(p(u,i)-p^{LFM}(u,i)\big)^2 $$` 其中: - D是所有训练样本集合 - `$p^{LFM}(u,i)$`是LFM算法预估值 该公式过拟合,导致模型特征值复杂,模型泛化能力减弱 为解决过拟合,需使用到正则化: ` $$ \begin{equation} \widetilde{J}(w;X,y) = J(w;X,y) + \alpha\Omega(w) \\[20px] \left\{ \begin{aligned} \Omega(w) &= \|w\| 1 = \sum i|w _i| & (l1正则化)\\[8px] \Omega(w) &= \|w\| 2 = \sum iw _i^2 & (l2正则化) \end{aligned} \right . \end{equation} $$ ` 算法迭代: 此处采用l2正则化,得到正则化后公式: `$$ loss = \sum {(u,i) \in D}\big(p(u,i) - \sum {f=1}^Fp {uf}q {if}\big)^2 + \partial|p u|^2 + \partial|q i|^2 $$` 其中: `$$ \frac{\partial loss}{\partial p {uf}} = -2\big(p(u,i) - p^{LFM}(u,i)\big)q {if} + 2\partial p _{uf} $$` `$$ \frac{\partial loss}{\partial q {if}} = -2\big(p(u,i) - p^{LFM}(u,i)\big)p {uf} + 2\partial q _{if} $$` 采用梯度下降的方法迭代,有迭代公式: ` $$ \begin{equation} \left\{ \begin{aligned} p {uf} &= p {uf} - \beta\frac{\partial loss}{\partial p _{uf}} \\ q {if} &= q {if} - \beta\frac{\partial loss}{\partial q _{if}} \end{aligned} \right . \end{equation} $$ ` 影响算法的因素: 1. 负样本取样。例如选取了100个正样本,就要选取100个负样本来平衡。 2. 隐特征 F,正则参数 α,leanring rate β。其中F选择在10~32之间,α和β一般选取在0.01~0.05之间 算法比较: 复杂度 | LFM | CF :-----:|:-----:|:-------: 时间 | O(dnF)| O(mk^2) 空间 | O(n) | O(n^2) |离线计算|响应及时 其中: d是迭代次数,n是样本大小,F是向量维度,m是用户点击次数
2019-5-4学习笔记
汇编学习笔记: 系统环境:macOS High Sierra 10.13.4 CPU:Intel 使用工具:NASM version 2.14.02 compiled on Dec 27 2018 环境配置: (请文中查看代码) 概念理解: 寻址方式: 寻址方式 | 指令中包含 | 说明 | 最终访问地址 :----------:|:------------------:|:---------:|:---------: 立即寻址方式 | 要访问的数据 | | 直接访问数据 寄存器寻址方式| 要访问的寄存器 | | 访问寄存器 直接寻址方式 | 内存地址 | | 内存地址 变址寻址方式 |内存地址、变址寄存器、比例因子| | (请文中查看代码) 间接寻址方式 | 寄存器 |寄存器中存放要访问的内存地址|寄存器中的内存地址 基址寻址方式 | 寄存器、偏移量 |寄存器中存放要访问的内存地址| (请文中查看代码) x86_64寄存器: 按寄存器排序: 寄存器| 用途 |跨函数调用保留 :---:|:---------------:|:----------: rax | 1st return register, number of vector registers used | x rbx | 被调用方保留的寄存器,基指针 | √ rcx | 用于向函数传递第四个参数 | x rdx | 用于向函数传递第三个参数,2nd return register | x rsp | 栈指针 | √ rbp | 被调用方保留的寄存器,帧指针 | √ rsi | 用于向函数传递第二个参数 | x rdi | 用于向函数传递第一个参数 | x r8 | 用于向函数传递第五个参数 | x r9 | 用于向函数传递第六个参数 | x r10 | 临时寄存器,用于传递函数的静态链指针 | x r11 | 临时寄存器 | x r12 | 被调用方保留的寄存器 | √ r13 | 被调用方保留的寄存器 | √ r14 | 被调用方保留的寄存器 | √ r15 | 被调用方保留的寄存器 | √ 按用途分类排序: - 作为函数返回值使用:rax - 栈指针寄存器,指向栈顶:rsp - 用作函数参数,依次对应第i参数:rdi, rsi, rdx, rcx, r8, r9 - 用作数据存储,遵循被调用者使用规则(随便用,调用子函数之前要备份以防被修改):rbx, rbp, r12, r13, r14, r15 - 用作数据存储,遵循调用者使用规则(使用之前要先保存原值):r10, r11 第一个程序HelloWorld: 执行过程: 源代码(main.asm): (请文中查看代码) 编译: (请文中查看代码) 链接: (请文中查看代码) 执行: (请文中查看代码) 程序解读:: 选举一段代码作为解释: (请文中查看代码) 在本段代码中,0x2000004代表的是系统调用(syscall) - write。 执行过程如下: 1. 给rax一个值0x2000004,代表本次指令调用要调用的是write指令 2. 给rdi一个值(1),代表从stdout输出,是系统指令调用的第一个参数 3. 给rsi一个值(字符串),代表要输出的字符内容,是系统指令调用的第二个参数 4. 给rdx一个值(字符串长度),是系统指令调用的第三个参数 5. syscall,将上述步骤转化为一个完整的指令并执行 6. ret,执行结束 以此类推 (请文中查看代码) 这段代码的含义为: 1. 给rax一个值0x2000001,表示退出syscall 2. 给rdi一个值0,表示退出指令的返回值为0,是系统指令调用的第一个参数 3. syscall,将上述步骤转化为一个完整的指令并执行 4. ret 执行结束 于是main.asm这一段程序就可以转化为如下伪代码: (请文中查看代码)未完待续
2018-5-22算法竞赛
算法竞赛中的博弈论: 这一篇文章将会系统的整理汇总算法竞赛中的博弈论知识,而博弈论的基础知识在这片文章中则不会提到 巴什博弈(Bash): 只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个。最后取光者得胜。 答案:如果n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品即可保证先手获胜 威佐夫博弈(Wythoff): 有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。 答案:两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜;反之,则后拿者取胜。 对于任意一个局势(a,b),奇异局势当且仅当(请文中查看代码) 尼姆博弈(Nim): 有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜。 * 推广:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根, 可将一堆全取走,但不可不取,最后取完者为胜,求先手必胜或必败。 答案:当每一堆的异或值为0时,先手必败,否则先手必胜 SG函数: (请文中查看代码)
2018-3-31算法竞赛
C++算法及数据结构模板: 本文章原为2016-09-28的文章冲刺NOIp2016算法模板(C++),本人于2016-11-20日从OI退役,并于2017-09-09服役ACM,故将本篇文章更新。之后本文章将持续更新并囊括更多的不仅限于OI的算法与数据结构。 * 程序大部分没经过编译和测评,欢迎在评论区指出本文中的错误另:点开右下角像WIFI一样的标志进入RSS模式(XML文件)即可避免索引目录鬼畜的问题(现该问题已经解决)(可能需要向下翻一会才能找到本篇文章)OI比赛记得考前一定要练好DFS和记忆化DFS!!骗分必用! * 栈与队列: 栈: (请文中查看代码) 队列: (请文中查看代码) 当然有的时候你手写的数据结构需要比较大的空间,这样队列就会造成很多损失,所以相应的就有两种解决方法:一:STL;二:循环队列,只需改两个地方(代码如下); (请文中查看代码) 单调队列: - 例题:[Luogu P1823 音乐会的等待(我写了一篇此题的解题报告) 以下单调队列的标程就用的音乐会的等待的。 (请文中查看代码) STL: 关于每个STL我只会写一下是什么,怎么用(举例子的形式),不会说的太细 向大家推荐C++库及函数等查询网站:[cplusplus 可迭代容器的遍历方法: 要用到迭代器,以vector举例,代码如下: (请文中查看代码) Vector: 不定长度数组 (请文中查看代码) Queue: 队列,操作与Stack一样。 Priority_queue: 相当于堆 (请文中查看代码) Stack: (请文中查看代码) Deque: 双向队,操作与Stack一样 Bitset: 压位神器,只普及一下,不会用。 Set: (请文中查看代码) Multiset: 与Set用法一样,只是允许重复元素。 Map: (请文中查看代码) Algorithm里其他好用的函数: Next_permutation: (请文中查看代码) Lowerbound与Upperbound: (请文中查看代码) Merge: (请文中查看代码) sort: (请文中查看代码) Reverse: (请文中查看代码) Unique: (请文中查看代码) Random_shuffle: 留一个概念,不会用,生成数据的时候用。 数论: 快速幂: 普通快速幂: (请文中查看代码) 矩阵快速幂: (请文中查看代码) 筛法求素数: 欧拉筛法: (请文中查看代码) 应用举例: - 模板题 : [Luogu P3383 验证素数: 普通方法: (请文中查看代码) Miller-Rabin: 时间复杂度:(请文中查看代码) k是次数(见下文) 难度:★★★ 这里只说明一下原理,关于代码,自行百度吧。 - 根据费马小定理,随机选一个数(请文中查看代码)(mod p)则很有可能是素数。多次尝试(尝试k次)若都成立若都成立则判定为素数。 - 但是合数也有可能能通过这一测试:Carmichael数 - Carmichael概念:   卡迈克尔数是一种合数,使得对于所有跟n互质的整数a:$$ a^{n-1}\equiv1 $$(mod n) - 这种数用此方法测试时,除非random出其因子,不然都无法判断为合数。例如:6。 - 二次探测定理:若n为素数,方程$$ x^2\equiv1 $$(mod n)小于n的正整数解只有$$ x=1 $$和$$ x=n-1 $$。 - 先计算出m、j,使得$$ n-1=m*2^j $$且j尽可能大。 - 随机选一个数$$ a\in(1,n) $$ - 计算x=$$ a^m $$mod n - 然后将x不断平方j次,重复如下步骤:   1. 计算y=$$ x^2 $$mod n   2. 如果y=1并且$$ x\neq1,n-1 $$,此时一定不是素数,退出测试   3. x=y;   4. 如果y=1,暂时认为是素数,回到2.继续下一轮 若上述计算中没有满足2.和4.而正常退出,即不满足$$ a^{n-1}\equiv1 $$(mod n),一定不是质数 其次:这个博客写的很好(点击进入); 分解质因数——唯一分解定理: (请文中查看代码) 最大公约数和最小公倍数: gcd为最大公约数,lcm为最小公倍数`$$ab=gcdlcm$$` ; (请文中查看代码) 扩展欧几里德: 解决$$ ax+by=gcd(a,b) $$当a,b互质:$$ ax+by=1 $$解为:`$$ x+(b/gcd)t $$ 或 $$ y+(a/gcd)t $$` (请文中查看代码) 应用举例: - 模板题 : NOIp2012TG day2 T1 / Luogu P1082 逆元: 所谓逆元就是$$ ab\equiv1(\mod p) $$,a和b就在模p的意义下逆元。 利用同余的性质: $$ ab\equiv1(\mod p)\Rightarrow ab-1\equiv0(\mod p)\Rightarrow ab+pt=1 $$ 故可以用扩展欧几里德求解 (请文中查看代码) 那么同时有个除法取模的问题 有a / c mod p = a / c mod p * 1 = a / c mod p * c^(p-1) mod p = a * c^(p-2) mod p 即可 Catalan数: 原理理解:(两个应用模板)括号化矩阵连乘: `$$ P=a1×a2×a3×……×an $$`,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?(h(n-1)种)出栈次序一个栈(无穷大)的进栈序列为1,2,3,…,n,有多少个不同的出栈序列?详情请参照百度百科: (请文中查看代码) 应用举例: - 模板题 : NOIp2003 PJ / [Luogu P1044 高精: 读入、储存与输出: 以下代码块均包含以下语句 : (请文中查看代码) 读入与储存 : (请文中查看代码) 输出 : (请文中查看代码) 高精度加法: 高精加单精: (请文中查看代码) 高精加高精: (请文中查看代码) 高精度乘法: 高精乘单精: (请文中查看代码) 高精乘高精: (请文中查看代码) 高精度除法: 高精度除以单精度: 此处略微借鉴了一下铭哥的标程 (请文中查看代码) 高精度模: 高精模单精: (请文中查看代码) 压位: (请文中查看代码)注意⚠:使用压位的时候的读入不要读错比如不要把99存到数组的两个位置里面,而应该是一个; 树: 建树: 具体思路:对于一个节点来说,其他的任意一个节点,不是他的父节点,就是他的子节点。 传递闭包: 详见上面图论部分Floyd算法。 并查集: (请文中查看代码) (请文中查看代码) 树状数组: (请文中查看代码) 应用模型: - 树状数组求逆序对: (请文中查看代码) 线段树: (请文中查看代码) LCA: 倍增版LCA 思路如下 (请文中查看代码) 图论: 最短路: dijkstra: 经过了heap优化,前向星存边。在ACM类型赛事中,卡SPFA的题目比较多,建议直接掌握此类型最短路算法 (请文中查看代码) SPFA: 以下代码中包括邻接表(前向星)存图 (请文中查看代码) 次短路: 代码比较麻烦,不写了,说一下思路吧。 先用SPFA跑一遍,找出来最短路。把最短路记下来。 接下来,每次删掉最短路上的一条边,再跑一边SPFA。 运行一遍以后,路径长度最小的即次短路。 K短路: 部分内容引自[阿波罗2003的博客 Dijkstra+A*: 时间复杂度:$$O(nk\log{n})$$ 首先建反图,跑一次最短路算法,得到每个点到t的最短路的距离。 然后用当前走的距离加上到终点的最短路的长度作为优先级进行A*。 1. 当一个点第k次出队时,答案是它的优先级 2. 当终点第k次出队时,答案是它已经走的路程 (请文中查看代码) 最短路+可持久化堆: 时间复杂度:$$O(n+m\log{m}+k\log{k})$$ 考虑建立反图,然后跑最短路算法得到以t为根的最短路径生成树。 当走了一条非树边(u,v,w)意味着什么? 最终的路径长度就会因此增加f[v]−f[u]+w。 对于一条路径,我们依次将它经过的非树边记下来,约定得到的序列是这条路径的非树边序列。 考虑对于一个合法的非树边序列,我们可以找到唯一的一条s到t的路径与之对应。 因此,k短路的长度就等于第k小的代价和加上s到t的最短路的长度。 考虑如何来得到一个合法的非树边序列。 1. 找到一条起点在当前点p到根t的路径上的非树边 2. 令p等于这条边的终点。 我们可以通过这样的方法来得到所有的非树边序列。但是我们并不需要所有的非树边序列,因此当找到第x短路后再进行拓展状态,然后用优先队列来维护。 但是这样每次拓展时间复杂度可达O(m),总时间复杂度可以达到O(mklog(mk))。 令人无法接受。但是其中真正会被用到的状态十分少。 因此可以像UVa 11997那样进行优化。 当一个非树边序列出队时,代价和比它大的才可能有用。 因此,考虑一个非树边序列出队时通过下面的方法来进行得到新的序列: 1. 追加操作:假如最后一条非树边的终点为v,找到一条起点在v到t的路径上代价最小的非树边追加在当前非树边序列后 2. 替换操作:将最后一条非树边更换为代价比它大的1条非树边。 例如图中橙色虚线是被替换掉的非树边,紫色是新加入的非树边 考虑用一些可持久化数据结构(如可持久化斜堆,可持久化线段树,可持久化Treap)来维护起点在点u到根的路径上的非树边的代价。 对于替换操作, - 如果用的可持久化堆,那么把最后一条非树边替换为它所在的堆(你从哪个堆把它拿出来的)中它的左右子节点代表的边。 - 如果用的可持久化平衡树,那么把最后一条非树边直接替换为它的后继 - ...... 这是一个很稳定的算法,时间复杂度O(n+mlogm+klogk)。就是常数有点大,sad..... 注意一些细节 - 计算代价时需要考虑终点是否可以到达t - 考虑s=t时,要求的k短路包不包含0 - k短路不存在,队首为空 (请文中查看代码) 最小生成树(MST): 最小生成树即一个无向连通不含圈图中,连接G中所有点,且边集是E的子集,且边权和最小的生成树。(我解释的有点拗口) 最小生成树算法一共有两个:Prim和Kruskal算法,由于经并查集优化的Kruskal算法比Prim算法优秀得多,且Prim算法较容易理解,这里只给出Kruscal算法的模板。 Kruskal: 下面展现两种做法,一种是普通的暴力枚举做法,另一种是并查集优化过的。并查集优化过的算法比较快,但是要忽略生成树的形状。就是说如果你需要用到新生成树的形状,那么不能使用此种方法。 - 普通方法://类似Prim算法 (请文中查看代码) 以上版本是自己写的,感觉不对(上面的已经改成伪代码了),于是抄下来了粉书上的伪代码和讲解: (请文中查看代码)在上面的伪代码中,最关键的地方在于"连通分量的查询与合并":需要知道任意两个点是否在同一个连通分量中,还需要合并两个连通分量。最容易想到的方法是"暴力"——每次"合并"时只在MST中加入一条边(如果使用邻接矩阵,只需G[e[i].u][e[i].v]=1),而"查询"时直接在MST中进行图遍历(DFS和BFS都可以判断连通性)。 - 并查集优化 (请文中查看代码) 其实此处还有一个优化,虽然不会节省很长时间,但是,优势都是一点点积累出来的!就是循环枚举边的时候不用for而用while,当当前得到的最小生成树一共有n-1条边时,最小生成树就已经生成完了,剩下的边就不用再枚举了。 训练参考: - 最小生成树: [Slim Span(UVa1395) - 最小生成树: Buy or Build(UVa1151) 图的遍历: Floyed: (请文中查看代码) 还有一点相关的东西就是传递闭包(Transitive Closure) 即在有向图中,有时不必关心路径长度,而只关心每两点间是否有通路,则可以用1和0分别表示"连通"和"不连通"。得到的结果称为有向图的传递闭包。 只需将程序中的 (请文中查看代码) 改成 (请文中查看代码) 例题: - 传递闭包:[电话圈(Calling Circles,ACM/ICPC World Finals 1996,UVa247)(Floyd,连通分量) - Floyd:噪音恐惧症(Audiophobia,UVa10048)(Floyd,最大值最小路) 二分图染色: 基本思路就是用DFS,对于每个点,将与其连接的下一个点染上不同的颜色。 下面的程序是“双栈排序“里二分图染色的子程序: (请文中查看代码) 附上几篇不错的博客:(感谢喵头鹰、暗金色、LOI_summer) [喵头鹰的博客 暗金色的博客 LOI_summer的博客 二分图匹配: 匈牙利算法: (请文中查看代码) 可以参考该篇博客:[匈牙利算法简单易懂 最大连通子图: Tarjan: (请文中查看代码)[键盘里的青春的博客中对tarjan算法的讲解比较详细,学习tarjan算法请看这篇文章。同时在此感谢此文章对我学习tarjan算法的帮助。 缩点: (请文中查看代码) 割点: 在一个无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。 也就是说,这个点维持着双联通的继续,去掉这个点,这个连通分量就无法再维持下去,分成好几个连通分量。 仅需在以上Tarjan算法中稍加改动,即可得到割点算法。 (请文中查看代码)缩点、割点、桥的内容感谢[Styx-ferryman的博客 网络流: 最大流: EdmondsKarp: (请文中查看代码) 分层图: 例如bzoj1579这种选择k条免费边的题目,可以建k+1层图,每一层图之间建立免费边,跑一边最短路,即可得出答案.(以下代码为有向边) (请文中查看代码) 动态规划: 钟长者说:有几个未知量,DP数组就有几维,若求个数能再省掉最后一维。 然而这只是一般情况,例如有个例外:HAOI2012 音量调节/[Luogu P1877,这道题就不能省掉最后一维。 铭哥说:重推所有的DP方程是复习DP的最佳方法 线性DP: 最大递增子序列和: (请文中查看代码) 最大连续子序列和: (请文中查看代码) 最长公共子序列和: (请文中查看代码) 字符串转换问题: 给定A串和B串,有删除一个字符、插入一个字符、改变一个字符三种操作,求A变到B的最少操作次数。 f[i][j]表示A的前i个字符变成B的前j个字符所用的最少步数。 (请文中查看代码) 最长公共子序列: LCS c[i][j] = |LCS(a[1...i],b[1...j])| (请文中查看代码) 最长不下降子序列: (请文中查看代码) 背包DP: 01背包: (请文中查看代码) 优化: (请文中查看代码) 例题: - Luogu1048 [菜药 完全背包: (请文中查看代码) 混合背包: 即有好几种背包的条件,分别写dp满足条件就可以了(比如NOIp2014TG的飞扬的小鸟) (请文中查看代码) 例题: - NOIp2014TG 飞扬的小鸟 分组背包: 这里有一篇[分组背包博客写的不错,参考这篇博客吧。感谢博客的作者nywsp。 - 练习题:luogu P1757 分治算法: 二分: (请文中查看代码) (请文中查看代码) 三分: 三分法常用来找凸点或凹点。 图片和思路取自黑码的博客 先取 L,R] 的中点 mid,再取 [mid,R] 的中点 mmid,通过比较 f(mid) 与 f(mmid) 的大小来缩小范围。 (请文中查看代码) (请文中查看代码) 排序算法: 插入排序/希尔排序: 因希尔排序是插入排序的升级版,故将两个算法放在了一起 具体分析请参考文章:[插入排序与希尔排序 插入排序(1.0): 时间复杂度: $$ O(n^2) $$ (请文中查看代码) 插入排序(2.0): (请文中查看代码) 希尔排序: 时间复杂度: $$ O(n^{\frac{3}{2}}) $$ (请文中查看代码) 归并排序: (请文中查看代码) 字符串算法: Hash: 哈希大法好 (请文中查看代码) Trie树: Trie数又叫字典树,比如由字符串"abc","ab","bd","dda"创建的Trie树如下图 以下Trie模板以HDU 1251为题目而写 (请文中查看代码) KMP: (请文中查看代码) 博弈论: [Kuangbin的ACM博弈论教程 Nim博弈: 题目:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根,可将一堆全取走,但不可不取,最后取完者为胜,求先手必胜或者必输。 解法:求每堆的异或值,若为0则必输,否则必赢 SG函数: (请文中查看代码) 暴力算法: 分块: 推荐学习视频:[UESTCACM 时间复杂度:$$O(n^{\frac{3}{2}})$$ (请文中查看代码)
2018-1-20杂记
Deemo: 《Deemo》是雷亚公司出品的一款以弹钢琴为主题的音乐游戏,游戏过程中通过不断的完成曲子获得分数会获得整个故事的一部分剧情。最近我终于将Deemo打通关,获得全部剧情后被故事结局催泪成功,现在我将这个故事分享给大家。(Deemo 3.0完整剧情) Deemo是一个小黑人,高高瘦瘦有一副弹钢琴的手,他沉默寡言从不言语,他的弹钢琴的乐声特别动听,似乎能激起内心所有感情。 Deemo生活在一个漆黑的世界里,就像只有夜晚。它的宅邸里有一个敞亮的大厅,大厅中间架着他的那副钢琴。大厅的左边是书房,Deemo是书房的常客,但除了Deemo,还有和Deemo一起生活的面具小姐。大厅的右边是一扇锁着的门,无论是Deemo还是面具,都不知道打开他的方法。在Deemo世界里,他和面具小姐便是所有的存在。面具小姐只有Deemo一半高度,一直披着斗篷戴着风帽还有那副面具,每日的活动就是四处转转与在书房里写琴谱。 某一天,Deemo正在大厅里弹着琴,就像往常一样,突然天空上亮了微弱的一道光,仔细看去竟是天空上开了一扇窗户,从那扇窗户里掉落的,是一个小女孩。Deemo赶紧跑过去接住了小女孩。 小女孩已经忘却了自己的名字、自己之前在做的事情,忘却了一切,只知道,她需要回到原来的那个世界。但是那扇窗户太高了,怎么够得到呢?Deemo想了一个法子,Deemo的琴声拥有让树苗生长的能力,他想不断弹琴让树苗长高知道能够到那扇窗户。 按照计划,Deemo每天都坐在大厅里弹琴,而小女孩就四处转转,从大厅转到书房,在书房里翻阅着不同的书,她时常能发现夹在书里的琴谱,然后拿去给Deemo弹奏。有一次,小女孩在书架上发现了一串数字——121.518549... 树苗在不断的长高,当树苗长到了一定高度变成了大树的时候,大厅右边的门神奇的打开了。喜欢探索的小女孩就率先进去侦查。在门后的房间里,有两扇封闭的玻璃窗——这是这里唯一能观察外界的地方了。透过窗户,小女孩发现外面是灰蒙蒙的一片,就像有毒雾一样,什么都看不清楚甚至有点恐怖。房间里还有一张独脚圆桌和一把椅子,椅子上放着一个吓人的猫型玩偶,小女孩看着那个玩偶,感觉好熟悉,但是又不敢去长看,因为它长得实在是太吓人了。圆桌桌脚上雕刻着另外一串数字——25.040854...还没来得及思考,面具小姐进了这间屋子。面具小姐好像没有注意到小女孩的存在,望着房间里的一幅画出神,嘴里还一直默念着“我该怎么做?...这样做真的值得吗?...我想...”。小女孩跑过去跟面具小姐打招呼,两人在寒暄过后面具小姐问,现在树有多高了?听到答案后的她只是“哦”了一声便离开了。小女孩便去欣赏那副画,画中是一个通往下方的楼梯,那副画真实到如果没有画框,恐怕会有不少人撞到这幅画。突然小女孩觉得有些头晕,便离开房间休息去了。 大树还在不断长高。一天,小女孩和Deemo玩耍的时候,把猫玩偶放到了画旁边,突然发现画好像有什么地方变了。原来是画变成了现实,楼梯也变成了真实的。Deemo和小女孩顺着楼梯走下去,来到了一个地下室。地下室中间架着另外一架钢琴。整个地下室和钢琴都被藤蔓缠绕着。钢琴上有一张琴谱,Deemo便试着用这架钢琴弹了这篇琴谱。曲子弹完,神奇的事情发生了,藤蔓全部退去,露出了地下室本该有的模样。小女孩在地下室里又发现了许多琴谱。与此同时,面具小姐来到树下,接住了一片树上掉下的树叶,停滞一会儿后,将其捏碎,洒落,并离去。 时间一点点流逝,转眼间大树又长高了许多。高到一定高度,树上出现了一个树洞。进去树洞后竟又是另一片天地,那就像是宅邸的第二层,有大厅,左房间和右房间,当然,这两个房间都是锁着的。大树不断长高,右房间的门也如Deemo预测的一样打开了。右边的门后不是房间,而是一节通往更高地方的楼梯,楼梯的尽头有一扇被藤蔓缠绕着的大门,无法打开。楼梯旁边还有一张书架,暑假的高处有一把钥匙,小女孩知道,那肯定是左房间的门的钥匙。于是它从书架上抽出许多书籍,摞高踩上去够那把钥匙。小女孩还是够不到钥匙,由于重心不稳,摔落了下来,这次接住他的还是Deemo,Deemo也帮她拿下了那把钥匙。 宅邸二层左房间的门开了,那是一个天台,同样敞亮,天台上还有一架望远镜。小女孩看到这幅景象,不禁想到,这里之前肯定有人住过。 右房间通往的那扇大门,一定是和大树的高度有关系的。果不其然,当大树长到最高,无法再生长的时候,缠绕在那扇大门上的藤蔓散去了。小女孩正要去推开那扇门,突然面具小姐冲过来,拉住他的胳膊阻止她,两人就这样撕扯起来。Deemo看到这幅景象,走过去摸了摸面具小姐的头,面具小姐只好放开了小女孩。 大门后是另一个天台,天台中间架了最后的一把琴,在这里,天上的那扇窗户不再这么遥远。剩下的,就要靠Deemo演奏曲子来架设虚幻的楼梯来送小女孩回家了。 楼梯架设完毕,Deemo把小女孩抱上了最后一个台阶。小女孩泪眼望着Deemo,毕竟和Deemo相处了这么多天,她也舍不得Deemo。 Deemo来到琴前,开始了最后一首曲子的演奏。最后一首曲子琴声轻柔悠扬像是在向小女孩送去最美好的祝福。每一个琴键被按下去,最后一个台阶就上升一点高度,向那扇窗户接近,向Deemo离去。 最后一键按下,Deemo的样子似乎有了变化。Deemo不再是那个小黑人,他化成了人的模样,同样高高瘦瘦,和小女孩的模样极像。这时面具小姐也摘下了她一直带着的面具,面具下面的面庞与小女孩一模一样。小女孩抑制不住自己的眼泪了,她终于记了起来,她叫Alice,他有个他最爱的哥哥,叫Hans,是世界钢琴比赛冠军。 那一天,Alice和Hans抱着猫玩偶去玩,小女孩太兴奋,穿过马路的时候没有注意车辆。一辆大货车冲了过来,Hans赶紧抱住了Alice,并背向货车,两人都倒在了血泊里。 Deemo化成的样子便是Hans的样子,他向小女孩望去,微笑,然后自己化成了泡影,消失了。小女孩也最终进入了窗内。 Alice从病床上醒来了,她缠着绷带,挂着药瓶。醒过的她赶紧跑向窗边,拉开了窗帘,发现窗外是一个繁华的城市。她意识到,他的哥哥Hans已经离开人世了,便跪在地上悲伤的大哭了起来... * 这个故事到此就结束了,其实这是根据真实事件改编的故事。那两串数字,121.518549和25.040854其实是经纬坐标,我们定位一下就会发现,这是一家位于中国台湾的建在书店上面的医院,而小女孩向窗外望去的大雾和感到眩晕都是因为她在被车撞过之后患上了脑震荡。 其他的就不多说了,这篇故事留在这里,留给大家细细品味。 感谢阅读。
2017-12-9算法竞赛
插入排序与希尔排序: 今天刚参加了华中师范大学的ACM新生杯,趁着还保持着对算法的敏感度(虽然今天A的题没有几道是真正的算法题),来写一篇关于插入排序及其升级版算法希尔排序的介绍 部分内容取自于知乎用户彭湖湾的文章 概念: 插入排序即将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。一般此算法时间复杂度较高,故适用于少量数据的排序 插入排序(1.0): 插入排序1.0即直接插入排序,将已知有序序列遍历一遍,以找到插入元素的位置,将该位置面的元素全部向后移动一位。 具体实现步骤:(对待插入元素) : 1. 和相邻的左边元素的值比较大小 2. 如果左边元素大于待排序元素,则交换两者的值,左边元素的值“右移”一位。 3. 如果左边元素小于等于待排序元素,说明已经插入到“合适位置”了,一趟插入结束。 示例如下图: 时间复杂度:(请文中查看代码) 实现代码如下: (请文中查看代码) 插入排序(2.0): 插入排序2.0即对待插入元素在已知有序序列中找到位置的过程进行了优化。 既然序列是已知的、有序的,那么我们自然可以想到在这过程中使用二分法。 代码如下: (请文中查看代码) 希尔排序(插入排序 3.0): 希尔排序又被称为步长递减插入排序或增量递减插入排序。 设h为步长,那么希尔排序的基本步骤为: : 1. 选择一个递增序列。并在递增序列中,选择小于数组长度的最大值,作为初始步长 h。 2. 开始的时候,将数组分为h个独立的子数组(1中h), 每个子数组中每个元素等距离分布,各个元素距离都是h。 3. 对2中分割出的子数组分别进行插入排序 4. 第一轮分组的插入排序完成后,根据递增序列(逆向看)减少h的值并进行第二轮分组, 同样对各个子数组分别插入排序。 不断循环1、2、4, 直到h减少到1时候, 进行最后一轮插入排序,也就是针对整个数组的直接插入排序(这个时候分组只有1个,即整个数组本身) 5. 一开始的时候h的值是比较大的(例如可以占到整个数组长度的一半),所以一开始的时候子数组的数量很多,而每个子数组长度很小。 随着h的减小,子数组的数量越来越少,而单个子数组的长度越来越大。 代码如下: (请文中查看代码) 希尔排序图示: 时间复杂度: (请文中查看代码) 本文章到此为止,谢谢阅读
2017-7-8学习笔记
Git学习笔记: What's Git ? Git是一个开源的分布式版本控制系统,可以有效、高速的处理从很小到非常大的项目版本管理。 一说到版本控制系统可能很多人会想到SVN,SVN作为一个集中式版本控制系统可是占据了不少程序员的青春,但是,Git的出现让SVN黯然失色。为什么呢?通俗来说,Git比SVN快的可不是一点半点。 什么是版本控制系统呢?看看现在普遍使用的微信、QQ,他们都是有版本的,所以你才会不断的更新,每次更新都有BUG被解决或者新功能的加入。而Git的功能可以说就是管理这些所有版本。公司通过Git将新版本发布,我们才能获取到新版本的app。 Git的安装: Mac环境和Linux环境下的安装: 博主是使用Mac的,就先来讲讲Mac环境下的安装。 首先,我建议你下载一个Xcode,作为程序员这个是少不了的。 打开终端(命令行),一条指令即可完成安装: (请文中查看代码) 此方法同样适用于Debian或Ubuntu Linux。老一点的Debian或Ubuntu Linux,要把命令改为sudo apt-get install git-core,因为以前有个软件也叫GIT(GNU Interactive Tools),结果Git就只能叫git-core了。由于Git名气实在太大,后来就把GNU Interactive Tools改成gnuit,git-core正式改为git。(摘自廖雪峰的官方网站) Windows环境下的安装: 无 工作区、暂存区和版本库的介绍: 我个人觉得学各类汇编语言之前先了解一下理论知识会学的比较快,于是我们先来看一下关于Git的理论知识。 工作区叫Working Directory;暂存区叫Stage;版本库叫做Repository。 当你要对某一个文件要通过Git上传,你首先要建立版本库,你的版本信息将存放在这里。 你的文件一开始一定是要存在本地文件夹里的,这个本地文件夹我们就可以称其为Working Directory。 在你上传文件到工作链之前,需要先将文件提交到stage暂存区,再将stage中的文件一并提交的master工作链。 创建版本库: (请文中查看代码) 这样,你就可以创建一个名为<file name>(你想要的名字)的Git版本库了。 之后系统会告诉你这是一个empty Git repository: (请文中查看代码) 然后你会发现这个目录下多了一个.git文件(隐藏文件夹)(不要动它) - 在目录下添加文件: 接下来我们学习一下最基本的"提交": 首先将文件置于你的工作目录下,也就是工作区。再使用如下指令: (请文中查看代码) 即可将文件提交。 下面介绍两个比较常用的命令: (请文中查看代码) 这条命令可以让你查看当前仓库的状态:红色文字是在工作区内的文件,绿色的是在暂存区中的文件。 (请文中查看代码) 这条命令可以查看这个版本与上个版本间文件的不同,这也是版本控制系统的方便快捷之处。 版本操作: 作为版本控制系统,肯定要有查看各个版本的能力,我们可以使用以下指令来查看你commit的历史记录。(第二行的指令可以使其更简洁) (请文中查看代码) 版本回溯: 在Git中用HEAD表示当前版本,上一个版本是HEAD^,上上个版本是HEAD^^,往上100个版本是HEAD~100 用回退命令将版本回退: (请文中查看代码) 这时再使用git log查看目录你就发现已经看不见HEAD的内容了。 但如果你能找到其commit ID,那么你仍然可以恢复其内容: (请文中查看代码) commit ID并不需要写全,写前几位,Git便可以自动查找 你可以用以下命令查看每一次的命令,以防止你找不到commit ID。 (请文中查看代码) 撤销修改: - 丢弃工作区的修改 (请文中查看代码) - 将暂存区的修改撤销,重新放回工作区 (请文中查看代码) Ps.用HEAD表示最新的版本 删除文件: (请文中查看代码) 如果你删错了: (请文中查看代码) git checkout命令是用版本库里的版本替换工作区的版本,所以无论工作区的修改还是删除都可以还原。 远程仓库GitHub: - 创建SSH Key (Secue Shell Key) (请文中查看代码) 然后一路回车。在用户主目录里找到.ssh目录,里面会有id\rsa.pub和id\rsa两个文件(秘钥对),id\rsa是私钥,不能泄露出去,id\rsa.pub是公钥,可以放心地告诉别人。 - 登录GitHub,打开"Account settings","SSH Keys"页面,点击"Add SSH Key",填上任意Title,在Key文本框里面粘贴公钥。 Ps.GitHub允许添加多个Key,方便在不同电脑上提交推送文件. 远程仓库操作: - 添加远程库: 先在GitHub上建立一个新仓库,名字为目前电脑上版本库对应的名字。 将其与已有本地仓库关联,并把本地仓库的内容推送到GitHub仓库: (请文中查看代码) 添加后远程库的名字是origin,这是Git的默认叫法。 然后把本地库内容推送至远程库: (请文中查看代码) (用 git push命令把当前分支master推送到远程库) Ps.master是仓库的主分支 由于远程库为空,第一次推送master时加上 -u 参数,这样本地与远程的master分支关联起来,在以后的推送或拉取时便可以简化命令 自此只要把本地做了提交,就可以用以下命令将本地master分支推送到远程库: (请文中查看代码) - 从远程库克隆 (请文中查看代码) 可以用命令ls查看当前目录文件。 分支管理: - 创建、合并分支 创建: (请文中查看代码) git checkout 加上-b参数表示创建并切换,相当于以下两条命令: (请文中查看代码) 查看当前分支用git branch命令. 把分支合并到master: (请文中查看代码) - 删除分支 (请文中查看代码) Git在实际生产中的应用: - --no-ff模式下的merge与实际开发 通常在合并分支时,If possible,Git会使用Fast forward模式,在这个模式下,删除分支后会丢掉分支信息。若强制禁用Fast forward模式,Git会在merge时生成一个新的commit,这样分支历史上就可以看出分支信息。 (请文中查看代码)因为本次合并后会创建一个新的commit,所以加上-m注释参数,把commit描述进去。(即可达到上图合并模式) - Bug处理 当你遇到一个代号为101的Bug,你想创建一个分支issue-101来修复它。但dev上进行的工作未完成而不能提交,我们就可以用stash功能将当前工作现场“储藏”起来,等以后恢复现场后可以继续工作: (请文中查看代码) 并且可以用git stash list命令查看stash目录: (请文中查看代码) 有两个恢复工作现场的方式: 1. 若apply后面不加任何内容则默认为最后一次stash的内容 (请文中查看代码) 上述命令提出后不会删除stash,用以下命令删除 (请文中查看代码) 2. 提出工作现场后删除stash的命令: (请文中查看代码) - 多人协作 查看远程库信息的命令: (请文中查看代码) 或者加个参数-v现实更详细的信息 (请文中查看代码) 创建远程origin的分支到本地 (请文中查看代码) - 解决冲突 把最新的提交从远程库抓取下来: (请文中查看代码)若无法pull是因为没有与远程库建立连接。 指定本地分支与远程分支的连接: (请文中查看代码) 解决完冲突后再push即可 标签: - 创建标签 首先切换到需要打标签的分支上再运用命令打标签: (请文中查看代码) Ps.commit ID不写的话就是最新一次的commit 用命令查看标签: (请文中查看代码) (标签将字母排序而不按时间顺序) 可以用命令来查看标签信息: (请文中查看代码) 可以创建带说明的标签: (请文中查看代码) 还可以通过加入-s参数用私钥签名一个标签: (请文中查看代码) 签名采用PGP签名,因此必须首先安装GunPG 标签操作: 删除标签: (请文中查看代码) 推送标签: (请文中查看代码) 自定义Git: 让Git显示颜色 (请文中查看代码) 忽略特殊文件: 编写.gitignore文件,将需要忽略的文件全部列入即可 - 配置别名 通俗地来讲就是给命令换个写法: Eg. st表示status: (请文中查看代码) co表示checkout: (请文中查看代码) ci表示commit,br表示branch等等。 Ps.--global参数是全局参数,对在这台电脑上的所有Git仓库都生效 用unstage代表reset HEAD (请文中查看代码) 用last显示最后一次提交信息 (请文中查看代码) 配置高端log: (请文中查看代码) - 配置文件:目录:.git/config alias]后面的即为别名 搭建Git服务器: You need :一台运行Linux的机器(推荐Ubuntu或者Deblan) 假设已有sudo权限的用户账号: 1. 安装Git 2. 创建Git用户,用来运行git服务: (请文中查看代码) 3. 创建证书目录: 把所有的公钥全部导入到/home/git/.ssh/authorized\_keys文件里,一行一个 4. 初始化Git仓库: 选定一个目录为Git的仓库:假设为/srv/sample.git 在/srv目录下输入命令: (请文中查看代码) 把owner改为git: (请文中查看代码) 5. 禁用shell登录 编辑/etc/passwd:找到: git:x:1001:1001:...:/home/git:/bin/bash 改为:git:x:1001:1001:...:/home/git:/usr/bin/git-shell 6. 克隆远程仓库 在各自的电脑上运行以下命令即可克隆: (请文中查看代码) - 管理公钥:可以用Gitosis来管理公钥 - 管理权限:Git不支持权限控制,但是支持hook,用Gitdite可以达到目的 码了一晚上总算是码完了。文中部分内容转自[廖雪峰的官方网站.感谢廖雪峰老师
2016-9-11算法竞赛
逆序对: 今天想写一个专题:如何求一串数中的逆序对个数。 具体来讲,一共有两种比较好的方法: 1. 归并排序 2. 树状数组 两种方法的比较: 先来比较一下两个方法: | 方法 | 时间复杂度 | 空间复杂度 | 代码长度 | 理解难度 | | :-- | :-------- | :------- | :------ | :----- | | 归并排序 | (请文中查看代码) | 相比较长(除非你用STL) | 容易 | | 树状数组 | (请文中查看代码) | 短小精悍(用不到STL) | 一般 | 好吧,其实并没有多大区别,但是还是建议这两个方法都学一下 * 归并排序: 其实就是在归并排序的时候发现一个较大的数在前面,计算一个逆序对个数,废话不多说,直接看代码理解吧。 代码: (请文中查看代码) * 树状数组: 详细解释请看我的另一篇博文[《树状数组》,具体原理与代码就不写了。(偷懒
2016-8-30算法竞赛
树状数组: 树状数组作为一种数据结构,在OI竞赛中也是一项常用常考点      Above all,树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为(请文中查看代码)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。 * 树状数组的核心代码: 关于树状数组有一段核心代码,即lowbit函数 (请文中查看代码)此函数用来找当前树状数组的上一个或下一个数组位置。 树状数组的经典操作: 修改操作: (请文中查看代码) 查询操作: (请文中查看代码) 还有一个看似比较高端的操作 (请文中查看代码) 树状数组的实际应用: 关于区间求和的程序: (请文中查看代码) 关于逆序对: 求逆序的思路: 可以把数一个个插入到树状数组中, 每插入一个数, 统计比他小的数的个数getsum( data[i] ),对应的逆序对个数为 i- getsum( data[i] ),其中 i 为当前已经插入的数的个数, getsum( data[i] )为比 data[i] 小的数的个数,i- getsum( data[i] ) 即比 data[i] 大的个数, 即逆序的个数。最后需要把所有逆序对个数求和,就是在插入的过程中边插入边求和。 但如果数据比较大,就必须采用离散化方法, 假设输入的数组是9 1 0 5 4, 离散后的结果aa[] = {5,2,1,4,3}; 在离散结果中间结果的基础上,那么其计算逆序数的过程是这么一个过程: - 输入5,调用upDate(5, 1),把第5位设置为1 1 2 3 4 5 0 0 0 0 1 计算1-5上比5小的数字存在么? 这里用到了树状数组的getSum(5) = 1操作,现在用输入的下标1 - getSum(5) = 0 就可以得到对于5的逆序数为0。 - 输入2, 调用upDate(2, 1),把第2位设置为1 1 2 3 4 5 0 1 0 0 1 计算1-2上比2小的数字存在么? 这里用到了树状数组的getSum(2) = 1操作,现在用输入的下标2 - getSum(2) = 1 就可以得到对于2的逆序数为1。 - 输入1, 调用upDate(1, 1),把第1位设置为1 1 2 3 4 5 1 1 0 0 1 计算1-1上比1小的数字存在么? 这里用到了树状数组的getSum(1) = 1操作,现在用输入的下标 3 - getSum(1) = 2 就可以得到对于1的逆序数为2。 - 输入4, 调用upDate(4, 1),把第4位设置为1 1 2 3 4 5 1 1 0 1 1 计算1-4上比4小的数字存在么? 这里用到了树状数组的getSum(4) = 3操作,现在用输入的下标4 - getSum(4) = 1 就可以得到对于4的逆序数为1。 - 输入3, 调用upDate(3, 1),把第3位设置为1 1 2 3 4 5 1 1 1 1 1 计算1-3上比3小的数字存在么? 这里用到了树状数组的getSum(3) = 3操作,现在用输入的下标5 - getSum(3) = 2 就可以得到对于3的逆序数为2。 - 0+1+2+1+2 = 6 这就是最后的逆序数 离散化的方式: (请文中查看代码) val存放原数组的元素,pos存放原始位置,即node[i].pos = i。 把这些结构体按照val的大小排序。 reflect数组存放离散化后的值,即reflect[node[i].pos] = i。 这样从头到尾读入reflect数组中的元素,即可以保持原来的大小关系,又可以节省大部分空间。 - 下面来看具体程序 (请文中查看代码)