ACM算法学习路线、清单

入门

模拟、暴力、贪心、高精度、排序

图论

搜索

BFS、DFS、IDDFS、IDA*、A*、双向BFS、记忆化

最短路

SPFA、bellman-fort(队列优化)、Dijkstra(堆优化)、Johnson、Floyd、差分约束、第k短路

树

树的重心和直径、dfs序、树链刨分与动态树、LCA、Prufer编码及Cayley定理、分治、最小生成树{ Prim(堆优化)、Kruskal }

图的联通

强联通分量、双联通分量、割点和桥、2-SAT

网络

网络流{
最大流-最小割
费用流{ zkw费用流、有负费用圈的转化 }
有上下界的网络流 }、
二分图{
最大匹配(匈牙利算法)、最大独立集、最大点权覆盖集、最小路径覆盖}、
方案唯一性

欧拉图

最小平均循环

拓扑排序

计算几何

凸包、半平面交、圆并圆交、pick定理、三角刨分、扫描线、旋转卡壳、仿射变换与矩阵

技巧与思想

二分、三分、位运算、离散化、分块、图的拆点、数列差分化及前缀和、启发式合并、cdq分治、哈夫曼编码、倍增(RMQ、LCA)、莫队算法(树上莫队)

字符串

KMP、Trie(xor问题) 、AC自动机、
后缀树{
后缀数组（波兰表）
后缀自动机
后缀仙人掌}、
LCP、Manacher、有限状态自动机

博弈论

SG函数、极大极小搜索算法（alpha-beta）

数据结构

栈(单调栈)、队列(单调队列)、堆(左偏堆)、链表、哈希表、
并查集{
路径压缩、带边权的并查集、拆点}、
块状链表-块状树、树状数组、
线段树{
Lazy-tag、合并、动态开点、zkw线段树}、
平衡树{
SBT、
splay{ 维护序列:Lazy-tag、合并与分裂 Finger search}
treap 合并与分裂
替罪羊树}、
划分树、归并树、k-d树、主席树、树套树

数学相关

线性筛素数、费马小定理及mr素数判断、高斯消元、原根、模方程{ 模意义下开根、模意义下求对数}、乘法逆元、容斥原理及Ramsey定理(补集转化）、gcd及扩展gcd、中国剩余定理、快速幂、置换、矩阵乘法、欧拉函数、数值与积分、概率与期望、更相减损术、莫比乌斯反演、快速傅里叶变换、排列组合、群论与Burnisde-Polya、母函数

规划

动态规划{
背包{01背包、完全背包、多重背包}
简单模型{LCS、LIS、LCIS}
区间DP
树形DP
数位DP
概率DP
斜率优化
四边形不等式(决策单调性)
数据结构优化
状态压缩(基于连通性的状态压缩)}、
线性规划{ 转化为图论模型、单纯型法}、
分数规划(01分数规划)

其他

随机算法、模拟退火、朱刘算法、爬山算法、遗传算法、DLX算法