ACM技能表

看看就好了(滑稽)

数据结构

栈

1. 栈
2. 单调栈

队列

1. 一般队列
2. 优先队列/单调队列
3. 循环队列
4. 双端队列

链表

1. 一般链表
2. 循环链表
3. 双向链表
4. 块状链表
5. 十字链表

邻接表/邻接矩阵

1. 邻接表
2. 邻接多重表

Hash表(哈希表)

1. Hash表
2. 字符串Hash

二叉树

1. 一般二叉树
2. 遍历二叉树

• [ ] 先序遍历二叉树
• [ ] 中序遍历二叉树
• [ ] 后序遍历二叉树

1. Huffman树(赫夫曼树)(最优二叉树)
2. Huffman编码(赫夫曼编码)
3. 二叉查找树/二叉排序树/二叉搜索树

• [ ] Treap
• [ ] 伸展树

1. 线索二叉树
2. 平衡二叉树

堆

1. 大/小根堆（优先队列）
2. 可并堆
3. 左偏堆

线段树

1. 一维线段树
2. 延迟标记
3. 二维线段树
4. 区间合并
5. 区间离散化/压缩
6. 扫描线
7. 线段树套平衡树
8. 主席树/可持久化线段树

树状数组

1. 一维树状数组

• [ ] 单点查询+区间修改
• [ ] 区间查询+单点修改
• [ ] 区间查询+区间修改

1. 二维树状数组

• [ ] 单点查询+区间修改
• [ ] 区间查询+单点修改
• [ ] 区间查询+区间修改

1. N维树状数组
2. 逆序对问题

字符串

1. 回文字符串

• [ ] 判断
• [ ] 最长回文子串
  • [ ] 朴素O(n3)
  • [ ] 中心扩散O(n2)
  • [ ] 动态规划O(n2)
  • [ ] Manacher算法(马拉车算法)O(n)

1. KMP算法
2. 最小表示法
3. 字典树/Trie树

• [ ] 静态建树
• [ ] 动态建树
• [ ] 可持久化Trie树

1. 后缀数组
2. 后缀树
3. 后缀自动机
4. Aho-Corasick自动机/AC自动机

并查集

1. 并查集
2. 路径压缩
3. 边带权并查集

分块

RMQ问题

1. 朴素
2. 线段树
3. ST表
4. RMQ标准算法

离散化

红黑树

跳跃表

图论

搜索

1. 深度优先遍历/DFS

• [ ] 深度优先遍历/DFS
• [ ] DFS序
• [ ] 迭代加深DFS(ID-DFS)
• [ ] 双向DFS

1. 广度优先遍历/BFS

• [ ] 广度优先遍历/BFS
• [ ] 双端队列BFS
• [ ] 优先队列BFS
• [ ] 多起点BFS
• [ ] 双重BFS
• [ ] 双向BFS

1. 剪枝
2. 拓扑排序
3. 状态压缩
4. A*算法
5. IDA*算法
6. 记忆化搜索

强连通分量

1. 强连通分量

• [ ] Tarjan算法
• [ ] Korasaju算法

1. 双连通分量
2. 强连通分支及其缩点
3. 图的割边和割点
4. 2-SAT问题
5. 欧拉路问题

• [ ] 欧拉路径
• [ ] 欧拉回路

1. 哈密顿回路

最小生成树

1. Prim算法
2. Kruskal算法(稀疏图)
3. Sollin算法
4. 次小生成树

• [ ] Prim算法
• [ ] Kruskal算法+LCA

1. 最小有向生成树
2. 第k小生成树
3. 最优比例生成树
4. 最小树形图
5. 最小瓶颈生成树

• [ ] 最小瓶颈生成树
• [ ] 每对结点间最小瓶颈路

1. 最小瓶颈路
2. 最小度限制生成树
3. 增量最小生成树
4. 平面点的欧几里德最小生成树
5. 平面点的曼哈顿最小生成树
6. 最小平衡生成树

最短路径

1. 单源最短路径

• [ ] 有向无环图的最短路径

  • [ ] 拓扑排序

• [ ] 非负权值加权图的最短路径

  • [ ] Dijkstra算法
  • [ ] Dijkstra算法(二叉堆优化)
• [ ] 含负权值加权图的最短路径
  • [ ] Bellman-Ford算法
  • [ ] SPFA算法

1. 全源最短最短路径

• [ ] Floyd算法
• [ ] Johnson算法

1. 次短路径
2. 第k短路径
3. 差分约束系统
4. 平面点对的最短路径(优化)
5. 双标准限制最短路径

环

1. 环判定
2. 负环判定

• [ ] Bellman-Ford算法
• [ ] SPFA算法

网络流

1. 最大流问题

• [ ] 增广路算法

  • [ ] 增广路定理
  • [ ] Ford-Fulkerson算法
  • [ ] Ford-Fulkerson迭加算法
  • [ ] Edmond-Karp算法
  • [ ] Dinic算法
  • [ ] ISAP算法/最短增广路算法

• [ ] 预流推进算法

1. 最小割最大流定理

• [ ] 多源多汇问题
• [ ] 无源无汇有容量下界网络的可行流
• [ ] 有容量下界网络的s-t最大/最小流
• [ ] 节点有限制的网络流

