noip算法总结2016

1、算法总结一、 动态规划和递推dp一般的解题步骤：分析问题，弄清题意从原问题中抽象出模型根据模型设计状态，要求状态满足最优子结构和无后效性直接设计状态有难度的话则需要考虑转化模型根据设计的状态考虑转移如果过不了题目要求的数据范围，则需要考虑优化由于动态规划涉及的内容太多，只言片语难以讲清，所以附件中放了很多篇关于动态规划的文章，大部分系原创，并附上了一些经典的论文，主要讲了DP的优化，一些特殊的状态设计技巧Dp和递推没有本质区别，都是用一些状态来描述问题，并记录下一些信息，根据已知信息推出未知信息，直到得到问题的解关于DP的优化有两篇神级论文，放在附件里面了，写的非常好。二、 图论及网络流最小生

2、成树：克鲁斯卡尔算法和普利姆算法，重要性质1：最小生成树上任意两点的路径的最大边最小重要性质2：最小生成树的多解（方案个数）只与相同权值的的边有关（省队集训题 生成树计数）最短路：spfa算法、堆+迪杰斯特拉算法 Spfa算法是基于松弛技术的，随机图效果极佳，最坏（网格图或存在负权环）O(nm)，适用于任意图，能够判断负权环 判负权环的方法：记录每个点当前从原点到它的最短路上边的条数，如果某次更新后这个条数n-1则存在负权环 堆+迪杰斯特拉则是用了贪心的思想，不断扩大确定dist的集合，同时更新dist，如果边权有负值就不能做，复杂度是O(n+m)logn)的拓扑排序：可以将有向图转化为一个线

3、性的序列，满足一个点所有的前驱结点都出现在这个点在序列中的位置之前。可以判断这个有向图是否有环一个简单而实用的扩展：给树做类top排序，可以有类似的功能，即每次去掉叶子结点，将树转化为一个具有拓扑关系的序列再扩展：树同构判断，可用类top确定树根是谁，再最小表示法+hash即可强连通分量、缩点：tarjan算法核心是每个点记一个时间戳tii, 另外lowi表示i点能延伸出的搜索树中节点的tii的最小值，还要维护个栈记当前路径上的点，lowi初始化为tii，如果搜完i了，tii=lowi则当前栈顶到i的所有点会在一个强连同分量内。关键代码：procedure dfs(i:longint);var

4、 j,k:longint;begin inc(time);tii:=time;vi:=true;lowi:=time; inc(ed);qed:=i;j:=hi; while j0 do begin k:=pointj; if tik=0 then begin dfs(k);if lowklowi then lowi:=lowk; end else if vk then if tiklowi then lowi:=tik; j:=nextj; end; if tii=lowi then begin inc(num);k:=0; repeat j:=qed;fj:=num;vj:=false;k

5、:=k+aj; if bj then barnum:=true; dec(ed); until qed+1=i; vlnum:=k; end;end; 欧拉路：含义：不重复地经过每条边的一条路径，如果起点和终点相同则叫“欧拉回路”，起点和终点不同叫“欧拉路径”存在欧拉路径的条件：至多两个点的度为基数（回路则要求全都为偶数）实现：（非常简单）一顿乱dfs就可以了，每次退栈的再将这条边加入答案序列procedure dfs(i:longint);var j,k:longint;begin j:=hi; while j0 do begin k:=pointj; if w(j+1)10 then be

6、gin dec(w(j+1)1); dfs(k); inc(ans0); ansans0:=dirj; end; j:=nextj; end;end;上面的代码中正边和反边的编号是相邻的，关注inc(ans0)的位置，是在递归调用的后面哈密尔顿回路含义：经过所有点的一个回路这是个NPC问题，只有近似算法（暴搜就不提了）比较好用的是模拟退火，以环上相邻两点有边相连的个数作为估价值，随机化调整二分图匹配：最大匹配：匈牙利算法，理论O(nm)，实际复杂度好很多最佳匹配：KM算法，理论O(n2m)，实际复杂度同匈牙利一样相当不错重要性质：最小可行定标和 = 最优匹配 KM算法中构造了一个非常不错的不等

