挑战程序设计竞赛—知识总结

2023年8月1日发(作者：)

挑战程序设计竞赛—知识总结准备篇1.5 运⾏时间概述编写的⽬的是⾯向ACM程序设计竞赛，不可避免的要涉及复杂度和运⾏时间的问题，本节给出了解决问题算法选择的依据。假设题⽬描述中给出的限制条件为，针对O(n2)的算法将会执⾏⼤于106次。如果时间限制是1s，则有下述结论：

上述结论表明，针对O(n2)的算法，n<=1000可以在时限内解决，但是如果n<=10000，则超时的可能性⾮常⼤，这就启⽰我们要寻找新的算法降低算法复杂度，否则将不能AC。1.6 三⾓形给定N个边，任选三边构成三⾓形，输出最⼤的周长。通过三层循环可以解决，但是复杂度为O(n3)。如果利⽤3.2节的折半枚举技巧可以在O(n2logn)的时间内解决：⾸先将所有的边排序，复杂度为O(nlogn)；然后两层循环得到任意两条边的距离之和；最后⼆分查找，找到能构成三⾓形的最⼤边。⽂中说还有O(nlogn)的算法，我不知道，希望有⼈能告诉我。折半枚举这个技巧⾮常有⽤，可以解决⼀⼤类问题，抽签问题即是⼀个⾮常好的例⼦。初级篇2.1 穷竭搜索1. 基础栈的头⽂件，常⽤⽅法：push，top，pop；队列的头⽂件，常⽤⽅法：push，front，pop。2. 深搜部分和问题：给定n个数，选出若各个其和是否为k。代码：int a[MAX_N];int n,k;

//已经从前i项得到了sum，然后对i项之和的进⾏分⽀bool dfs(int i,int sum){ if(i==n) return sum==k;

if(dfs(i+1,sum)) return true; if(dfs(i+1,sum+a[i])) return true;

return false;}

