圖論
路徑問題
最短路徑
0/1邊權(quán)最短路徑
BFS
非負(fù)邊權(quán)最短路徑
Dijkstra
*** 可以用Dijkstra解決的問題的特征
負(fù)邊權(quán)最短路徑
Bellman-Ford
*** Bellman-Ford的Yen-氏優(yōu)化
*** 差分約束系統(tǒng)
Floyd
*** 廣義路徑問題
*** 傳遞閉包
*** 極小極大距離 / 極大極小距離
Euler Path / Tour
圈套圈算法
混合圖的 Euler Path / Tour
Hamilton Path / Tour
特殊圖的Hamilton Path / Tour 構(gòu)造
生成樹問題
最小生成樹
第k小生成樹
最優(yōu)比率生成樹
*** 0/1分?jǐn)?shù)規(guī)劃
度限制生成樹
連通性問題
*** 強(qiáng)大的DFS算法
無向圖連通性
割點(diǎn)
割邊
二連通分支
有向圖連通性
強(qiáng)連通分支
*** 2-SAT
*** 最小點(diǎn)基
有向無環(huán)圖
拓?fù)渑判?br />
*** 有向無環(huán)圖與動態(tài)規(guī)劃的關(guān)系
二分圖匹配問題
*** 一般圖問題與二分圖問題的轉(zhuǎn)換思路
最大匹配
*** 有向圖的最小路徑覆蓋
*** 0 / 1矩陣的最小覆蓋
完備匹配
最優(yōu)匹配
網(wǎng)絡(luò)流問題
*** 網(wǎng)絡(luò)流模型的簡單特征和與線性規(guī)劃的關(guān)系
最大流最小割定理
最大流問題
有上下界的最大流問題
*** 循環(huán)流
最小費(fèi)用最大流 / 最大費(fèi)用最大流
弦圖的性質(zhì)和判定
組合數(shù)學(xué)
*** 解決組合數(shù)學(xué)問題時常用的思想
*** 逼近
*** 遞推 / 動態(tài)規(guī)劃
概率問題
Polya定理
計算幾何 / 解析幾何
*** 計算幾何的核心：叉積 / 面積
*** 解析幾何的主力：復(fù)數(shù)
基本形
點(diǎn)
直線，線段
多邊形
凸多邊形 / 凸包
*** 凸包算法的引進(jìn)，卷包裹法
Graham掃描法
*** 水平序的引進(jìn)，共線凸包的補(bǔ)丁
完美凸包算法
相關(guān)判定
兩直線相交
兩線段相交
點(diǎn)在任意多邊形內(nèi)的判定
點(diǎn)在凸多邊形內(nèi)的判定
經(jīng)典問題
最小外接圓
近似O(n)的最小外接圓算法
點(diǎn)集直徑
旋轉(zhuǎn)卡殼，對踵點(diǎn)
多邊形的三角剖分
數(shù)學(xué) / 數(shù)論
最大公約數(shù)
Euclid算法
擴(kuò)展的Euclid算法
同余方程 / 二元一次不定方程
同余方程組
線性方程組
高斯消元法
*** 解mod 2域上的線性方程組
*** 整系數(shù)方程組的精確解法
矩陣
行列式的計算
*** 利用矩陣乘法快速計算遞推關(guān)系
分?jǐn)?shù)
分?jǐn)?shù)樹
連分?jǐn)?shù)逼近
數(shù)論計算
求N的約數(shù)個數(shù)
求phi(N)
求約數(shù)和
……
素數(shù)問題
概率判素算法
概率因子分解
數(shù)據(jù)結(jié)構(gòu)：
組織結(jié)構(gòu)
二叉堆
左偏樹
勝者樹
Treap
統(tǒng)計結(jié)構(gòu)
樹狀數(shù)組
虛二叉樹
線段樹
*** 矩形面積并
*** 圓形面積并
關(guān)系結(jié)構(gòu)
Hash表
并查集
*** 路徑壓縮思想的應(yīng)用
STL中的數(shù)據(jù)結(jié)構(gòu)
vector
deque
set / map
動態(tài)規(guī)劃 / 記憶化搜索
*** 動態(tài)規(guī)劃和記憶化搜索在思考方式上的區(qū)別
最長子序列系列問題
最長不下降子序列
最長公共子序列
一類NP問題的動態(tài)規(guī)劃解法
樹型動態(tài)規(guī)劃
背包問題
動態(tài)規(guī)劃的優(yōu)化
*** 四邊形不等式
*** 狀態(tài)設(shè)計
*** 規(guī)劃方向（？）
常用思想
二分
最小表示法
ACM需要掌握的知識
對ACM競賽的算法大概分了一下類，分成了數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)和算法三大塊。
一 數(shù)學(xué)(Mathematics)
1 離散數(shù)學(xué)(Discrete Mathematics)
1.1 圖論(Graph Theory)
圖的遍歷(Graph Traversal): DFS, BFS
最小生成樹(Minimum Spanning Tree): Prim, Kruskal
最短路徑(Shortest Path): Dijkstra, Floyd
傳遞閉包(Transitive Closure)
關(guān)節(jié)點(diǎn)(Articulation Point - UndiGraph)
拓?fù)渑判?Topological Sort - AOV-Network)
關(guān)鍵路徑(Critical Path - AOE-Network)
回路問題: 歐拉路(Euler Path), 漢密爾頓回路(Hamilton Tour)
差分約束(Difference Constraints): Bellman-Ford
二部圖匹配(Bipartite Matching)
網(wǎng)絡(luò)流(Network Flow)
...
1.2 組合數(shù)學(xué)(Combinatorics)
2 數(shù)論(Number Theory)
2.1 素數(shù): GCD, LCM...
2.2 同余
3 計算幾何(Computational Geometry)
線段相交, 多邊形面積, 內(nèi)點(diǎn)外點(diǎn)的判斷, 凸包(Convex Hull), 重心(Bary Center)...
4 線性代數(shù)
矩陣(Matrix), 線性方程組(Linear Equations)...
5 概率論
6 初等數(shù)學(xué)與解析幾何
7 高等數(shù)學(xué)
點(diǎn)積(Dot Product), 差積(Cross Product), 積分(Integral), 微分(Differential)...
二 數(shù)據(jù)結(jié)構(gòu)(Data Structure)
1 線性結(jié)構(gòu)
線性表(Linear List)
棧(Stack), 隊列(Queue)
數(shù)組(Array), 串(String), 廣義表(General List)
2 非線性結(jié)構(gòu)
樹(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)
錦標(biāo)賽排序(Tournament Sort) O(nlogn)
堆排序(Heap Sort) O(nlogn)
3.4 歸并排序(Merge Sort) O(nlogn)
3.5 基數(shù)排序(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 深度優(yōu)先(Depth First Search)
2.3 廣度優(yōu)先(Breadth First Search)
2.4 啟發(fā)式搜索(Heuristic Search)
3 以“相似或相同子問題”為核心的算法
3.1 遞推
3.2 遞歸(Recursion)
3.3 貪心法(Greedy)
3.4 動態(tài)規(guī)劃(Dynamic Programming)