1. 最小费用最大流问题

• [ ] 容量不固定的s-t最小费用流
• [ ] 含负费用的最小费用最大流
• [ ] 费用与流量平方成正比的最小流

二分图匹配

1. 二分图判定
2. 二分图最大匹配

• [ ] 匈牙利算法

1. Konig定理
2. 二分图最小点覆盖

• [ ] 匈牙利算法

1. 二分图最小边覆盖
2. 二分图最佳完美匹配

• [ ] Kuhn-Munkres算法

1. 二分图完全匹配

• [ ] Kuhn-Munkres算法

1. 二分图多重匹配
2. 二分图带权最大匹配

• [ ] Kuhn-Munkres算法

1. 二分图最大独立集
2. 最大闭合子图
3. 最大密度子图
4. 公平分配问题
5. 区间k覆盖问题
6. 有向无环图(DAG)的最小路径覆盖

• [ ] DAG的最小不相交路径覆盖
• [ ] DAG的最小可相交路径覆盖

树的直径

1. 树形DP
2. BFS

基环树

最近公共祖先

1. 向上标记法
2. 树上倍增
3. Tarjan 算法
4. LCA 转 RMQ

弦图

稳定婚姻问题

动态规划

四边形不等式理论

不完全状态记录

1. 青蛙过河问题
2. 区间DP

背包问题

1. 0-1背包
2. 完全背包
3. 分组背包
4. 多重背包
5. 判定性背包问题
6. 带附属关系的背包问题
7. + -1背包问题
8. 双背包求最优值
9. 构造三角形问题
10. 带上下界限制的背包问题(012背包)

线性的动态规划问题

1. 积木游戏问题
2. 决斗（判定性问题）
3. 圆的最大多边形问题
4. 统计单词个数问题
5. 棋盘分割
6. 日程安排问题
7. 最***近问题(求出两数之比最接近某数/两数之和等于某数等等)
8. 方块消除游戏(某区间可以连续消去求最大效益)
9. 资源分配问题
10. 数字三角形问题
11. 漂亮的打印
12. 邮局问题与构造答案
13. 最高积木问题
14. 两段连续和最大
15. 2次幂和问题
16. N个数的最大M段子段和
17. 交叉最大数问题

判定性问题的DP(如判定整除、判定可达性等)

1. 模K问题的DP
2. 特殊的模K问题，求最大(最小)模K的数
3. 变换数问题

单调性优化的动态规划

1. 1-SUM问题
2. 2-SUM问题
3. 序列划分问题(单调队列优化)

剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)

1. 凸多边形的三角剖分问题
2. 乘积最大问题
3. 多边形游戏(多边形边上是操作符,顶点有权值)
4. 石子合并(N^3/N^2/NLogN各种优化)

贪心的动态规划

1. 最优装载问题
2. 部分背包问题
3. 乘船问题
4. 贪心策略
5. 双机调度问题Johnson算法

区间DP

数位DP

状态DP

1. 牛仔射击问题(博弈类)
2. 哈密顿路径的状态dp
3. 两支点天平平衡问题
4. 一个有向图的最接近二部图

树型DP

1. 完美服务器问题(每个节点有3种状态)
2. 小胖守皇宫问题
3. 网络收费问题
4. 树中漫游问题
5. 树上的博弈
6. 树的最大独立集问题
7. 树的最大平衡值问题
8. 构造树的最小环

数学

数论

1. 积性函数
2. 佩尔方程
3. 同余

• [ ] 同余定理
• [ ] 费马小定理
• [ ] 欧拉定理
• [ ] 欧拉定里推论
• [ ] 扩展欧几里得算法
• [ ] 中国剩余定理
• [ ] 乘法逆元

1. 素数

• [ ] 欧几里得定理
• [ ] 朴素法
• [ ] 筛选法
  • [ ] Eratosthenes筛选法
  • [ ] 线性筛
• [ ] 米勒测试法

1. 约数/因数/因子
2. 连分数逼近
3. 循环群生成元
4. 进制位

矩阵

1. 矩阵乘法
2. 矩阵快速幂
3. 矩阵转置

组合数学

1. 排列组合
2. 容斥原理
3. 递推关系和生成函数
4. Lucas定理
5. Polya计数法
6. N皇后构造解
7. 幻方的构造
8. Catalan数列
9. Stirling数列
10. 斐波拉契数
11. 调和数
12. 连分数
13. MoBius
14. 偏序关系理论

计算几何

1. 基本公式
2. 线段
3. 多边形
4. 三角形
5. 圆
6. 球
7. 可视图的建立
8. 对踵点
9. 经典问题

计算方法

1. 二分法
2. 迭代法
3. 三分法
4. 快速幂
5. 解线性方程组
6. 解模线性方程组
7. 定积分计算
8. 多项式求根
9. 周期性方程
10. 线性规划
11. 快速傅立叶变换
12. 随机算法
13. 0/1分数规划
14. 迭代逼近
15. 矩阵法

概率论

1. 全概率公式
2. 数学期望

博弈论

1. SG函数
2. 极大极小过程
3. Nim问题