noip算法总结2016

算法总结

一、 动态规划和递推

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

a’y + b’x – b’*(x div y)*y = d b’x + (a’– b’*(x div y))*y = d 有a = b’ b = a’ - b’*(x div y) 边界：y = 0时，a = 1, b = 0

解模方程ax mod 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 mod a1 = b1 x mod a2 = b2

令x = a1*y + b1

则(a1*y + b1) mod a2 = b2 a1*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是上面用扩展欧几里得解出来的东西，成功地等价地把系数消掉了

素数和整除性问题 判断素数的方法：

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!

容斥原理：在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，

人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

容斥原理的一点思考：我们可能会碰到这样一类问题，题目要我们统计一个集合，但这个集合本身是非常难以计算，甚至根本就无法计算时，我们可以考虑把这个集合“设”出来，因为不可计算不代表不可解，有时候我们是可以用容斥原理列出关于这个集合的方程，然后再利用别的信息解出这个集合，从而避免了麻烦的直接计算。 Pólya定理和Burnside引理 内容：

Burnside引理：本质不同的染色方案个数为

∑作用在一个染色方案上的每个置换的不动元素个数/|G| 经典应用：poj 2888有限制的环染色方案统计，循环同构

经典优化：朴素的想法如果是枚举每次跳多少步，然后循环节长度l = 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)

Pólya定理：本质不同的染色方案个数为（m是颜色个数） ∑m^(每种置换中的循环节个数)/|G| 经典应用：HNOI 2009 图同构计数

经典优化：不直接统计原来要统计的东西，转而考虑每个需要被统计的东西会被统计多少次，然后集中处理，通常“本质不同”的被统计的东西相对于原来for的东西是非常少的，所有复杂度会大幅降低，通常的“集中处理”方法是快速幂。

七、 计算几何

计算几何题的最大特点就是编程复杂度极高，大部分题目都是思想简单，实现复杂，考察选手的编程实现能力，而且精度问题也往往需要仔细考虑 基础知识： 旋转、平移

Rotate(var Px,var Py, A) // 将向量(Px, Py)以原点为中心逆时针旋转A（弧度） Qx = Px, Qy = Py Px = 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 + Qx Py = Py + Qy 过两点PA(xA, yA), PB(xB, yB)的直线L: Ax + By + C = 0： BuildLine(PA, PB, L) A = yA – yB B = xB – xA C = xA * yB – yA * xB 求直线L: Ax + By + C = 0上两个不同的点PA(xA, yA), PB(xB, yB) BuildPoints(L, PA, PB) T = A2 + B2 xA = - C * A / T, xB = xA + B yA = - C * B / T, yB = yA - A （由以上两条，可在直线的两种表示方式之间进行转化） 求点P(xP, yP)到直线L(PA-PB)的距离

Distance (P, L) Distance = |(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)的对称点Q GetSymmetryPoint(P, L, Q) PB = PB – PA, P = P – PA A = 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, var P) S = A1 * B2 – A2 * B1 X = C1 * B2 – C2 * B1 Y = 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的相交情况 否则 若P同时在S1、S2上则P为S1、S2的交点 否则没有交点 重要知识点： 凸包

计算几何中最基本也是最重要同时也是非常有用的一个知识点，根据经验，很多几何题都可以不管别的，先求个凸包再说，性质说不定就出来了。

凸包的常用求法是graham扫描法，先把点按横坐标排序，再一边扫描，一边用个栈维护凸包上的点，叉积判断当前栈顶的点是否应该被剔除复杂度是排序的复杂度O(nlogn)

旋转卡壳

其实这是一种思想，一类方法，以维护对踵点为例（对踵点即每个点在凸包上最远点），核心是利用上一次的信息，当i点在凸包上逆时针转动的时候，对踵点j也会在凸包上逆时针转动，而且是单调移动的，也就是说，i+1的对踵点不会比i的对踵点靠前。这样，就可以用个指针维护对踵点，对应维护就可以了，总的复杂度还是O(n)。应用这个思想，可以均摊O(1)地对应维护一些因变量，只要该变量关于自变量的变化过程单调非降。经典例题HNOI2007day1最小矩形覆盖（维护凸包上的向前、向左、向右的最远点）

半平面交（O(nlogn)算法）详细介绍见题解篇

凸多边形的重心、面积，空间多面体的体积：核心是利用叉积

八、 字符串

Kmp：核心是构造next函数，该函数可感性地理解为“失败指针”，即如果在该位匹配失败则指针应该跳到哪里去，然后可以以线性时间复杂度完成单串模式匹配问题

Ac自动机：见数据结构总结，可以做到O(n)的多串模式匹配

后缀数组：本质是给所有后缀排序，核心是height数组，具体介绍见题解篇 一般实现用O(nlogn)的倍增算法

九、 各种怪怪的算法

1. 高斯消元（解xor方程组）

本质是加减消元，每次用一个方程去消掉其他方程中的一个未知元，构造出“阶梯矩阵”，然后反代逐个求解

Xor方程组类似，参考poj 1830 开灯问题题解 2. 拉格朗日逐差法

给你一个多项式函数的前n项，要你求第n+1项 20100902未完成的序列

3. 模拟退火（爬山搜索、随机化调整）

随机调整使解不断变优，有时候需要按一定几率给不优的解一点生存空间，防止当前解没有办法通过调整更优了而陷入死胡同

经典例题：20060423圆桌会议、graceful树的优美标号、CTSC2007激光坦克

4. sg函数与组合游戏

核心就是nim取石子游戏，基本上所有组合游戏都可以转化为nim游戏，通过构造sg函数、分解游戏来解决一类平等博弈问题

核心知识点：SG（i） = { x | not ( x in { SG ( i的后继状态) } ) , x in N )，用中文来讲就是i状态的sg值等于i后继状态的sg函数值中没有出现过的最小自然数（可以为0） 定理：sg( i1 , i2 , i3 , i4 , i5 … , im ) = sg( i1 ) xor sg ( i2) xor sg( i3 ) xor … xor sg( im ) 那么我们就可以预处理出所有 sg( i )，然后快速地判断必胜必败态了 更加详细的介绍：

王晓珂《解析一类组合游戏》

组合游戏略述——浅谈SG游戏的若干拓展及变形 从“k倍动态减法游戏”出发探究一类组合游戏问题 浅谈如何解决不平等博弈问题

5. 线性规划

——半平面交：只能解决两个参量的线性规划问题，具体做法见《计算几何》 ——单纯形法：实现很简单，复杂度在一般情况下非常好，但最坏是O(n!)的，有一定实际价值（其实单纯形还能解决一大堆能划归为线性规划问题的问题，比方说网络流就可以看成是要求满足流量平衡方程和容量限制的一个线性规划问题，），详细介绍及数学证明参考《算法导论》

本文来源：https://www.bwwdw.com/article/1xn.html