（有下划线的表示还不了解）

动态规划

基础

• 线性dp、区间dp，主要就是状态方程的设计和状态的转移

• 背包dp，及其扩展 《背包九讲》是很好的学习资料

• 用dp递推概率、期望（dp求期望一般分为两种。一种是dp状态保存的是概率，则期望=概率*花费。另一种是dp状态直接保存期望，这样一般都是逆推的。）

• 树形dp（有些会套个背包dp，有些需要多次树形dp）

• 状态压缩dp

• 数位dp

• RMQ、二维RMQ

进阶

• dp优化

  使用数据结构优化，如线段树、树状数组、单调队列、单调栈、维护前缀和 …

  斜率优化（具有单调性可直接用单调队列或者二分，不具单调性要用平衡二叉树动态维护凸壳）

  四边形不等式优化

• 插头dp

数据结构

基础

• 队列、栈

• 树、图的存储、遍历 邻接表和邻接矩阵

• 单调队列、单调栈

• 线段树、树状数组

• 并查集、带权并查集

• 堆、优先队列

• 平衡二叉树

  Treap

  Spaly必须会

  [红黑树]

  [AVL树]

• Hash散列表

进阶

• 分块数组（分块的思想很强大）
• 二维线段树（就是线段树套线段树，其实还有个[矩形树]）、二维树状数组（就是树状数组套树状数组）
• 树链剖分
• 树套树，如线段树套平衡二叉树、树状数组套平衡二叉树 …
• Link-Cut-Tree（解决一类动态树的问题，可以说是树的剖分+Splay）
• 可持久化数据结构，如主席树、可持久化线段树、可持久化字典树、可持久化并查集、可持久化Treap …

搜索

基础

• 深搜
• 广搜
• 记忆化搜索（也可以放到dp分类里）
• 使用优先队列的广搜
• 模拟退火、爬山算法

进阶

• 搜索剪枝
• 双向广搜
• A、IDA
• 舞蹈链

图论

基础

• 最短路（Dijkstra、Spfa、Floyd）

• 最小生成树（Prim、Kruskal）

• 拓扑排序

• 二分图最大匹配（匈牙利算法）

  二分图的最小顶点覆盖

  DAG图的最小路径覆盖

  二分图的最大独立集

• 二分图最优匹配（KM算法）

• 二分图多重匹配

• 网络流

  最大流（Dinic、Sap）

  最小费用最大流

  带上下界的最大流

• 有向图强连通分量的Tarjan算法

• 最近公共祖先 Tarjan算法实现与RMQ实现各有千秋

• 差分约束系统

• 欧拉回路

• 构造哈密顿回路

• 最大团

• 无向图全局最小割（StoerWagner）

进阶

• 次小生成树

• 最优比率生成树

• [度限制生成树]

• [第k小生成树]

• 次短路、第k短路

• 网络流 胡伯涛的《最小割模型在信息学竞赛中的应用》是很好的学习资料

  最大权闭合图

  最大密度子图

  二分图最小点权覆盖集

  二分图最大点权独立集

  区间k覆盖的模型

  平面图网络流

• 无向图的割点和桥、边双联通分量、点双联通分量

• 2-SAT

• 最小树形图

• 一般图匹配

• 生成树计数、最小生成树计数

数学

基础

数论

• 欧几里得算法、扩展欧几里得算法

  乘法逆元

  中国剩余定理

  欧拉函数

  欧拉定理

  Miller_Rabin大素数判定

  Pollard_rho大整数拆分

• 线性代数

  矩阵乘法&快速幂

  高斯消元

• 组合数学

  容斥原理

  鸽巢原理

  [母函数]

  [稳定婚姻问题]

• 概率统计

• 群论

  置换群

  BurnSide引理

  Polya定理

进阶

• 莫比乌斯反演
• BSGS
• FFT
• ……
• 数学的进阶内容太多了

字符串

基础

• KMP、扩展KMP
• 字典树
• 最长回文子串的Manacher算法
• 字符串最小/最大表示法
• 许多字符串问题可以用dp甚至贪心求解

进阶

• AC自动机、Trie图
• 回文树
• 后缀数组、后缀自动机、后缀树
• 序列自动机

计算几何

基础

• 向量的点积、叉积
• 极角排序
• Graham扫描法
• 二维最近点对
• 最小覆盖圆
• 圆面积并
• ……
• 计算几何的题目各种各样

进阶

• 半平面交
• 旋转卡壳
• 三维凸包
• ……
• 计算几何的题目各种各样

杂

博弈

一些经典的博弈、SG函数、必胜必败态搜索

STL

vector、set/mutiset、map、queue、stack、deque、string、rope…

排序

虽然都用sort但是堆排序的原理还是要知道的

分治

普通的分治

CDQ分治

整体二分

树分治

二分、三分

2-points

01分数规划

构造

树的同构（树的hash）

莫队算法、[树上莫队]

找规律、打表