void solve() { if(dfs(0,0)) printf(“Yesn”);

else printf(“Non”);}该代码具有普遍性，能解决⾮常多的问题，如果不考虑复杂度01背包也可以按照这个思路解决。深搜按照回溯的策略去遍历问题的解空间，部分和问题和01背包问题的解都是原数组的⼦集，所以其解空间构成了⼀个⼆叉树。除了⼆叉树形式的解空间，还有很多问题的解空间是k叉树，例如⼋皇后问题，每⼀⾏的皇后有⼋个位置可以选择，解空间构成了⼀个⼋叉树。不管是⼏叉树，代码结构类似。此外《编程之美》第3.2节的电话号码对应英语单词也属于此类结构，只不过每⼀层的叉树不⼀样。解空间是k叉树时，遍历的复杂度是O(kn)。由于复杂度⾮常⾼，在遍历的过程中往往伴随着解空间的剪枝。还有很多问题的解空间不是原数据的⼦集，⽽是⼀个排列，此时解空间是⼀个排列树。最具代表性的⼀个例⼦是旅⾏商问题，其每⼀层的树节点都在逐次减⼀，所以其复杂度是O(n!)。还有⼀些问题不属于上⾯的两类情况，例如n皇后问题，其复杂度变为O(nn)。还有⼀个例⼦是《编程之美》1.3节的烙饼排序问题，也是⼀个复杂度变为O(nn)的深搜问题。剑指offer⾯试题12的打印1到最⼤n位数也可以通过每次都是O(n)复杂度的深搜完成。不管属于哪⼀类，它们的代码结构⽐较类似：dfs(int i){ //1 输出结果 if(i==n) printf();

//2 剪枝

//3遍历下⼀层 for(int j=0;j=w[i];j--){ dp[j]=max(dp[j], dp [j-w[i]]+v[i]); } } printf(“%dn”,dp[W]);}完全背包问题的空间优化代码：int dp[MAX_W+1];void solve(){ for(int i=0;i

CompletePack(weight,value) for w from weight to W do f [w] = max(f [w], f [w-weight] + value)根据上⾯两个背包问题的伪代码，多重背包问题就可以按照下⾯的思路解决：MultiplePack(weight; value; amount)if weight * amount > W then CompletePack(cost; weight) returnk=1 while k < amount do ZeroOnePack(k*weight; k*value) amount=amount-k k=k*2ZeroOnePack(amount*weight; amount*value)上⾯解决多重背包的⽅法是将其每⼀个物品分别分解成完全背包或者是01背包问题来解决，虽然不是最低复杂度，但是效率也很⾼。将上述三种背包混合就得到混合背包问题，伪代码为：for i from 1 to N do if 第i件物品属于01背包 then ZeroOnePack(w[i]; v[i]) else if 第i件物品属于完全背包 then CompletePack(w[i]; v[i]) else if 第i件物品属于多重背包 then MultiplePack(w[i]; v[i]; m[i])关于初等背包的另⼀个需要注意问题是初始化问题。有的题⽬要求“恰好装满背包”时的最优解，有的题⽬则并没有要求必须把背包装满。⼀种区别这两种问法的实现⽅法是在初始化的时候有所不同。如果是第⼀种问法，要求恰好装满背包，那么在初始化时除了f[0]为0，其它f[1..W]均设为-∞，这样就可以保证最终得到的f[N]是⼀种恰好装满背包的最优解。如果并没有要求必须把背包装满，⽽是只希望价格尽量⼤，初始化时应该将f[0..W]全部设为0。⼀个“恰好装满背包”的实例是编程之美1.6节的饮料供应问题。关于背包问题的⾼级主题和详细介绍⼤家可以看：

。

2.4 数据结构1. 基本结构STL中的优先队列为priority_queue，头⽂件为，常⽤操作为：push，top，pop，empty，size。该优先队列默认pop的是最⼤值，如果想pop最⼩值（最⼩堆），则需要指明⽐较函数：priority_queue,greater> que;STL中实现⼆叉搜索树的容器有set和map，头⽂件分别为和

void init(int n){ for(int i=0;i

int find(int e){ int j=e; while(!root[j]) j=parent[j];

int f=e; while(f!=e) { int pf=parent[f]; parent[f]=j; f=pf; }

return j;}

void union(int i,int j) { if(parent[i]

root[i]=false; parent[i]=j; } else{parent[i]+=parent[j]; root[j]=false; parent[j]=i; }}并查集的⼀个最典型应⽤是Kruskal算法解决最⼩⽣成树（MST）问题。2.5 图1. 图着⾊问题书中介绍了⼆分图的判定问题，代码如下：vector G[MAX_V];//图 int V; int color[MAX_V];

bool dfs(int v,int c){ color[v]=c; for(int i=0;i

void solve(){ for(int i=0;i P;//保存的结果，first为最短距离，second为相应顶点

int V;vector G[MAX_V];int d[MAX_V];

void dijkstra(int s){ priority_queue,greater

> que; fill(d,d+V,INF); d[s]=0; (P(0,s));

while(!()){ P p=(); (); int v=; for(int i=0;id[v]+){ d[]=d[v]+; (P(d[],)); } } }}Prim算法是求MST，它和Dijkstra算法⼗分相似，都是从某个顶点出发，不断添加边的算法。2.6 简单的数学问题1. 埃⽒筛法判断⼀个数是否是素数，只需要判断⼩于等于n的开⽅的整数能否整除n即可。如果需要求所有⼩于n的素数，则需要埃⽒筛法。思想很简单，代码如下：int prime[MAX_N];bool is_prime[MAX_N+1];

int sieve(int n){ int p=0; for(int i=0;i<=n;i++) is_prime[i]=true; is_prime[0]=is_prime[1]=false; for(int i=2;i<=n;i++){ if(is_prime[i]){ prime[p++]=I; for(int j=2*i;j<=n;j+=i) is_prime[j]=false; } } return p;}快速幂运算在求xn时，我们通过将n按照⼆进制分解，可以获得⼀个求幂的快速算法：typedef long long ll;

ll mod_pow(ll x,ll n,ll mod){ ll res=1; while(n>0){ if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res;}求幂的快速算法在求矩阵的幂时也可以采⽤。总体上，第⼆章的难度中等偏上，只要能多思考，绝⼤多数问题都能看懂。中级篇3.1 ⼆分搜索通过该节让我真切明⽩⼆分搜索的应⽤价值远远⼤于其看上去的样⼦，所以该节内容值得仔细研究。另⼀⽅⾯，⼆分搜索的难度也不像其看上去的样⼦，⽹上说“80%的程序员写不对⼆分查找”并⾮谣⾔。1. lower_bound 给定⼀个单调不下降数列和⼀个数k，求满⾜ai>=k的最⼩i。 ⾸先看⼀下第n/2个值。如果a[n/2]>=k，则可以知道解的范围不⼤于n/2。反之，如果a[n/2]

void lower_bound(){ int lb=-1,ub=n;

while(ub-lb>1){ int mid=(lb+ub)/2; if(a[mid]>=k) ub=mid; else lb=mid; } printf(“%dn”,ub);}上述算法不仅能找到要寻找的值，⽽且返回的是⼀系列值中的最⼩值，可以⽤来求解“满⾜某个条件C(x)的最⼩的x”问题。STL将上述代码以lower_bound函数的形式实现，不过需要注意的是该函数返回的是⼀个位置指针，可以通过解引⽤来获取元素值，还可以通过与数组起点相减获得位置下标。与此类似的还有函数upper_bound函数，它返回ai>k的最⼩i。利⽤这两个函数我们就可以求数组中元素k出现的次数： upper_bound(a,a+n,k)-lower_bound(a,a+n,k); 后⾯三个⼩节讲了⼆分搜索的应⽤，它们都依赖下⾯的基本原理：问题的正确解为X，当给定的解⼩于等于X时，都能满⾜要求；当给定的解⼤于X时，解不满⾜要求。也即解空间以X为分界，分成正确的和错误的两个⼦集。解题流程都是：判断⼀个给定的数x是否满⾜条件，若满⾜条件就放⼤x，否则就减⼩x，通过不停地减⼩搜索区间找到最后的值。对于x是浮点数的情况，可以通过设定⼀个遍历次数的上届完成⼆分搜索。由于⼆分搜索每次将区间减⼩⼀半，所以100次遍历即可以将区间减到任意精度。对于x是整数的情况，可以简单的选取lb为问题的解。这是因为lb总是问题的解，ub总不是问题的解，当两者距离等于1时，搜索结束。此时lb还是问题的解，ub依旧不是问题的解。此外，前⾯介绍的图最⼩着⾊问题也是⽤了⼆分搜索的思想。3.2 常⽤技巧（⼀）1. 尺取法 给定⼀个长度为n的正整数数列，以及整数S。求总和不⼩于S的连续⼦序列的长度最⼩值。 可以按照如下⽅法解决该问题：（1） 设置两个指针s和t，⼀开始都指向数列第⼀个元素，此外sum=0,res=0；（2） 只要sum=S，更新res=min(res,t-s)；（4） 将sum减去⼀个元素，s加1，执⾏（2）。上述流程反复地推进区间的开头和末尾，来求取满⾜条件的最⼩区间。代码如下：void solve(){ int res=n+1; int s=0,t=0,sum=0; for(;;){ while(tn) res=0;}尺取法在别的地⽅⼜被称为滑动窗⼝或者蠕⾍算法，应⽤很⼴。让⼈看不明⽩的编程之美3.5节最短摘要的⽣成也是采⽤了此法。2. 位运算 常⽤集合运算的位运算：（1） 空集：0；（2） 只含有第i个元素的集合：1<>i&1);（5） 向集合加⼊第i个元素：S|1<>1)|y;}3.5 ⽹络流 很多问题都可以转⾏为⼆分图匹配，所以⼆分图匹配的匈⽛利算法要掌握。在⽹络流中有四个概念需要强调：匹配：在G中两两没有公共端点的边集合M边覆盖：G中的任意顶点都⾄少是F中某条边的端点的边集合F独⽴集：在G中两两互不相连的顶点集合S顶点覆盖：G中的任意边都有⾄少⼀个端点属于S的顶点集合S 以上四个概念满⾜如下关系：对于不存在孤⽴点的图，|最⼤匹配|+|最⼩边覆盖|=|V||最⼤独⽴集|+|最⼩顶点覆盖|=|V| 利⽤这些关系，对于最⼤匹配和最⼩边覆盖，最⼤独⽴集和最⼩顶点覆盖，只要能求解其中⼀个，另⼀个问题也就得到解决。最⼤独⽴集问题是NP复杂的问题，但是针对⼆分图，有如下等式成⽴： |最⼤匹配|=|最⼩顶点覆盖|总体上，第三章的难度很⼤，本⼈只能理解其中的⼀⼩部分，哎……⾼级篇4.1 数学问题在此只介绍容斥原理。给定⼀个数列长度为m，求1到n中的整数⾄少能整除a中的⼀个元素的数有⼏个。此问题即是求容斥原理的公式，计算⽅法为：累加所有能整除⼀个元素的个数，减去所有两个元素的公倍数，……。代码如下：typedef long long ll;int a[MAX_N];int n,m;

void solve(){ ll res=0; //变量m个元素的所有⼦集 for(int i=0;i<(1<>=1)num+=j&1;//统计该⼦集有多少个元素 ll lcm=1; for(int j=0;j>j&1){ lcm=lcm/gcd([lcm,a[j]])*a[j];//求⼀个数组的最⼩公倍数

if(lcm>n) break; } } if(num%2==0) res-=n/lcm; else res+=n/lcm; } printf("%dn”,res);}4.3 图论⼤师1. 强连通分量 强连通分量分解可以通过两次DFS实现。第⼀次DFS时，选取任意顶点作为起点，遍历所有尚未访问过的顶点，并在回溯前给顶点标号。对剩余尚未访问过的顶点不断重复上述过程。完成标号后，越接近图的尾部，顶点的标号越⼩。第⼆次DFS时，先将所有边反向，然后以标号最⼤的顶点为起点进⾏DFS。这样DFS所遍历的顶点集合就构成了⼀个强连通分量。之后，只要还有尚未访问的顶点，就从中选取标号最⼤的顶点不断重复上述过程。求图的强连通分量⾮常重要，需要熟悉代码：int V;//定点数vector G[MAX_V];//图的邻接表表⽰vector rG[MAX_V];//把边反向后的图vector vs;//后序遍历顺序的顶点列表bool used[MAX_V];//访问标记int cmp[mAX_V];//所属强连通分量的拓扑序

void add_edge(int from,int to){ G[from].push_back(to); G[to].push_back(from);}

void dfs(int v){ used[v]=true; for(int i=0;i

void rdfs(int v,int k){ used[v]=true; cmp[v]=k; for(int i=0;i

}

int scc(){ memset(used,0,sizeof(used)); (); for(int v=0;v=0;i--){ if(!used[vs[i]])) rdfs(vs[i],k++); }

return k;}2. 2-SAT给定⼀个bool⽅程，判断是否存在⼀组布尔变量的真值指派使整个⽅程为真的问题，称为布尔⽅程的可满⾜性问题（SAT），该问题是⼀个NP问题。合取范式如下：如果合取范式中的每个⼦句中的变量个数都不超过两个，则对应的SAT问题⼜被称为2-SAT问题，该问题可以在线性时间内解决。解决⽅法是利⽤蕴含操作将每个⼦句，以改为这样原布尔公式就变成只有与运算的公式，每⼀个⼦句都是⼀个蕴含运算。对每个布尔变量x，构造两个顶点分别代表x和关系为边建⽴有向图。此时，如果图上的a点能够到达b点的话，就表⽰当a为真时b也⼀定为真。因此，同⼀强连通分量中所含的所有⽂字的布尔值均相同。 如果存在某个布尔变量x，x和

均在同⼀个强连通分量中，则⽆法令整个布尔公式的值为真。反之，对于每个布尔变量x，让

3. LCA LCA问题是求树中两个节点的最近公共祖先问题，针对不同类型的树和数据结构有不同的算法。1) 基于⼆分搜索的⽅法 记节点v到根的深度为depth(v)。那么，如果节点w是u和v的公共祖先的话，让u向上⾛depth(u)-depth(w)，让v向上⾛depth(v)-depth(w)步，都将⾛到w。因此，⾸先将u和v中较深的节点向上⾛|depth(u)-depth(v)|不，再⼀起⼀步步向上⾛，直到⾛到同⼀个节点，就可以在O(depth(u)+depth(v))时间内求出LCA。这要求的数据结构必须有⼀个parent域⽤来指⽰⽗节点，此外每个节点都有⼀个深度信息。2) 基于RMQ的算法⾸先，按从根DFS访问的顺序得到顶点序列vs[i]和对应的深度depth[i]。对于每个顶点v，记其在vs中⾸次出现的下标为id[i]。这些都可以在O(n)的时间内求得。⽽LCA(u，v)就是访问u之后到访问v之前所经过顶点中离根最近的那个。假设id[u]<=id[v]，那么有LCA(u,v)=vs[id[u]<=i<=id[v]中令depth(i)最⼩的i]⽽这变成了⼀个区间最⼩值查询问题，可以利⽤RMQ⾼效地求解。关于RMQ的求解，⼤家可以查阅⽹上关于RMQ的ST算法。 针对LCA问题，还有并查集+dfs的tarjan算法，更详细的资料可参考：。4.7 字符串1. 后缀数组 后缀数组是⼀个很难的东西，但是很有⽤，在此不做过多介绍。如果想深⼊了解它，请参考罗穗骞的和。后缀数组能处理很多问题。例如，字符串匹配，假设已经计算好字符串S的后缀数组，现在要求字符串T在S中出现的位置，只要通过⼆分搜索就可以在O(|T|log|S|)的时间内完成。如果配合使⽤最长公共前缀数组，就可以实现更多应⽤。可以⽤来寻找两个字符串的最长公共⼦串和字符串是最长回⽂⼦串。 整本书真是越看让⼈越感到⼒不从⼼，⼼⽣厌倦，但是⼀旦掌握⼀个思想，威⼒⽆穷。真⼼希望励志于算法的⼈能买下此书，细细研读，必有⾮常⼤的收获！勘误表1. P113：倒数第⼆段第⼀句“min(y1,y2)<=y<=min(y1,x2)”应改为“min(y1,y2)<=y<=min(y1,y2)”。2. P130：上⾯问题描述的限制条件“1<=N<=100” 应改为“1<=P<=100”。3. P132：Millionaire的问题描述第⼆句“⼀开始你有x元钱，接着进M轮赌博” 应改为“⼀开始你有x元钱，接着进⾏M轮赌博”。4. P152：⼀开始第⼀个求和“f[i]” 应改为“f[j]”；后⾯两个求和符合的下标“i=”应改为“j=”。5. P159：第⼆个公式的条件“是k是偶数时”应改为“当k是偶数时”。6. P361：第⼀⾏“我们统⼀⽤n表⽰数上节点的个数”应改为“我们统⼀⽤n表⽰树上节点的个数”。7.

p342 状态转移⽅程的所有s[j]都应该改为s[j+1]

2023年8月1日发(作者：)

挑战程序设计竞赛—知识总结准备篇1.5 运⾏时间概述编写的⽬的是⾯向ACM程序设计竞赛，不可避免的要涉及复杂度和运⾏时间的问题，本节给出了解决问题算法选择的依据。假设题⽬描述中给出的限制条件为，针对O(n2)的算法将会执⾏⼤于106次。如果时间限制是1s，则有下述结论：

上述结论表明，针对O(n2)的算法，n<=1000可以在时限内解决，但是如果n<=10000，则超时的可能性⾮常⼤，这就启⽰我们要寻找新的算法降低算法复杂度，否则将不能AC。1.6 三⾓形给定N个边，任选三边构成三⾓形，输出最⼤的周长。通过三层循环可以解决，但是复杂度为O(n3)。如果利⽤3.2节的折半枚举技巧可以在O(n2logn)的时间内解决：⾸先将所有的边排序，复杂度为O(nlogn)；然后两层循环得到任意两条边的距离之和；最后⼆分查找，找到能构成三⾓形的最⼤边。⽂中说还有O(nlogn)的算法，我不知道，希望有⼈能告诉我。折半枚举这个技巧⾮常有⽤，可以解决⼀⼤类问题，抽签问题即是⼀个⾮常好的例⼦。初级篇2.1 穷竭搜索1. 基础栈的头⽂件，常⽤⽅法：push，top，pop；队列的头⽂件，常⽤⽅法：push，front，pop。2. 深搜部分和问题：给定n个数，选出若各个其和是否为k。代码：int a[MAX_N];int n,k;

//已经从前i项得到了sum，然后对i项之和的进⾏分⽀bool dfs(int i,int sum){ if(i==n) return sum==k;

if(dfs(i+1,sum)) return true; if(dfs(i+1,sum+a[i])) return true;

return false;}

void solve() { if(dfs(0,0)) printf(“Yesn”);

else printf(“Non”);}该代码具有普遍性，能解决⾮常多的问题，如果不考虑复杂度01背包也可以按照这个思路解决。深搜按照回溯的策略去遍历问题的解空间，部分和问题和01背包问题的解都是原数组的⼦集，所以其解空间构成了⼀个⼆叉树。除了⼆叉树形式的解空间，还有很多问题的解空间是k叉树，例如⼋皇后问题，每⼀⾏的皇后有⼋个位置可以选择，解空间构成了⼀个⼋叉树。不管是⼏叉树，代码结构类似。此外《编程之美》第3.2节的电话号码对应英语单词也属于此类结构，只不过每⼀层的叉树不⼀样。解空间是k叉树时，遍历的复杂度是O(kn)。由于复杂度⾮常⾼，在遍历的过程中往往伴随着解空间的剪枝。还有很多问题的解空间不是原数据的⼦集，⽽是⼀个排列，此时解空间是⼀个排列树。最具代表性的⼀个例⼦是旅⾏商问题，其每⼀层的树节点都在逐次减⼀，所以其复杂度是O(n!)。还有⼀些问题不属于上⾯的两类情况，例如n皇后问题，其复杂度变为O(nn)。还有⼀个例⼦是《编程之美》1.3节的烙饼排序问题，也是⼀个复杂度变为O(nn)的深搜问题。剑指offer⾯试题12的打印1到最⼤n位数也可以通过每次都是O(n)复杂度的深搜完成。不管属于哪⼀类，它们的代码结构⽐较类似：dfs(int i){ //1 输出结果 if(i==n) printf();

//2 剪枝

//3遍历下⼀层 for(int j=0;j=w[i];j--){ dp[j]=max(dp[j], dp [j-w[i]]+v[i]); } } printf(“%dn”,dp[W]);}完全背包问题的空间优化代码：int dp[MAX_W+1];void solve(){ for(int i=0;i

CompletePack(weight,value) for w from weight to W do f [w] = max(f [w], f [w-weight] + value)根据上⾯两个背包问题的伪代码，多重背包问题就可以按照下⾯的思路解决：MultiplePack(weight; value; amount)if weight * amount > W then CompletePack(cost; weight) returnk=1 while k < amount do ZeroOnePack(k*weight; k*value) amount=amount-k k=k*2ZeroOnePack(amount*weight; amount*value)上⾯解决多重背包的⽅法是将其每⼀个物品分别分解成完全背包或者是01背包问题来解决，虽然不是最低复杂度，但是效率也很⾼。将上述三种背包混合就得到混合背包问题，伪代码为：for i from 1 to N do if 第i件物品属于01背包 then ZeroOnePack(w[i]; v[i]) else if 第i件物品属于完全背包 then CompletePack(w[i]; v[i]) else if 第i件物品属于多重背包 then MultiplePack(w[i]; v[i]; m[i])关于初等背包的另⼀个需要注意问题是初始化问题。有的题⽬要求“恰好装满背包”时的最优解，有的题⽬则并没有要求必须把背包装满。⼀种区别这两种问法的实现⽅法是在初始化的时候有所不同。如果是第⼀种问法，要求恰好装满背包，那么在初始化时除了f[0]为0，其它f[1..W]均设为-∞，这样就可以保证最终得到的f[N]是⼀种恰好装满背包的最优解。如果并没有要求必须把背包装满，⽽是只希望价格尽量⼤，初始化时应该将f[0..W]全部设为0。⼀个“恰好装满背包”的实例是编程之美1.6节的饮料供应问题。关于背包问题的⾼级主题和详细介绍⼤家可以看：

。

2.4 数据结构1. 基本结构STL中的优先队列为priority_queue，头⽂件为，常⽤操作为：push，top，pop，empty，size。该优先队列默认pop的是最⼤值，如果想pop最⼩值（最⼩堆），则需要指明⽐较函数：priority_queue,greater> que;STL中实现⼆叉搜索树的容器有set和map，头⽂件分别为和

void init(int n){ for(int i=0;i

int find(int e){ int j=e; while(!root[j]) j=parent[j];

int f=e; while(f!=e) { int pf=parent[f]; parent[f]=j; f=pf; }

return j;}

void union(int i,int j) { if(parent[i]

root[i]=false; parent[i]=j; } else{parent[i]+=parent[j]; root[j]=false; parent[j]=i; }}并查集的⼀个最典型应⽤是Kruskal算法解决最⼩⽣成树（MST）问题。2.5 图1. 图着⾊问题书中介绍了⼆分图的判定问题，代码如下：vector G[MAX_V];//图 int V; int color[MAX_V];

bool dfs(int v,int c){ color[v]=c; for(int i=0;i

void solve(){ for(int i=0;i P;//保存的结果，first为最短距离，second为相应顶点

int V;vector G[MAX_V];int d[MAX_V];

void dijkstra(int s){ priority_queue,greater

> que; fill(d,d+V,INF); d[s]=0; (P(0,s));

while(!()){ P p=(); (); int v=; for(int i=0;id[v]+){ d[]=d[v]+; (P(d[],)); } } }}Prim算法是求MST，它和Dijkstra算法⼗分相似，都是从某个顶点出发，不断添加边的算法。2.6 简单的数学问题1. 埃⽒筛法判断⼀个数是否是素数，只需要判断⼩于等于n的开⽅的整数能否整除n即可。如果需要求所有⼩于n的素数，则需要埃⽒筛法。思想很简单，代码如下：int prime[MAX_N];bool is_prime[MAX_N+1];

int sieve(int n){ int p=0; for(int i=0;i<=n;i++) is_prime[i]=true; is_prime[0]=is_prime[1]=false; for(int i=2;i<=n;i++){ if(is_prime[i]){ prime[p++]=I; for(int j=2*i;j<=n;j+=i) is_prime[j]=false; } } return p;}快速幂运算在求xn时，我们通过将n按照⼆进制分解，可以获得⼀个求幂的快速算法：typedef long long ll;

ll mod_pow(ll x,ll n,ll mod){ ll res=1; while(n>0){ if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res;}求幂的快速算法在求矩阵的幂时也可以采⽤。总体上，第⼆章的难度中等偏上，只要能多思考，绝⼤多数问题都能看懂。中级篇3.1 ⼆分搜索通过该节让我真切明⽩⼆分搜索的应⽤价值远远⼤于其看上去的样⼦，所以该节内容值得仔细研究。另⼀⽅⾯，⼆分搜索的难度也不像其看上去的样⼦，⽹上说“80%的程序员写不对⼆分查找”并⾮谣⾔。1. lower_bound 给定⼀个单调不下降数列和⼀个数k，求满⾜ai>=k的最⼩i。 ⾸先看⼀下第n/2个值。如果a[n/2]>=k，则可以知道解的范围不⼤于n/2。反之，如果a[n/2]

void lower_bound(){ int lb=-1,ub=n;

while(ub-lb>1){ int mid=(lb+ub)/2; if(a[mid]>=k) ub=mid; else lb=mid; } printf(“%dn”,ub);}上述算法不仅能找到要寻找的值，⽽且返回的是⼀系列值中的最⼩值，可以⽤来求解“满⾜某个条件C(x)的最⼩的x”问题。STL将上述代码以lower_bound函数的形式实现，不过需要注意的是该函数返回的是⼀个位置指针，可以通过解引⽤来获取元素值，还可以通过与数组起点相减获得位置下标。与此类似的还有函数upper_bound函数，它返回ai>k的最⼩i。利⽤这两个函数我们就可以求数组中元素k出现的次数： upper_bound(a,a+n,k)-lower_bound(a,a+n,k); 后⾯三个⼩节讲了⼆分搜索的应⽤，它们都依赖下⾯的基本原理：问题的正确解为X，当给定的解⼩于等于X时，都能满⾜要求；当给定的解⼤于X时，解不满⾜要求。也即解空间以X为分界，分成正确的和错误的两个⼦集。解题流程都是：判断⼀个给定的数x是否满⾜条件，若满⾜条件就放⼤x，否则就减⼩x，通过不停地减⼩搜索区间找到最后的值。对于x是浮点数的情况，可以通过设定⼀个遍历次数的上届完成⼆分搜索。由于⼆分搜索每次将区间减⼩⼀半，所以100次遍历即可以将区间减到任意精度。对于x是整数的情况，可以简单的选取lb为问题的解。这是因为lb总是问题的解，ub总不是问题的解，当两者距离等于1时，搜索结束。此时lb还是问题的解，ub依旧不是问题的解。此外，前⾯介绍的图最⼩着⾊问题也是⽤了⼆分搜索的思想。3.2 常⽤技巧（⼀）1. 尺取法 给定⼀个长度为n的正整数数列，以及整数S。求总和不⼩于S的连续⼦序列的长度最⼩值。 可以按照如下⽅法解决该问题：（1） 设置两个指针s和t，⼀开始都指向数列第⼀个元素，此外sum=0,res=0；（2） 只要sum=S，更新res=min(res,t-s)；（4） 将sum减去⼀个元素，s加1，执⾏（2）。上述流程反复地推进区间的开头和末尾，来求取满⾜条件的最⼩区间。代码如下：void solve(){ int res=n+1; int s=0,t=0,sum=0; for(;;){ while(tn) res=0;}尺取法在别的地⽅⼜被称为滑动窗⼝或者蠕⾍算法，应⽤很⼴。让⼈看不明⽩的编程之美3.5节最短摘要的⽣成也是采⽤了此法。2. 位运算 常⽤集合运算的位运算：（1） 空集：0；（2） 只含有第i个元素的集合：1<>i&1);（5） 向集合加⼊第i个元素：S|1<>1)|y;}3.5 ⽹络流 很多问题都可以转⾏为⼆分图匹配，所以⼆分图匹配的匈⽛利算法要掌握。在⽹络流中有四个概念需要强调：匹配：在G中两两没有公共端点的边集合M边覆盖：G中的任意顶点都⾄少是F中某条边的端点的边集合F独⽴集：在G中两两互不相连的顶点集合S顶点覆盖：G中的任意边都有⾄少⼀个端点属于S的顶点集合S 以上四个概念满⾜如下关系：对于不存在孤⽴点的图，|最⼤匹配|+|最⼩边覆盖|=|V||最⼤独⽴集|+|最⼩顶点覆盖|=|V| 利⽤这些关系，对于最⼤匹配和最⼩边覆盖，最⼤独⽴集和最⼩顶点覆盖，只要能求解其中⼀个，另⼀个问题也就得到解决。最⼤独⽴集问题是NP复杂的问题，但是针对⼆分图，有如下等式成⽴： |最⼤匹配|=|最⼩顶点覆盖|总体上，第三章的难度很⼤，本⼈只能理解其中的⼀⼩部分，哎……⾼级篇4.1 数学问题在此只介绍容斥原理。给定⼀个数列长度为m，求1到n中的整数⾄少能整除a中的⼀个元素的数有⼏个。此问题即是求容斥原理的公式，计算⽅法为：累加所有能整除⼀个元素的个数，减去所有两个元素的公倍数，……。代码如下：typedef long long ll;int a[MAX_N];int n,m;

void solve(){ ll res=0; //变量m个元素的所有⼦集 for(int i=0;i<(1<>=1)num+=j&1;//统计该⼦集有多少个元素 ll lcm=1; for(int j=0;j>j&1){ lcm=lcm/gcd([lcm,a[j]])*a[j];//求⼀个数组的最⼩公倍数

if(lcm>n) break; } } if(num%2==0) res-=n/lcm; else res+=n/lcm; } printf("%dn”,res);}4.3 图论⼤师1. 强连通分量 强连通分量分解可以通过两次DFS实现。第⼀次DFS时，选取任意顶点作为起点，遍历所有尚未访问过的顶点，并在回溯前给顶点标号。对剩余尚未访问过的顶点不断重复上述过程。完成标号后，越接近图的尾部，顶点的标号越⼩。第⼆次DFS时，先将所有边反向，然后以标号最⼤的顶点为起点进⾏DFS。这样DFS所遍历的顶点集合就构成了⼀个强连通分量。之后，只要还有尚未访问的顶点，就从中选取标号最⼤的顶点不断重复上述过程。求图的强连通分量⾮常重要，需要熟悉代码：int V;//定点数vector G[MAX_V];//图的邻接表表⽰vector rG[MAX_V];//把边反向后的图vector vs;//后序遍历顺序的顶点列表bool used[MAX_V];//访问标记int cmp[mAX_V];//所属强连通分量的拓扑序

void add_edge(int from,int to){ G[from].push_back(to); G[to].push_back(from);}

void dfs(int v){ used[v]=true; for(int i=0;i

void rdfs(int v,int k){ used[v]=true; cmp[v]=k; for(int i=0;i

}

int scc(){ memset(used,0,sizeof(used)); (); for(int v=0;v=0;i--){ if(!used[vs[i]])) rdfs(vs[i],k++); }

return k;}2. 2-SAT给定⼀个bool⽅程，判断是否存在⼀组布尔变量的真值指派使整个⽅程为真的问题，称为布尔⽅程的可满⾜性问题（SAT），该问题是⼀个NP问题。合取范式如下：如果合取范式中的每个⼦句中的变量个数都不超过两个，则对应的SAT问题⼜被称为2-SAT问题，该问题可以在线性时间内解决。解决⽅法是利⽤蕴含操作将每个⼦句，以改为这样原布尔公式就变成只有与运算的公式，每⼀个⼦句都是⼀个蕴含运算。对每个布尔变量x，构造两个顶点分别代表x和关系为边建⽴有向图。此时，如果图上的a点能够到达b点的话，就表⽰当a为真时b也⼀定为真。因此，同⼀强连通分量中所含的所有⽂字的布尔值均相同。 如果存在某个布尔变量x，x和

均在同⼀个强连通分量中，则⽆法令整个布尔公式的值为真。反之，对于每个布尔变量x，让

3. LCA LCA问题是求树中两个节点的最近公共祖先问题，针对不同类型的树和数据结构有不同的算法。1) 基于⼆分搜索的⽅法 记节点v到根的深度为depth(v)。那么，如果节点w是u和v的公共祖先的话，让u向上⾛depth(u)-depth(w)，让v向上⾛depth(v)-depth(w)步，都将⾛到w。因此，⾸先将u和v中较深的节点向上⾛|depth(u)-depth(v)|不，再⼀起⼀步步向上⾛，直到⾛到同⼀个节点，就可以在O(depth(u)+depth(v))时间内求出LCA。这要求的数据结构必须有⼀个parent域⽤来指⽰⽗节点，此外每个节点都有⼀个深度信息。2) 基于RMQ的算法⾸先，按从根DFS访问的顺序得到顶点序列vs[i]和对应的深度depth[i]。对于每个顶点v，记其在vs中⾸次出现的下标为id[i]。这些都可以在O(n)的时间内求得。⽽LCA(u，v)就是访问u之后到访问v之前所经过顶点中离根最近的那个。假设id[u]<=id[v]，那么有LCA(u,v)=vs[id[u]<=i<=id[v]中令depth(i)最⼩的i]⽽这变成了⼀个区间最⼩值查询问题，可以利⽤RMQ⾼效地求解。关于RMQ的求解，⼤家可以查阅⽹上关于RMQ的ST算法。 针对LCA问题，还有并查集+dfs的tarjan算法，更详细的资料可参考：。4.7 字符串1. 后缀数组 后缀数组是⼀个很难的东西，但是很有⽤，在此不做过多介绍。如果想深⼊了解它，请参考罗穗骞的和。后缀数组能处理很多问题。例如，字符串匹配，假设已经计算好字符串S的后缀数组，现在要求字符串T在S中出现的位置，只要通过⼆分搜索就可以在O(|T|log|S|)的时间内完成。如果配合使⽤最长公共前缀数组，就可以实现更多应⽤。可以⽤来寻找两个字符串的最长公共⼦串和字符串是最长回⽂⼦串。 整本书真是越看让⼈越感到⼒不从⼼，⼼⽣厌倦，但是⼀旦掌握⼀个思想，威⼒⽆穷。真⼼希望励志于算法的⼈能买下此书，细细研读，必有⾮常⼤的收获！勘误表1. P113：倒数第⼆段第⼀句“min(y1,y2)<=y<=min(y1,x2)”应改为“min(y1,y2)<=y<=min(y1,y2)”。2. P130：上⾯问题描述的限制条件“1<=N<=100” 应改为“1<=P<=100”。3. P132：Millionaire的问题描述第⼆句“⼀开始你有x元钱，接着进M轮赌博” 应改为“⼀开始你有x元钱，接着进⾏M轮赌博”。4. P152：⼀开始第⼀个求和“f[i]” 应改为“f[j]”；后⾯两个求和符合的下标“i=”应改为“j=”。5. P159：第⼆个公式的条件“是k是偶数时”应改为“当k是偶数时”。6. P361：第⼀⾏“我们统⼀⽤n表⽰数上节点的个数”应改为“我们统⼀⽤n表⽰树上节点的个数”。7.

p342 状态转移⽅程的所有s[j]都应该改为s[j+1]