《noip算法总结.pdf》由会员分享,可在线阅读,更多相关《noip算法总结.pdf(11页珍藏版)》请在三一文库上搜索。
1、. . 算法总结 一、动态规划和递推 dp 一般的解题步骤: 分析问题, 弄清题意从原问题中抽象出模型根据模型设计状态,要求状态满足 最优子结构和无后效性直接设计状态有难度的话则需要考虑转化模型根据设 计的状态考虑转移如果过不了题目要求的数据范围,则需要考虑优化 由于动态规划涉及的内容太多,只言片语难以讲清,所以附件中放了很多篇关于动态规 划的文章,大部分系原创,并附上了一些经典的论文,主要讲了DP的优化,一些特殊 的状态设计技巧 Dp 和递推没有本质区别,都是用一些状态来描述问题,并记录下一些信息,根据已知 信息推出未知信息,直到得到问题的解 关于 DP的优化有两篇神级论文,放在附件里面了,
2、写的非常好。 二、图论及网络流 最小生成树 :克鲁斯卡尔算法和普利姆算法, 重要性质1:最小生成树上任意两点的路径的最大边最小 重要性质2:最小生成树的多解(方案个数)只与相同权值的的边有关(省队集训 题 生成树计数) 最短路 :spfa 算法、堆 +迪杰斯特拉算法 Spfa算法是基于 松弛技术 的,随机图效果极佳, 最坏(网格图或存在负权环)O(nm), 适用于任意图,能够判断负权环 判负权环的方法:记录每个点当前从原点到它的最短路上边的条数,如果某次更 新后这个条数n-1 则存在负权环 堆+迪杰斯特拉则是用了贪心的思想,不断扩大确定dist的集合,同时更新dist , 如果边权有负值就不能
3、做,复杂度是O(n+m)logn) 的 拓扑排序 :可以 将有向图转化为一个线性的序列,满足一个点所有的前驱结点都出现在 这个点在序列中的位置之前。可以判断这个有向图是否有环 一个简单而实用的扩展:给树做类top 排序, 可以有类似的功能,即每次去掉叶子 结点,将树转化为一个具有拓扑关系的序列 再扩展:树同构判断,可用类top 确定树根是谁,再最小表示法+hash 即可 强连通分量、缩点:tarjan算法 核心是每个点记一个时间戳tii, 另外 lowi表示 i 点能延伸出的搜索树中节点的 tii的最小值, 还要维护个栈记当前路径上的点,lowi初始化为tii,如果搜完i 了, tii=low
4、i则当前栈顶到i 的所有点会在一个强连同分量内。 关键代码: procedure dfs(i:longint); . . var j,k:longint; begin inc(time);tii:=time;vi:=true;lowi:=time; inc(ed);qed:=i;j:=hi; while j10 then begin dec(w(j+1)1); dfs(k); inc(ans0); ansans0:=dirj; end; j:=nextj; end; end; 上面的代码中正边和反边的编号是相邻的,关注inc(ans0)的位置,是在递归调用的 后面 哈密尔顿回路 含义:经过所有
5、点的一个回路 这是个 NPC问题,只有近似算法(暴搜就不提了) 比较好用的是模拟退火 ,以环上相邻两点有边相连的个数作为估价值,随机化调整 二分图匹配 : 最大匹配:匈牙利算法,理论O(nm),实际复杂度好很多 最佳匹配: KM算法,理论O(n2m),实际复杂度同匈牙利一样相当不错 重要性质:最小可行定标和 = 最优匹配 KM 算法中构造了一个非常不错的不等式lxi + lyj = wi,j,有的题目可以利 . . 用这个不等式套KM求出最小可行定标和,如20101112 ti糟糕的传染 网络流 非常神奇的一个东西,数学味有余而图论味不足,通常用来解决限制条件太强,以至于 无论如何都表示不了状
6、态的题,很多经典例题见网络流24 题 通常使用的最大流算法是dinic,代码要背熟,一般能10 分钟之内敲出来 最大流最小割定理 经典模型:最小割模型,最大权闭合图,平面图网络流转最小割 参考神文胡伯涛论文 费用流 相当于网络流的一个强化,能多处理一维信息。具体来讲就是给边多加一个“费用”, 每次增广的费用就是这条增广路的费用之和*流量。 费用流有最小费用最大流和最大费用最大流,用spfa 每次找条最短(长)路增广即可 最小费用最大流还可以用zkw 算法加速,差不多比裸spfa+ 增广快 10 倍的样子(在二 分图网络流上尤为明显),我和盾盾研究了一种更nb 的费用流, 我命名为 “距离标号连
7、 续增广路费用流算法” ,能够秒杀几千个点的稠密随机图,二分图就更不在话下了,速 度几乎达到了dinic的三分之一的样子,而且实现非常简单! 经典例题参考网络流24 题 三、贪心 贪心的关键是找结论,同时给出证明,然后就可以利用这个结论来做题了 当然,考场上对你猜出的结论给出证明通常是很难的,所以用贪心法解题需要丰富的经 验,正确的“题感” ,胆大心细才能搞出来 由于经常要取最优值,所以常常与堆、平衡树等数据结构结合起来 贪心 +其他算法: 由于贪心往往能大幅化简状态,利用问题的某些“单调性”,加上贪心的思想,往往能 是问题大幅简化,从而结合其他算法解决问题 经典例题:田忌赛马,利用贪心来确定
8、状态 四、分治 分而治之的思想在信息学竞赛中是非常重要的,下面主要介绍一下分治的经典应用 二分查找 思想很简单,功能很强大,边界要注意,负数要特判 (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 取模也适用 . . 扩展:求(1 + a + a2 + a3 + + an) mod p的值 O(logn)算法:分治 1 +
9、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 分数规划) 当答案满足在解集空间中连续分布时可以使用二分答案,将最优性问题转化为判定性问 题 ,通常标志:最大值最小 等 差分约束系统中有时也需要二分答案以解决最优性问题,顺便能多得到一个信息 二分答案还有一个优势,那就是已经知道了答案,那就可能
10、可以将一些直接做必须在线 的操作转化为离线操作(也就是说,我可以排序然后判定),诸如要求你判定“第一句 出现矛盾的话”之类的题目(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 胡伯涛论文 树的分治 一般用来解决树上的路径或统计类问题,每次只考虑跟树根有关的信息,然后递归分治 处理 树的分治通常有
11、基于点或基于边的分治,基于点的难合,基于边的复杂度太高 这里只介绍基于点的分治 步骤: 处理跟当前树根有关的信息 重新 计算子树大小 在子树中选择 重心 为根,递归到相应子树处理 因为每次选了重心, 所以递归总共logn 层, 每层 O(n) 的复杂度,总复杂度就是O(nlogn) 更详细严谨的介绍见漆子超论文 二分搜索 直接搜的复杂度是指数级的的话,一般是40 左右的数据量,hash 一半,搜一半 ,搜后 面的时候利用之前的hash 信息合并出原问题的解 而直接搜的复杂度达到阶乘级的话n 一般就不超过20 了,做法一般差不多 经典例题: POI02szy,NOI2001方程的解数 五、搜索
12、. . 作为信息学竞赛中的所谓“万能算法” , 搜索可以说是计算机学科所具有的最大特点了, 自然地, 搜索算法的应用自然也是非常之广泛,除了专门的搜索题,搜索一般可以用来 部分预处理,打表找规律,当然还有骗分 搜索的一般步骤:确定状态选择搜索方式(dfs 、bfs )确定产生式规则开 始搜索 搜索的常见优化方式: 改变状态表示 这个需要根据题目而定,确定一个漂亮的状态表示,可能就有希望转向记忆化了,即使 不行, 搞出一个漂亮的状态表示是解决一道麻烦题的最重要的一步,再者, 调试起来也 会容易许多。 优化搜索顺序 这个优化在多数搜索中能起到摧枯拉朽的提速效果,通常我们选择枝叶较少的儿子先扩 展,
13、例如大名鼎鼎的dancing Links ,除了利用双向十字链表去除冗余状态,每次选择 可扩展数最少的儿子扩展同样给它的神速创造了条件。(poj的一道数独题,我在选择 拿出去扩展的点的那个循环中(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
14、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 实际操作时,只
15、要取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 利用扩展
16、欧几里得可解得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! 容斥
17、原理 :在计数时, 必须注意无一重复,无一遗漏。 为了使重叠部分不被重复计算, 人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含 于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去, 使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理。 容斥原理的一点思考:我们可能会碰到这样一类问题,题目要我们统计一个集合,但这 个集合本身是非常难以计算,甚至根本就无法计算时,我们可以考虑把这个集合“设” 出来 ,因为不可计算不代表不可解,有时候我们是可以用容斥原理列出关于这个集合的 方程 ,然后再利用别的信息解出这个集合,从而避免了麻烦的直接计算。
18、 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(
19、每种置换中的循环节个数)/|G| 经典应用: HNOI 2009 图同构计数 经典优化: 不直接统计原来要统计的东西,转而考虑每个需要被统计的东西会被统计多 少次,然后集中处理,通常“本质不同”的被统计的东西相对于原来for 的东西是非常 少的,所有复杂度会大幅降低,通常的“集中处理”方法是快速幂。 七、计算几何 计算几何题的最大特点就是编程复杂度极高,大部分题目都是思想简单,实现复杂, 考 察选手的编程实现能力,而且精度问题也往往需要仔细考虑 基础知识: 旋转、平移 . . 过两点 PA(xA, yA), PB(xB, yB)的直线 L: Ax + By + C = 0: 求直线 L: Ax
20、 + By + C = 0上两个不同的点PA(xA, yA), PB(xB, yB) (由以上两条,可在直线的两种表示方式之间进行转化) 求点 P(xP, yP)到直线 L(PA-PB) 的距离 过点 P(xP, yP)平行与直线L: (PA PB) 的直线: 求点 P(xP, yP)关于直线L(PA-PB) 的对称点 Q 求两直线L1: A1 x + B1 y + C1 = 0与 L2: A2 x + B2 y + C2 = 0的交点 P(xP, yP) GetSymmetryPoint(P, L, Q) PB = PB PA, P = P PA A = getAngle(P to PB)
21、Rotate(P , 2 * A) Q = P + PA GetLine(P, L) Return Line(P, P + PA PB) Distance (P, L) Distance = |(PA P)(PB P)| / |PA PB| BuildPoints(L, PA, PB) T = A 2 + B2 xA = - C * A / T, xB = xA + B yA = - C * B / T, yB = yA - A BuildLine(PA, PB, L) A = yA yB B = xB xA C = xA * yB yA * xB Rotate(var Px,var Py,
22、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 . . 求两直线L1: (PA PB), L2: (PC PD) 的交点 P(xP, yP) 求两线段S1: (PA PB), S2: (PC PD) 的交点 P(xP, yP) 重要知识点: 凸包 计算几何中最
23、基本也是最重要同时也是非常有用的一个知识点,根据经验, 很多几何题 都可以不管别的,先求个凸包再说,性质说不定就出来了。 凸包的常用求法是graham 扫描法,先把点按横坐标排序,再一边扫描,一边用个栈维 护凸包上的点,叉积判断当前栈顶的点是否应该被剔除复杂度是排序的复杂度 O(nlogn) 旋转卡壳 其实这是一种思想,一类方法, 以维护对踵点为例 (对踵点即每个点在凸包上最远点), 核心是利用上一次的信息,当 i 点在凸包上逆时针转动的时候,对踵点 j 也会在凸包上 逆时针转动,而且是单调移动的,也就是说,i+1 的对踵点不会比i 的对踵点靠前。这 样,就可以用个指针维护对踵点,对应维护就可
24、以了,总的复杂度还是O(n) 。应用这 个思想,可以均摊O(1) 地对应维护一些因变量,只要该变量关于自变量的变化过程单 调非降。经典例题HNOI2007day1最小矩形覆盖(维护凸包上的向前、向左、向右的最 远点) 半平面交 (O(nlogn) 算法)详细介绍见题解篇 凸多边形的重心、面积,空间多面体的体积:核心是利用叉积 八、字符串 Kmp :核心是构造next 函数,该函数可感性地理解为“失败指针”,即如果在该位匹配 失败则指针应该跳到哪里去,然后可以以线性时间复杂度完成单串模式匹配问题 GetIntersection(S1,S2, var P) 检查直线L1: (PA PB), L2:
25、 (PC PD)的交点 P(xP , yP) 若 L1, L2重合,则直接在直线上判断S1、 S2的相交情况 否则 若 P同时在 S1、S2上则 P为 S1、S2的交点 否则没有交点 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 . . Ac 自动机 :见数据结构总结,可以做到O(n) 的多串模式匹配 后缀数组 :本质是给所有后
26、缀排序,核心是height数组,具体介绍见题解篇 一般实现用O(nlogn) 的倍增算法 九、各种怪怪的算法 1.高斯消元(解xor 方程组) 本质是加减消元,每次用一个方程去消掉其他方程中的一个未知元,构造出“阶梯 矩阵” ,然后反代逐个求解 Xor 方程组类似,参考poj 1830 开灯问题题解 2.拉格朗日逐差法 给你一个多项式函数的前n 项,要你求第n+1项 20100902 未完成的序列 3.模拟退火(爬山搜索、随机化调整) 随机调整使解不断变优,有时候需要按一定几率给不优的解一点生存空间,防止当 前解没有办法通过调整更优了而陷入死胡同 经典例题: 20060423 圆桌会议、 gr
27、aceful树的优美标号、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.31doc.com/p-5012206.html