算法总结
一、 动态规划和递推
dp一般的解题步骤： 分析问题，弄清题意——从原问题中抽象出模型——根据模型设计状态，要求状态满足最优子结构和无后效性——直接设计状态有难度的话则需要考虑转化模型——根据设计的状态考虑转移——如果过不了题目要求的数据范围，则需要考虑优化 由于动态规划涉及的内容太多，只言片语难以讲清，所以附件中放了很多篇关于动态规划的文章，大部分系原创，并附上了一些经典的论文，主要讲了DP的优化，一些特殊的状态设计技巧
Dp和递推没有本质区别，都是用一些状态来描述问题，并记录下一些信息，根据已知信息推出未知信息，直到得到问题的解
关于DP的优化有两篇神级论文，放在附件里面了，写的非常好。
二、 图论及网络流
最小生成树：克鲁斯卡尔算法和普利姆算法，
——重要性质1：最小生成树上任意两点的路径的最大边最小
——重要性质2：最小生成树的多解（方案个数）只与相同权值的的边有关（省队集训题生成树计数）
最短路：spfa算法、堆+迪杰斯特拉算法
Spfa算法是基于松弛技术的，随机图效果极佳，最坏（网格图或存在负权环）O(nm)，适用于任意图，能够判断负权环 ——判负权环的方法：记录每个点当前从原点到它的最短路上边的条数，如果某次更新后这个条数>n-1则存在负权环
堆+迪杰斯特拉则是用了贪心的思想，不断扩大确定dist的集合，同时更新dist，如果边权有负值就不能做，复杂度是O((n+m)logn)的
拓扑排序：可以将有向图转化为一个线性的序列，满足一个点所有的前驱结点都出现在这个点在序列中的位置之前。可以判断这个有向图是否有环
——一个简单而实用的扩展：给树做类top排序，可以有类似的功能，即每次去掉叶子结点，将树转化为一个具有拓扑关系的序列
——再扩展：树同构判断，可用类top确定树根是谁，再最小表示法+hash即可
强连通分量、缩点：tarjan算法
核心是每个点记一个时间戳ti[i], 另外low[i]表示i点能延伸出的搜索树中节点的ti[i]的最小值，还要维护个栈记当前路径上的点，low[i]初始化为ti[i]，如果搜完i了，ti[i]=low[i]则当前栈顶到i的所有点会在一个强连同分量内。 关键代码： procedure dfs(i:longint); var j,k:longint; begin
inc(time);ti[i]:=time;v[i]:=true;low[i]:=time; inc(ed);q[ed]:=i;j:=h[i]; while j<>0 do begin k:=point[j];
if ti[k]=0 then begin
dfs(k);if low[k] if v[k] then if ti[k] if ti[i]=low[i] then begin inc(num);k:=0; repeat j:=q[ed];f[j]:=num;v[j]:=false;k:=k+a[j]; if b[j] then bar[num]:=true; dec(ed); until q[ed+1]=i; vl[num]:=k; end; end; 欧拉路： 含义：不重复地经过每条边的一条路径，如果起点和终点相同则叫“欧拉回路”，起点和终点不同叫“欧拉路径” 存在欧拉路径的条件：至多两个点的度为基数（回路则要求全都为偶数） 实现：（非常简单） 一顿乱dfs就可以了，每次退栈的再将这条边加入答案序列 procedure dfs(i:longint); var j,k:longint; begin j:=h[i]; while j<>0 do begin k:=point[j]; if w[(j+1)>>1]>0 then begin dec(w[(j+1)>>1]); dfs(k); inc(ans[0]); ans[ans[0]]:=dir[j]; end; j:=next[j]; end; end; 上面的代码中正边和反边的编号是相邻的，关注inc(ans[0])的位置，是在递归调用的后面 哈密尔顿回路 含义：经过所有点的一个回路 这是个NPC问题，只有近似算法（暴搜就不提了） 比较好用的是模拟退火，以环上相邻两点有边相连的个数作为估价值，随机化调整 二分图匹配： 最大匹配：匈牙利算法，理论O(nm)，实际复杂度好很多 最佳匹配：KM算法，理论O(n^2m)，实际复杂度同匈牙利一样相当不错 ——重要性质：最小可行定标和 = 最优匹配 KM算法中构造了一个非常不错的不等式lx[i] + ly[j] >= w[i,j]，有的题目可以利用这个 不等式套KM求出最小可行定标和，如20101112 ti糟糕的传染 网络流 非常神奇的一个东西，数学味有余而图论味不足，通常用来解决限制条件太强，以至于无论如何都表示不了状态的题，很多经典例题见《网络流24题》 通常使用的最大流算法是dinic，代码要背熟，一般能10分钟之内敲出来 最大流最小割定理 经典模型：最小割模型，最大权闭合图，平面图网络流转最小割 ——参考神文胡伯涛论文 费用流 相当于网络流的一个强化，能多处理一维信息。具体来讲就是给边多加一个“费用”，每次增广的费用就是这条增广路的费用之和*流量。 费用流有最小费用最大流和最大费用最大流，用spfa每次找条最短（长）路增广即可 最小费用最大流还可以用zkw算法加速，差不多比裸spfa+增广快10倍的样子（在二分图网络流上尤为明显），我和盾盾研究了一种更nb的费用流，我命名为“距离标号连续增广路费用流算法”，能够秒杀几千个点的稠密随机图，二分图就更不在话下了，速度几乎达到了dinic的三分之一的样子，而且实现非常简单！ 经典例题参考《网络流24题》 三、 贪心 贪心的关键是找结论，同时给出证明，然后就可以利用这个结论来做题了 当然，考场上对你猜出的结论给出证明通常是很难的，所以用贪心法解题需要丰富的经验，正确的“题感”，胆大心细才能搞出来 由于经常要取最优值，所以常常与堆、平衡树等数据结构结合起来 贪心+其他算法： 由于贪心往往能大幅化简状态，利用问题的某些“单调性”，加上贪心的思想，往往能是问题大幅简化，从而结合其他算法解决问题 经典例题：田忌赛马，利用贪心来确定状态 四、 分治 分而治之的思想在信息学竞赛中是非常重要的，下面主要介绍一下分治的经典应用 二分查找 思想很简单，功能很强大，边界要注意，负数要特判（NOI2010 PIANO） 在非负数范围内的二分一般写法 如果是l := mid - 1或+ 1则mid := (l + r) div 2 而如果是r := mid - 1 或 +1则 mid := (l + r + 1) div 2 快速幂 a^b = (a^(b div 2))^2 + ord(odd(b))*a 取模也适用 ——扩展：求(1 + a + a^2 + a^3 + … + a^n) mod p的值 O(logn)算法：分治 1 + a + a^2 + a^3 + … + a^n = (1 + a + a^2 + a^3 + … + a^(n div 2))*a^(n div 2) + ord(odd(n))*a^n 两个快速幂可以合到一起写 快速排序，归并排序 任何一本算法书上都会讲的，这里就略过了，值得一提的是快排记得加上随机化 k := a[random(r - l + 1) + l] 二分答案（0-1分数规划） 当答案满足在解集空间中连续分布时可以使用二分答案，将最优性问题转化为判定性问题，通常标志：最大值最小等 差分约束系统中有时也需要二分答案以解决最优性问题，顺便能多得到一个信息 二分答案还有一个优势，那就是已经知道了答案，那就可能可以将一些直接做必须在线的操作转化为离线操作（也就是说，我可以排序然后判定），诸如要求你判定“第一句出现矛盾的话”之类的题目（poj 3657） 0-1分数规划也是经典的利用二分答案来做的一类问题 通常是要求你最小化 f(x)/g(x) 令ans = f(x)/g(x) 则f(x) - g(x)*ans = 0 重构权，将f(i) - g(i)*ans作为新权值，用相应算法求出一个“最小值”，判断是否>=0，接着二分即可 详细说明及数学证明见集训队07胡伯涛论文 树的分治 一般用来解决树上的路径或统计类问题，每次只考虑跟树根有关的信息，然后递归分治处理 树的分治通常有基于点或基于边的分治，基于点的难合，基于边的复杂度太高 这里只介绍基于点的分治 步骤： 处理跟当前树根有关的信息 重新计算子树大小 在子树中选择重心为根，递归到相应子树处理 因为每次选了重心，所以递归总共logn层，每层O(n)的复杂度，总复杂度就是O(nlogn) 更详细严谨的介绍见漆子超论文 二分搜索 直接搜的复杂度是指数级的的话，一般是40左右的数据量，hash一半，搜一半，搜后面的时候利用之前的hash信息合并出原问题的解 而直接搜的复杂度达到阶乘级的话n一般就不超过20了，做法一般差不多 经典例题：POI02szy，NOI2001方程的解数 五、 搜索 作为信息学竞赛中的所谓“万能算法”，搜索可以说是计算机学科所具有的最大特点了，自然地，搜索算法的应用自然也是非常之广泛，除了专门的搜索题，搜索一般可以用来部分预处理，打表找规律，当然还有骗分 搜索的一般步骤：确定状态——选择搜索方式（dfs、bfs）——确定产生式规则——开始搜索 搜索的常见优化方式： 改变状态表示 这个需要根据题目而定，确定一个漂亮的状态表示，可能就有希望转向记忆化了，即使不行，搞出一个漂亮的状态表示是解决一道麻烦题的最重要的一步，再者，调试起来也会容易许多。 优化搜索顺序 这个优化在多数搜索中能起到摧枯拉朽的提速效果，通常我们选择枝叶较少的儿子先扩展，例如大名鼎鼎的dancing Links，除了利用双向十字链表去除冗余状态，每次选择可扩展数最少的儿子扩展同样给它的神速创造了条件。（poj的一道数独题，我在选择拿出去扩展的点的那个循环中<和<=的区别就是200ms和2000ms的区别） 可行性剪枝以及最优性剪枝 这是非常常用的剪枝思路之一，因题目而异，在迭代加深搜索中尤为重要 一般思路：考虑每次解最多变优多少，从当前的层数来看还有多少改进空间，如果已经不可能成为解或更新答案则可以剪枝了 ——A*及IDA*算法：本质就是给搜索加上一个满足相容性的估价函数，然后用估价函数剪枝，理论上很牛B，实际上不常用，因为考场上很难想出满足那么多条件的估价函数，但记得一些常见模型的估价函数还是有价值的。例如15数码的估价函数就可以选择除了0之外每个元素到自己该到的位置的曼哈顿距离之和，因为每次最多使一个数距离减少1，所以这个估价函数是相容的，再例如求k短路的A*算法就是用个堆维护 min{ f(s) + g(s) }估价函数就是从汇点反搜的“反向最短路”的长度。 部分搜索+其他算法 部分搜索+二分图匹配：楼天成《匹配算法在搜索问题中的巧用》 经典例题：mt problem 2 milk（很郁闷的说，只用该算法仍不能ac之） 六、 数论和组合数学 同余方程（组） #define (a mod b)->((a mod b + b) mod b)–>解决负数的问题 解线性同余方程的方法：扩展欧几里德 核心操作： 求ax + by = gcd(a, b) = d 先递归求a’y + b’(x mod y) = d a’y + b’(x - x div y*y) = d