圖論
路徑問題
最短路徑
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)