图论
路径问题
最短路径
0/1边权最短路径
BFS
非负边权最短路径
Dijkstra
*** 可以用Dijkstra解决的问题的特征
负边权最短路径
Bellman-Ford
*** Bellman-Ford的Yen-氏优化
*** 差分约束系统
Floyd
*** 广义路径问题
*** 传递闭包
*** 极小极大距离 / 极大极小距离
Euler Path / Tour
圈套圈算法
混合图的 Euler Path / Tour
Hamilton Path / Tour
特殊图的Hamilton Path / Tour 构造
生成树问题
最小生成树
第k小生成树
最优比率生成树
*** 0/1分数规划
度限制生成树
连通性问题
*** 强大的DFS算法
无向图连通性
割点
割边
二连通分支
有向图连通性
强连通分支
*** 2-SAT
*** 最小点基
有向无环图
拓扑排序
*** 有向无环图与动态规划的关系
二分图匹配问题
*** 一般图问题与二分图问题的转换思路
最大匹配
*** 有向图的最小路径覆盖
*** 0 / 1矩阵的最小覆盖
完备匹配
最优匹配
网络流问题
*** 网络流模型的简单特征和与线性规划的关系
最大流最小割定理
最大流问题
有上下界的最大流问题
*** 循环流
最小费用最大流 / 最大费用最大流
弦图的性质和判定
组合数学
*** 解决组合数学问题时常用的思想
*** 逼近
*** 递推 / 动态规划
概率问题
Polya定理
计算几何 / 解析几何
*** 计算几何的核心：叉积 / 面积
*** 解析几何的主力：复数
基本形
点
直线，线段
多边形
凸多边形 / 凸包
*** 凸包算法的引进，卷包裹法
Graham扫描法
*** 水平序的引进，共线凸包的补丁
完美凸包算法
相关判定
两直线相交
两线段相交
点在任意多边形内的判定
点在凸多边形内的判定
经典问题
最小外接圆
近似O(n)的最小外接圆算法
点集直径
旋转卡壳，对踵点
多边形的三角剖分
数学 / 数论
最大公约数
Euclid算法
扩展的Euclid算法
同余方程 / 二元一次不定方程
同余方程组
线性方程组
高斯消元法
*** 解mod 2域上的线性方程组
*** 整系数方程组的精确解法
矩阵
行列式的计算
*** 利用矩阵乘法快速计算递推关系
分数
分数树
连分数逼近
数论计算
求N的约数个数
求phi(N)
求约数和
……
素数问题
概率判素算法
概率因子分解
数据结构：
组织结构
二叉堆
左偏树
胜者树
Treap
统计结构
树状数组
虚二叉树
线段树
*** 矩形面积并
*** 圆形面积并
关系结构
Hash表
并查集
*** 路径压缩思想的应用
STL中的数据结构
vector
deque
set / map
动态规划 / 记忆化搜索
*** 动态规划和记忆化搜索在思考方式上的区别
最长子序列系列问题
最长不下降子序列
最长公共子序列
一类NP问题的动态规划解法
树型动态规划
背包问题
动态规划的优化
*** 四边形不等式
*** 状态设计
*** 规划方向（？）
常用思想
二分
最小表示法
ACM需要掌握的知识
对ACM竞赛的算法大概分了一下类，分成了数学、数据结构和算法三大块。
一 数学(Mathematics)
1 离散数学(Discrete Mathematics)
1.1 图论(Graph Theory)
图的遍历(Graph Traversal): DFS, BFS
最小生成树(Minimum Spanning Tree): Prim, Kruskal
最短路径(Shortest Path): Dijkstra, Floyd
传递闭包(Transitive Closure)
关节点(Articulation Point - UndiGraph)
拓扑排序(Topological Sort - AOV-Network)
关键路径(Critical Path - AOE-Network)
回路问题: 欧拉路(Euler Path), 汉密尔顿回路(Hamilton Tour)
差分约束(Difference Constraints): Bellman-Ford
二部图匹配(Bipartite Matching)
网络流(Network Flow)
...
1.2 组合数学(Combinatorics)
2 数论(Number Theory)
2.1 素数: GCD, LCM...
2.2 同余
3 计算几何(Computational Geometry)
线段相交, 多边形面积, 内点外点的判断, 凸包(Convex Hull), 重心(Bary Center)...
4 线性代数
矩阵(Matrix), 线性方程组(Linear Equations)...
5 概率论
6 初等数学与解析几何
7 高等数学
点积(Dot Product), 差积(Cross Product), 积分(Integral), 微分(Differential)...
二 数据结构(Data Structure)
1 线性结构
线性表(Linear List)
栈(Stack), 队列(Queue)
数组(Array), 串(String), 广义表(General List)
2 非线性结构
树(Tree)
堆(Heap)
图(Graph)
3 排序
3.1 插入排序
直接插入排序(Insert Sort) O(n^2)
折半插入排序(Binary Insert Sort)
希尔排序(Shell Sort)
3.2 交换排序
冒泡排序(Bubble Sort) O(n^2)
快速排序(Quick Sort)?? O(nlogn)
3.3 选择排序
直接选择排序(Select Sort) O(n^2)
锦标赛排序(Tournament Sort) O(nlogn)
堆排序(Heap Sort) O(nlogn)
3.4 归并排序(Merge Sort) O(nlogn)
3.5 基数排序(Radix Sort) O(d(n+radix))
4 查找
4.1 二分(Binary Search)
4.2 树型
二叉搜索树(Binary Search Tree)
平衡搜索树(AVL Tree)
并查集(Union-Find Set)
4.3 哈希(Hashing)
三 算法(Algorithm)
1 模拟算法
2 搜索算法
2.1 枚举搜索(Enumeration)
2.2 深度优先(Depth First Search)
2.3 广度优先(Breadth First Search)
2.4 启发式搜索(Heuristic Search)
3 以“相似或相同子问题”为核心的算法
3.1 递推
3.2 递归(Recursion)
3.3 贪心法(Greedy)
3.4 动态规划(Dynamic Programming)