算法分块总结为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。

算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。

另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。

图论模型的应用分层图思想的应用：用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。

重要的是，新建立的图有一些很好的性质：由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。

由于层之间的相似性，很多计算结果都是相同的。

所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。

如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。

层之间是拓扑有序的。

这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。

这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。

二分图最大及完备匹配的应用：ZOJ place the robots:二分图最优匹配的应用：最大网络流算法的应用：典型应用就求图的最小割。

最小费用最大流的应用：容量有上下界的最大流的应用：欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。

最小生成树：求最小生成树，比较常用的算法有Prim算法和Kruskal算法。

前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。

最小K度限制生成树：抽象成数学模型就是：设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。

首先考虑边界情况。

先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中dT(v0)≥m。

也就是说，当k<m时，问题无解。

再根据上述定理，得出算法的框架：下面分别考虑每一步首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。

接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。

于是，我们就得到了一个m 度限制生成树，不难证明，这就是最小m度限制生成树。

这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。

假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？在原先的树中加入一条与v0相关联的边后，必定形成一个环。

若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。

删去的边的权值越大，则所得到的生成树的权值和就越小。

动态规划就有了用武之地。

设Best(v)为路径v0—v上与v0无关联且权值最大的边。

定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞| (v0,v’)∈E(T)。

状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。

故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。

1 先求出最小m度限制生成树；2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。

加边和去边过程，利用动态规划优化特别值得注意。

次小生成树：加边和去边很值得注意。

每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。

具体做法：首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。

如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。

最短路径的应用：Dijkstra 算法应用：Folyed 算法应用：Bellman-Ford 算法的应用：差分约束系统的应用：搜索算法搜索对象和搜索顺序的选取最为重要。

一些麻烦题，要注意利用数据有序化，要找一个较优的搜索出发点，凡是能用高效算法的地方尽量争取用高效算法。

基本的递归回溯深搜，记忆化搜索，注意剪枝：广搜（BFS）的应用：枚举思想的应用：ZOJ 1252 island of logicA*算法的应用：IDA*算法的应用，以及跳跃式搜索探索：限深搜索，限次：迭代加深搜索：部分搜索+高效算法（比如二分匹配，动态规划）：ZOJ milk bottle data:剪枝优化探索：可行性剪枝，最优性剪枝，调整搜索顺序是常用的优化手段。

动态规划动态规划最重要的就是状态的选取，以及状态转移方程，另外还要考虑高效的预处理（以便更好更快的实现状态转移）。

最常用的思想就是用枚举最后一次操作。

状态压缩DP，又叫带集合的动态规划：题目特点是有一维的维数特别小。

类似TSP问题的DP：状态划分比较困难的题目：树形DP：四边形不等式的应用探索：四边形不等式通常应用是把O(n^3)复杂度O(n^2)高档数据结构的应用并查集的应用：巧用并查集中的路径压缩思想：堆的利用：线段树的应用：总结用线段树解题的方法根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。

建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等树的每个节点根据题目所需，设置变量记录要求的值用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。

利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。

在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。

Trie的应用：；Trie图的应用探索：后缀数组的应用研究：在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树了解得比较多，关于后缀数组则很少见于国内的资料。

其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。

树状数组的应用探索：；计算几何掌握基本算法的实现。

凸包的应用：；半平面交算法的应用：；几何+模拟类题目：几何设计好算法，模拟控制好精度。

扫描法：；转化法：ZOJ 1606 将求所围的格子数，巧妙的转化为求多边形的面积。

离散法思想的应用：；经典算法：找平面上的最近点对。

贪心矩形切割二分思想应用活用经典算法利用归并排序算法思想求数列的逆序对数：利用快速排序算法思想，查询N个数中的第K小数：博弈问题博弈类题目通常用三类解法：第一类推结论；第二类递推，找N位置，P位置；第三类SG函数的应用。

第四类极大极小法，甚至配合上αβ剪枝。

最难掌握的就是第四类极大极小法。

第一类：推结论。

典型题目：第二类：递推。

典型题目：比如有向无环图类型的博弈。

在一个有向图中，我们把选手I有必胜策略的初始位置称为N位置(Next player winning)，其余的位置被称为P位置(Previous player winning)。

很显然，P位置和N位置应该具有如下性质：1．所有的结束位置都是P位置。

2．对于每一个N位置，至少存在一种移动可以将棋子移动到一个P位置。

3．对于每一个P位置，它的每一种移动都会将棋子移到一个N位置。

这样，获胜的策略就是每次都把棋子移动到一个P位置，因为在一个P位置，你的对手只能将棋子移动到一个N位置，然后你总有一种方法再把棋子移动到一个P位置。

一直这样移动，最后你一定会将棋子移动到一个结束位置（结束位置是P位置），这时你的对手将无法在移动棋子，你便赢得了胜利。

与此同时，得到了这些性质，我们便很容易通过倒退的方法求出哪些位置是P位置，哪些位置是N位置，具体的算法为：1．将所有的结束位置标为P位置。

2．将所有能一步到达P位置的点标为N位置。

3．找出所有只能到达N位置的点，将它们标为P位置。

4．如果在第三步中没有找到新的被标为P位置的点，则算法结束，否则转到步骤2。

这样我们便确定了所有位置，对于题目给出的任一初始位置，我们都能够很快确定出是选手I获胜还是选手II获胜了。

第三类：SG函数的应用。

关于SG函数的基本知识：对于一个有向图(X, F)来说，SG函数g是一个在X上的函数，并且它返回一个非负整数值，具体定义为nyng≥=对于所有≠g∈x(x)()}y(,0)Fmin{1．对于所有的结束位置x，g(x) = 0。

2．对于每一个g(x) ≠ 0的位置x，在它可以一步到达的位置中至少存在一个位置y使得g(y) = 0。

3．对于每一个g(x) ＝0的位置x，所有可以由它一步到达的位置y都有g(y)≠0。

定理如果g(x i)是第i个有向图的SG函数值，i = 1,…,n，那么在由这n个有向图组成的状态的SG函数值g(x1,…x n) = g(x1) xor g(x2) xor … xor g(x n)第四类：极大极小法。

典型题目：ZOJ 1155：Triangle WarZOJ 1993：A Number Game矩阵妙用矩阵最基本的妙用就是利用快速乘法O（logn）来求解递推关系（最基本的就是求Fibonacci 数列的某项）和各种图形变换，以及利用高斯消元法变成阶梯矩阵。

典型题目：数学模型举例向量思想的应用：UVA 10089：注意降维和向量的规范化；利用复数思想进行向量旋转。

递推UV A 10253：数代集合数代集合的思想：ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题：Intuitionistic Logic用枚举+数代集合思想优化，注意到题中有一句话："You may assume that the number H = |H| of elements of H doesn't exceed 100"，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。