7、式lxi + lyj = wi,j，有的题目可以利用这个不等式套KM求出最小可行定标和，如20101112 ti糟糕的传染网络流非常神奇的一个东西，数学味有余而图论味不足，通常用来解决限制条件太强，以至于无论如何都表示不了状态的题，很多经典例题见网络流24题通常使用的最大流算法是dinic，代码要背熟，一般能10分钟之内敲出来最大流最小割定理经典模型：最小割模型，最大权闭合图，平面图网络流转最小割参考神文胡伯涛论文费用流相当于网络流的一个强化，能多处理一维信息。具体来讲就是给边多加一个“费用”，每次增广的费用就是这条增广路的费用之和*流量。费用流有最小费用最大流和最大费用最大流，用spfa每次

8、找条最短（长）路增广即可最小费用最大流还可以用zkw算法加速，差不多比裸spfa+增广快10倍的样子（在二分图网络流上尤为明显），我和盾盾研究了一种更nb的费用流，我命名为“距离标号连续增广路费用流算法”，能够秒杀几千个点的稠密随机图，二分图就更不在话下了，速度几乎达到了dinic的三分之一的样子，而且实现非常简单！经典例题参考网络流24题三、 贪心贪心的关键是找结论，同时给出证明，然后就可以利用这个结论来做题了当然，考场上对你猜出的结论给出证明通常是很难的，所以用贪心法解题需要丰富的经验，正确的“题感”，胆大心细才能搞出来由于经常要取最优值，所以常常与堆、平衡树等数据结构结合起来贪心+其他算

