ACM竞赛算法知识导图（会继续补充）

一、动态规划(dp)

1.线性dp

2.状压dp

（1）高维前缀和

（2）动态高维前缀和

3.区间dp

4.树形dp（普通型，换根型）

5.概率dp

6.数位dp

7.背包

（1）01背包

（2）无限背包

（3）多重背包

（4）树形背包

（5）分组背包

（6）混合背包

（7）多维背包

（8）巨大背包

8.记忆化搜索

9.轮廓线dp

10.插头dp

11.计数dp

12.图上dp

13.基环树dp

14.自动机dp（状态机模型）

15.分治dp

16.填坑dp

17.动态dp

18.dp套dp

19.优化

（1）单调栈优化

（2）单调队列优化

（3）四边形不等式优化

（4）斜率优化

（5）数据结构优化

（6）决策单调性

二、数据结构

1.队列

（1）普通队列

（2）双端队列

（3）单调队列

2.栈

（1）普通栈

（2）单调栈

3.链表

（1）普通链表

（2）双向链表

（3）循环链表

（4）跳表（块状链表）

（5）邻接表、邻接矩阵（存图）

4.堆

（1）普通堆

（2）对顶堆

（3）斐波那契堆

（4）左偏堆

5.线段树

（1）基础线段树

（2）权值线段树

（3）主席树（可持久化线段树）

（4）李超线段树

（5）线段树合并

（6）zkw线段树

6.树状数组

7.平衡树

（1）Splay

（2）FHQ（范浩强）

（3）Treap

（4）可持久化平衡树

（5）AVL

（6）SBT

（7）替罪羊树

（8）红黑树

8.并查集

（1）普通并查集

（2）带权并查集

（3）可持久化并查集

9.ST表

10.DLX（Dancing Links）

11.KD树

（1）动态

（2）普通

12.树套树

（1）线段树套线段树

（2）线段树套平衡树

13.笛卡尔树

14.LCT

15.虚树

16.树链剖分

（1）重链剖分

（2）长链剖分

17.树的启发式合并

18.DSU on tree

19.划分树

20.析合树

21.动态树

22.RMQ

23.差分数组、前缀和

24.AC自动机

25.SA数组

26.SA自动机

27.Trie（字典树）

28.后缀树

29.回文自动机

30.分块

（1）莫队

（2）链上分块

（3）树上分块

31.左偏树

32.点分治

33.点分树

34.CDQ分治

35.仙人掌

36.pb_ds库

37.STL

38.树的哈希

39.串的哈希

40.B树

41.B+树

42.可持久化Trie

43.珂朵莉树（ODT）

44. van Emde Boas 树

45.不相交集合森林

46.二叉堆

三、计算几何

1.基本知识

（1）点集

（2）叉积

（3）极角序

（4）Pick定理

2.线段（直线）

（1）相交判定

（2）交点

（3）旋转

3.多边形

（1）凸包

（2）多边形包含

（3）旋转卡壳

（4）半平面交

（5）重心

（6）格点数

（7）凸包直径

（8）凸多边形的交、并

（9）多边形的核

（10）凸包与直线的集交

4.圆

（1）交点切线

（2）面积交、并

（3）最小圆覆盖

（4）圆反演

（5）圆的离散化

（6）圆与线求交

（7）圆与凸包求交

5.三角剖分

6.扫描线

7.数值计算

（1）辛普森积分

（2）自适应辛普森积分

8.点定位

9.凸包快速操作

10.Voronoi图

11.最近点对

12.三维计算几何

（1）点、直线、平面、向量旋转

（2）长方体表面两点最短距离

（3）点积、叉积、混合积

（4）四面体体积

（5）最小球覆盖

（6）三维凸包

13.三角形四心

14.平面最小哈曼顿距离生成树

15.最大空凸包

16.平面划分

17.费马点

18.托勒密定理

19。对踵点

四、数论

1.埃式筛

2.欧拉筛

3.杜教筛

4.gcd、lcm

5.快速幂

6.逆元（费马小定理）

7.扩展欧几里得（扩欧）

8.费马定理/欧拉定理

9.扩展欧拉定理

10.原根/阶

11.单位根

12.类欧几里得

13.同余方程组

（1）中国剩余定理

（2）扩展中国剩余定理

14.Lucas定理

（1）Lucas

（2）exLucas

15.离散对数

（1）BSGS

（2）Pohlig-Hellman

16.线性筛

17.整除分块

18.狄利克雷卷积

19.莫比乌斯反演

20.min25筛

21.Miller Rabin

22.Pollard Rho

23.佩尔方程

24.单位根反演

25.二次剩余

（1）勒让德符号

（2）Cipolla算法

26.矩阵快速幂

27.Gauss消元

28.线性基

29.行列式

30.矩阵求逆

31.常系数线性递推

32.矩阵树定理

33.BM

34.BEST 定理

35.特征值、特征向量

36.组合数

（1）杨辉三角

（2）多重集组合数

37.二项式定理

38.概率论

（1）期望的线性性

（2）条件概率

39.容斥原理

（1）鸽巢原理（抽屉原理）

