acm算法竞赛模板个人总结

《acm算法竞赛模板个人总结》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数学4最大公约数、最小公倍数4最大公约数——欧几里得算法O(n)4Stein算法O(log(max(a,b)))4最小公倍数：4素数相关5普通素数判断5筛法求素数[1，N]5二次筛法求素数[L，R]6Miller-Rabbin素数测试方法7算术基本定理的定义和性质：8同余方程[组]乘法模逆元中国剩余定理9扩展欧几里得，求一组解x，y，使得gcd(a,b)=d=a*x+b*y9扩展欧几里得，求所有解x，y，使得c=a*x+b*y10扩展欧几里得，求a关于n的逆元a^-1，使得a*a^-1≡1(modn)10扩展欧几里得，求解x，满足同余方

2、程组x≡Ri(modAi)10扩展欧几里得，求解x，满足高次同余方程A^x≡B(modC)11中国剩余定理：13中国剩余定理最小非负数解的算法：14求解a*x+b*y=c的其中一组解，使得

3、x

4、+

5、y

6、尽可能小，若相等，则a

7、x

8、+b

9、y

10、尽可能小。15整数快速幂16矩阵快速幂16整数分解18试除法整数分解18筛法整数分解18PollardRho大整数分解19欧拉函数22直接欧拉函数22递推快速求欧拉函数23容斥原理23母函数24普通母函数24指数型母函数25其他相关27九余数定理：一个数N各位数字的和，对9取余等于这个数对9取余27给

11、你一个奇数N，求1~N的奇数平方和：S=N*(N+1)*(N+2)/627约瑟夫问题：有N个人，编号为1~N，按顺时针围成一个圈，每数k个人，就将这个人从圈中消除，问：最终只留下一个人的编号。27给你整数x和y的和以及x和y的积，是否能找到满足这两个式子的整数x和整数y。29Fibonacci数列大于40前四位数字29小于N的素数个数为π(N),π(N)的位数是多少？29Stirling公式：当N足够大时，N!=(N/e)*N*sqrt(2*pi*N)。29有N张卡，将N张卡分成若干不同的集合，集合不能为空。问：总共有多少种分法。29字

12、符串29KMP291.既能做前缀又能做后缀的子串长度302.求最短子串长度303.求模式串pat在主串str中匹配次数304.求N行M列的字符矩阵，最小的字符子矩阵的面积305.求字符串s的循环前缀的长度和循环的次数30字典树31数据结构33并查集33树状数组33单点更新，区间求值：树状数组代表区间的和。33区间更新，单点求值：树状数组代表单个元素的变化34求逆序数：数组Tree[i]表示数字i是否在序列中出现过，如果数字i已经存在于序列中，Tree[i]=1，否则Tree[i]=0。按序列从左到右将值为a的元素当作下标为a，赋值为1插

13、入树状数组里，这时，比a的数个数就是i-Query(a)。将全部结果累加起来就是逆序数了。35二维树状数组：36线段树36单点更新37成段更新43区间合并52扫描线54图论58图的五种种存储方式58方式1：邻接矩阵58方式2：前向星58方式3：邻接表——动态建表59方式4：邻接表——vector模拟链表实现60方式5：邻接表——链式前向星★61拓扑排序62最小生成树63Kruskal算法：63Prim算法：64次小生成树65最小树形图68最近公共祖先LCA—Tarjan-LCA算法：72树的最小支配集、最小点覆盖、最大独立集74最小支配

14、集：指从所有顶点中取尽量少的点组成一个集合，使得剩下的所有点都与取出来的点有边相连。顶点个数最小的支配集被称为最小支配集。这里用贪心法来求。74最小点覆盖：指从所有顶点中取尽量少的点组成一个集合，使得集合中所有的边都与取出来的点有边相连。顶点个数最小的覆盖集被称为最小点覆盖。76最大独立集：指从所有顶点中取尽量多的点组成一个集合，使得这些点之间没有边相连。顶点个数最多的独立集被称为最大独立集。77单源最短路径Dijkstra、BellmanFord、SPFA77Dijkstra算法：77BellmanFord算法：79SPFA算法：81

15、多源最短路径Floyd、Floyd求最小环84Floyd算法：用来找出每对点之间的最短距离。图可以是无向图，也可以是有向图，边权可为正，也可以为负，唯一要求是不能有负环。84Floyd求最小环85K短路—A*+SPFA算法：86差分约束系统89强连通分量Kosaraju、Tarjan91Kosaraju算法：92Tarjan算法：942-SAT97二分图100二分图最大匹配——匈牙利算法DFS版：100二分图多重匹配：101二分图最佳匹配——KM算法：102网络流最大流EdmondKarp、SAP104EdmondKarp算法：104S

16、AP算法：106输入输出外挂—仅适合纯数字输入109数学最大公约数、最小公倍数最大公约数、最小公倍数性质：1.若a

17、m，b

18、m，则lcm(a，b)

19、m。2.若d

20、a，d

21、b，则d

22、gcd(a，b)。3.lc