9、法：由于贪心往往能大幅化简状态，利用问题的某些“单调性”，加上贪心的思想，往往能是问题大幅简化，从而结合其他算法解决问题经典例题：田忌赛马，利用贪心来确定状态四、 分治分而治之的思想在信息学竞赛中是非常重要的，下面主要介绍一下分治的经典应用二分查找思想很简单，功能很强大，边界要注意，负数要特判（NOI2010 PIANO）在非负数范围内的二分一般写法如果是l := mid - 1或+ 1则mid := (l + r) div 2而如果是r := mid - 1 或 +1则 mid := (l + r + 1) div 2快速幂ab = (a(b div 2)2 + ord(odd(b)*a取模

10、也适用扩展：求(1 + a + a2 + a3 + + an) mod p的值 O(logn)算法：分治 1 + a + a2 + a3 + + an = (1 + a + a2 + a3 + + a(n div 2)*a(n div 2) + ord(odd(n)*an 两个快速幂可以合到一起写快速排序，归并排序任何一本算法书上都会讲的，这里就略过了，值得一提的是快排记得加上随机化k := arandom(r - l + 1) + l二分答案（0-1分数规划）当答案满足在解集空间中连续分布时可以使用二分答案，将最优性问题转化为判定性问题，通常标志：最大值最小等差分约束系统中有时也需要二分答案

11、以解决最优性问题，顺便能多得到一个信息二分答案还有一个优势，那就是已经知道了答案，那就可能可以将一些直接做必须在线的操作转化为离线操作（也就是说，我可以排序然后判定），诸如要求你判定“第一句出现矛盾的话”之类的题目（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胡伯涛论文树的分治一般用来解决树上的路径或统计类问题，每次只考虑跟

12、树根有关的信息，然后递归分治处理树的分治通常有基于点或基于边的分治，基于点的难合，基于边的复杂度太高这里只介绍基于点的分治步骤： 处理跟当前树根有关的信息 重新计算子树大小 在子树中选择重心为根，递归到相应子树处理因为每次选了重心，所以递归总共logn层，每层O(n)的复杂度，总复杂度就是O(nlogn)更详细严谨的介绍见漆子超论文二分搜索直接搜的复杂度是指数级的的话，一般是40左右的数据量，hash一半，搜一半，搜后面的时候利用之前的hash信息合并出原问题的解而直接搜的复杂度达到阶乘级的话n一般就不超过20了，做法一般差不多经典例题：POI02szy，NOI2001方程的解数五、 搜索作为

13、信息学竞赛中的所谓“万能算法”，搜索可以说是计算机学科所具有的最大特点了，自然地，搜索算法的应用自然也是非常之广泛，除了专门的搜索题，搜索一般可以用来部分预处理，打表找规律，当然还有骗分搜索的一般步骤：确定状态选择搜索方式（dfs、bfs）确定产生式规则开始搜索搜索的常见优化方式：改变状态表示这个需要根据题目而定，确定一个漂亮的状态表示，可能就有希望转向记忆化了，即使不行，搞出一个漂亮的状态表示是解决一道麻烦题的最重要的一步，再者，调试起来也会容易许多。优化搜索顺序这个优化在多数搜索中能起到摧枯拉朽的提速效果，通常我们选择枝叶较少的儿子先扩展，例如大名鼎鼎的dancing Links，除了利用

14、双向十字链表去除冗余状态，每次选择可扩展数最少的儿子扩展同样给它的神速创造了条件。（poj的一道数独题，我在选择拿出去扩展的点的那个循环中和(a mod b + b) mod b) 解决负数的问题解线性同余方程的方法：扩展欧几里德核心操作：求ax + by = gcd(a, b) = d先递归求ay + b(x mod y) = day + b(x - x div y*y) = day + bx b*(x div y)*y = dbx + (a b*(x div y)*y = d有a = b b = a - b*(x div y)边界：y = 0时，a = 1, b = 0解模方程ax mod

15、 b = c等价于解出ax + by = c无解的条件c mod gcd(a,b) 0求解ax +by = c令d = gcd(a, b), c = c div d求解原方程等价于求解ax + by = d, 求完后将答案乘上c即可求ax mod b = c的最小正解的方法先求出一组ax + by = c的可行解x,y（实际上我们只要x）由a(x + k*b) mod b = c所以我们可以通过给x加上若干倍b使得a恰好大于0实际操作时，只要取x = x mod b就可以了，如果x 0 则 x := x + b解同余方程组的方法：每次合并两个模方程，合到最后就能够解出来了核心操作：合并x mo

16、d a1 = b1x mod a2 = b2令x = a1*y + b1则(a1*y + b1) mod a2 = b2a1*y mod a2 = b2 - b1可以用扩展欧几里得求出y,从而求出最小正x同时满足两个方程合并之后变成 x mod lcm(a1, a2) = x mod lcm(a1, a2)以此合并求解即可将带系数的方程化为不带系数的方法：ax mod b = c ax + by = c 利用扩展欧几里得可解得x, y那么x的通解可以表示为x + k*(b div gcd(a, b)因此，原方程等价于x mod (b div gcd(a, b) = x, x是新的未知数,x是上

17、面用扩展欧几里得解出来的东西，成功地等价地把系数消掉了素数和整除性问题判断素数的方法：O(sqrt(n):从2枚举到sqrt(n)逐一判断即可 均摊O(ln(n)的方法：筛选法 利用费马小定理可以O(k*logn)地检验质数，但有一定概率出错（k是检验次数）组合计数类问题基本：排列和组合：C(N,M) = N!/(M!(N-M)!) P(N,M) = N!M!容斥原理：在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的

18、结果既无遗漏又无重复，这种计数的方法称为容斥原理。容斥原理的一点思考：我们可能会碰到这样一类问题，题目要我们统计一个集合，但这个集合本身是非常难以计算，甚至根本就无法计算时，我们可以考虑把这个集合“设”出来，因为不可计算不代表不可解，有时候我们是可以用容斥原理列出关于这个集合的方程，然后再利用别的信息解出这个集合，从而避免了麻烦的直接计算。Plya定理和Burnside引理内容：Burnside引理：本质不同的染色方案个数为作用在一个染色方案上的每个置换的不动元素个数/|G|经典应用：poj 2888有限制的环染色方案统计，循环同构经典优化：朴素的想法如果是枚举每次跳多少步，然后循环节长度l

19、= gcd(i, n)，那就可以改为枚举l，然后用欧拉函数求出满足gcd(i, n) = l的i的个数方法： L = gcd(i, n) Gcd(i/l, n/l) = 1 又i/l = n/l，所以满足条件的i的个数= phi(n/l)Plya定理：本质不同的染色方案个数为（m是颜色个数） m(每种置换中的循环节个数)/|G|经典应用：HNOI 2009 图同构计数经典优化：不直接统计原来要统计的东西，转而考虑每个需要被统计的东西会被统计多少次，然后集中处理，通常“本质不同”的被统计的东西相对于原来for的东西是非常少的，所有复杂度会大幅降低，通常的“集中处理”方法是快速幂。七、 计算几何计

20、算几何题的最大特点就是编程复杂度极高，大部分题目都是思想简单，实现复杂，考察选手的编程实现能力，而且精度问题也往往需要仔细考虑基础知识：旋转、平移Rotate(var Px,var Py, A) / 将向量(Px, Py)以原点为中心逆时针旋转A（弧度）Qx = Px, Qy = PyPx = Qx * cos(A) Qy * sin(A)Py = Qx * sin(A) + Qy * cos(A)Move(var Px, var Py, Qx, Qy) / 将向量(Px, Py)按照(Qx, Qy)平移Px = Px + QxPy = Py + Qy过两点PA(xA, yA), PB(xB,

21、 yB)的直线L: Ax + By + C = 0：BuildLine(PA, PB, L)A = yA yBB = xB xAC = xA * yB yA * xB求直线L: Ax + By + C = 0上两个不同的点PA(xA, yA), PB(xB, yB)BuildPoints(L, PA, PB)T = A2 + B2xA = - C * A / T, xB = xA + ByA = - C * B / T, yB = yA - A（由以上两条，可在直线的两种表示方式之间进行转化）求点P(xP, yP)到直线L(PA-PB)的距离Distance (P, L)Distance =

22、|(PA P)(PB P)| / |PA PB|过点P(xP, yP)平行与直线L: (PA PB)的直线：GetLine(P, L)Return Line(P, P + PA PB)求点P(xP, yP)关于直线L(PA-PB)的对称点QGetSymmetryPoint(P, L, Q)PB = PB PA, P = P PAA = getAngle(P to PB)Rotate(P, 2 * A)Q = P + PA求两直线L1: A1 x + B1 y + C1 = 0与L2: A2 x + B2 y + C2 = 0的交点P(xP, yP)GetIntersection(L1, L2,

23、 var P)S = A1 * B2 A2 * B1X = C1 * B2 C2 * B1Y = A1 * C2 A2 * C1若S = 0若X = Y = 0，则L1、L2重合；否则无交点否则xP = -X / S, yP = -Y / S求两直线L1: (PA PB), L2: (PC PD)的交点P(xP, yP)求两线段S1: (PA PB), S2: (PC PD)的交点P(xP, yP)GetIntersection(S1,S2, var P)检查直线L1: (PA PB), L2: (PC PD)的交点P(xP, yP)若L1, L2重合，则直接在直线上判断S1、S2的相交情况否

24、则若P同时在S1、S2上则P为S1、S2的交点否则没有交点重要知识点：凸包计算几何中最基本也是最重要同时也是非常有用的一个知识点，根据经验，很多几何题都可以不管别的，先求个凸包再说，性质说不定就出来了。凸包的常用求法是graham扫描法，先把点按横坐标排序，再一边扫描，一边用个栈维护凸包上的点，叉积判断当前栈顶的点是否应该被剔除复杂度是排序的复杂度O(nlogn)旋转卡壳其实这是一种思想，一类方法，以维护对踵点为例（对踵点即每个点在凸包上最远点），核心是利用上一次的信息，当i点在凸包上逆时针转动的时候，对踵点j也会在凸包上逆时针转动，而且是单调移动的，也就是说，i+1的对踵点不会比i的对踵点靠

25、前。这样，就可以用个指针维护对踵点，对应维护就可以了，总的复杂度还是O(n)。应用这个思想，可以均摊O(1)地对应维护一些因变量，只要该变量关于自变量的变化过程单调非降。经典例题HNOI2007day1最小矩形覆盖（维护凸包上的向前、向左、向右的最远点）半平面交（O(nlogn)算法）详细介绍见题解篇凸多边形的重心、面积，空间多面体的体积：核心是利用叉积八、 字符串Kmp：核心是构造next函数，该函数可感性地理解为“失败指针”，即如果在该位匹配失败则指针应该跳到哪里去，然后可以以线性时间复杂度完成单串模式匹配问题Ac自动机：见数据结构总结，可以做到O(n)的多串模式匹配后缀数组：本质是给所有后缀排序，核