（2）min-max容斥

（3）二项式反演

40.斐波那契数列

41.错排问题

42.卡特兰数

43.拆分数

44.斯特林数

45.贝尔数

46.伯努利数

47.prufer序列 

48.LGV引理

49.杨表

50.博弈论

（1）Nim 游戏

（2）SG函数

（3）不平等博弈（超现实数）

51.FFT

52.NTT

53.拉格朗日插值

54.生成函数

55.多项式全家桶

56.集合幂级数（FWT\FMT）

57.群论

（1）置换

（2）Burnside引理

（3）Polya定理

58.线性规划

59.质因数分解

60.单变元模线性方程

61.N次剩余

62.平方剩余

63.欧拉函数

64.Mobius 函数

65.高阶代数方程式求根

66.进制转换

67.格雷码

68.高精度

69.全排列散列

70.除数函数

71.积性函数

72.莫比乌斯函数

73.三角形数

74.降幂公式

75.Stirling 数

76.母函数

77.Bertrand猜想

78.威尔逊定理

79.最小二乘法

80.哥德巴赫猜想

五、图论

1.图的储存

（1）邻接表

（2）前向星

（3）链式前向星

（4）邻接矩阵

2.DFS

3.BFS

4.拓扑排序

5.欧拉图（回路）

6.哈密顿图

7.单源最短路

（1）Dijkatra

        I.朴素版

        II.堆优化版

（2）Bellman-ford

（3）spfa

（4）最短路径树

8.传递闭包(Floyd - Warshall) -- 每对顶点间的最短路径

9.k短路

10.差分约束

11.Floyd 求最小环

12.树的遍历（前、中、后、层序）

13.最小生成树

（1）Prim

（2）Kruskal

（3）Boruvka

14.次小生成树

15.最小树形图

16.LCA

（1）离线 tarjan

（2）在线 dfs + ST

（3）倍增算法

17.树的直径

18.最小支配集

19.最小点覆盖

20.最大独立集（团）--- 最大完全子图

21.点（边）双连通分量

（1）tarjan

（2）割点、割边

（3）圆方树

（4）kosaraju

（5）缩点

22.二分图

（1）二分图判定（染色）

（2）匈牙利算法

（3）KM

（4）hopcraft-karp

（5）二分图最大匹配

（6）DAG

23.网络流

（1）最大流（最小割）

        I.Dinic

        II.Sap

（2）费用流

        I.最大流

        II.可行流

        III.zkw 费用流

（3）上下界网络流

24.2-Sat

25.竞赛图

26.斯坦纳树

27.一般图匹配

28.支配树

29.全局最小割

30.弦图的判定

31.仙人掌图

（1）无向仙人掌图

（2）有向仙人掌图

32.混合图欧拉回路

33.Hopcroft - Karp算法

34.单独限制最小生成树

35.最优比例生成树

36.完美消除序列

37.最大团搜索

38.极大团的计数

39.图的同构

40.树的同构

41.Johnson算法

42.Ford-Fulkerson 方法

43.最大二分匹配

44.推送-重贴标签算法

45.前置重贴标签算法

46.流网络

47.树的计数

48.有特殊条件的汉密尔顿回路

49.普吕弗序列

50.模2意义下的二分图匹配数

六、字符串

1.KMP

2.扩展KMP

3.Manacher

4.AC自动机

5.SA 数组

（1）DC3

（2）DA suffix array 倍增算法

6.SA 自动机

7.字符串hash

8.字符串散列

9.串的最小表示

10.有限状态自动机

11.字典树（Trie）

12.回文自动机

13.最小表示法

14.Lyndon 分解

15.后缀树

16.Rabin - Karp 算法

 七、杂

1.排序

（1）选择排序

（2）冒泡排序

（3）插入排序

（4）快速排序

（5）归并排序

（6）桶排序

（7）基数排序

（8）堆排序

（9）希尔排序

（10）计数排序

2.模拟

3.递归、回溯

4.贪心

（1）Haffman 树

（2）排序不等式

（3）绝对值不等式

5.二分

6.高精度

7.时空复杂度

8.离散

9.前缀和、差分

10.逆序对

11.扫描线

12.双指针

13.倍增

14.三分

15.枚举子集、超集

16.搜索

（1）DFS

（2）BFS

（3）A*

（4）IDA

（5）Flood Fill

（6）DLX

（7）折半搜索

（8）剪枝

17.分治

（1）树上分治

（2）点分

（3）边分

（4）动态点分

（5）cdq分治

18.随机

（1）爬山法

（2）模拟退火

（3）遗传算法

19.快读、快写

20.对拍

21.拟阵

22.转换

23.构造

24.计算

25.序列

26.主定理

27.区间树

28.核算法

29.势能法

30.动态表

31.聚合分析

32.多线程算法

33.NP完全性

34.近似算法

（1）顶点覆盖问题

（2）旅行商问题

（3）集合覆盖问题

（4）随机化和线性规划

（5）子集和问题

35.随机化算法

（1）随机数

（2）数值随机化算法

（3）舍伍德算法

（4）拉斯维加斯算法

（5）蒙特卡罗算法