###### tags: `Competitive Programming`
# 競程技能樹

<style>
.lv1 {
color: #bf0b0b;
}
.lv2 {
color: #cf7a0c;
}
.lv3 {
color: #b5af00;
}
.lv4 {
color: #078c1f;
}
</style>

## 等級
<span class="lv1">◆</span> = 連聽都沒聽過。
<span class="lv2">◆</span> = 知道在幹嘛，但不會寫 or 沒寫過。
<span class="lv3">◆</span> = 實作過一兩次，現在寫還是會很卡。
<span class="lv4">◆</span> = 已經寫過很多次，但還需要多練習題目。

## 知識
### 實用技巧
<span class="lv3">◆</span> 掃描線
<span class="lv4">◆</span> 位元運算
<span class="lv4">◆</span> 前綴和
<span class="lv4">◆</span> 差分
<span class="lv4">◆</span> 雙指標
<span class="lv4">◆</span> 倍增法
<span class="lv4">◆</span> 離散化
<span class="lv4">◆</span> I/O優化
<span class="lv2">◆</span> 壓常：#pragma、static、branch predictor
<span class="lv4">◆</span> #define／template／operator overload
<span class="lv4">◆</span> 啟發式合併

### STL/PBDS
<span class="lv4">◆</span> vector
<span class="lv4">◆</span> queue、stack、deque
<span class="lv4">◆</span> set、map、unordered_set、unordered_map、priority_queue
<span class="lv4">◆</span> pair
<span class="lv1">◆</span> tuple
<span class="lv4">◆</span> 黑魔法 (\_\_gnu_pbds)
- tree
- 可合併priority_queue

### 排序與搜尋
<span class="lv4">◆</span> comparator
<span class="lv4">◆</span> 二分搜、三分搜、三分搜轉二分搜
<span class="lv4">◆</span> 二分搜實作細節
<span class="lv4">◆</span> 對答案二分搜
<span class="lv3">◆</span> 整體二分搜
<span class="lv4">◆</span> bubble sort、insertion sort
<span class="lv4">◆</span> merge sort、quick sort
<span class="lv3">◆</span> counting sort、radix sort

### 枚舉
<span class="lv3">◆</span> 枚舉排列、組合
<span class="lv4">◆</span> $O(2^n)$ 枚舉子集
<span class="lv3">◆</span> $O(3^n)$ 枚舉子集的子集
<span class="lv4">◆</span> 折半枚舉

### Greedy
<span class="lv3">◆</span> 習題

### DP題型
<span class="lv4">◆</span> 線性DP
<span class="lv4">◆</span> 路徑DP
<span class="lv4">◆</span> 背包DP
<span class="lv4">◆</span> 區間DP
<span class="lv4">◆</span> DAG DP
<span class="lv3">◆</span> DP 回溯
<span class="lv3">◆</span> 機率/期望值DP
<span class="lv3">◆</span> 賽局DP
<span class="lv2">◆</span> 數位DP
<span class="lv4">◆</span> 位元DP
<span class="lv2">◆</span> 輪廓線DP
<span class="lv2">◆</span> 插頭DP

### DP優化
<span class="lv4">◆</span> 前綴優化
<span class="lv4">◆</span> 單調隊列優化
<span class="lv4">◆</span> 矩陣快速冪優化
<span class="lv3">◆</span> 資料結構優化
<span class="lv2">◆</span> SOS 位元DP優化
<span class="lv1">◆</span> 1D/1D 凹/凸優化
<span class="lv1">◆</span> 2D/1D 優化
<span class="lv1">◆</span> 分治優化
<span class="lv3">◆</span> 斜率優化
<span class="lv2">◆</span> Aliens 優化
<span class="lv1">◆</span> Slope Trick
<span class="lv1">◆</span> SMAWK

<!-- ============================================== -->
### 圖論 I：Basic Knowledge
<span class="lv4">◆</span> DFS、BFS
<span class="lv4">◆</span> 並查集
<span class="lv4">◆</span> 拓樸排序
<span class="lv4">◆</span> Bellman-Ford
<span class="lv4">◆</span> SPFA
<span class="lv4">◆</span> Dijkstra (Sparse Graph)
<span class="lv4">◆</span> Dijkstra (Dense Graph)
<span class="lv4">◆</span> Floyd-Warshall
<span class="lv4">◆</span> 分層Dijkstra
<span class="lv4">◆</span> Eulerian Path
<span class="lv4">◆</span> Hamilton Path
<span class="lv2">◆</span> 差分約束系統
<span class="lv2">◆</span> 同餘最短路

### 圖論 II：Basic Tree Knowledge
<span class="lv4">◆</span> 樹直徑
<span class="lv4">◆</span> 樹重心
<span class="lv4">◆</span> 樹 DP
<span class="lv4">◆</span> Prim (Sparse Graph)
<span class="lv4">◆</span> Prim (Dense Graph)
<span class="lv4">◆</span> Kruskal
<span class="lv4">◆</span> 倍增 LCA
<span class="lv2">◆</span> Tarjan $O(n)$ 離線 LCA
<span class="lv3">◆</span> 全方位木 DP

### 圖論 III：Tree Decomposition
<span class="lv2">◆</span> 樹壓平
<span class="lv1">◆</span> 樹鏈剖分
<span class="lv1">◆</span> 重心剖分

### 圖論 IV：Connectivity
<span class="lv3">◆</span> DFS Tree
<span class="lv2">◆</span> 關節點、點BCC
<span class="lv3">◆</span> 橋、邊BCC
<span class="lv3">◆</span> SCC (Tarjan)
<span class="lv3">◆</span> SCC (Kosaraju)
<span class="lv3">◆</span> 2-SAT

### 圖論 V：Matching
<span class="lv1">◆</span> Berge's Lemma
<span class="lv1">◆</span> 匈牙利演算法
<span class="lv1">◆</span> Hopcroft-Karp
<span class="lv1">◆</span> Kőnig's Theorem
<span class="lv1">◆</span> 最小點覆蓋
<span class="lv1">◆</span> 最小邊覆蓋
<span class="lv1">◆</span> 最大點獨立集
<span class="lv1">◆</span> 最大邊獨立集
<span class="lv1">◆</span> Hall's Marriage Theorem
<span class="lv1">◆</span> Kuhn-Munkres $O(|V|^4)$
<span class="lv1">◆</span> Kuhn-Munkres $O(|V|^3)$

### 圖論 VI：Flow
<span class="lv3">◆</span> 網路流名詞定義
<span class="lv3">◆</span> 最大流／最小割
<span class="lv2">◆</span> Edmonds-Karps Algorithm
<span class="lv2">◆</span> Dinic's Algorithm
<span class="lv1">◆</span> Dinic's Algorithm (ISAP 優化)
<span class="lv1">◆</span> MCMF
<span class="lv1">◆</span> 建模方法
<span class="lv1">◆</span> 循環流、有上下界限制的流
<span class="lv1">◆</span> Stoer-Wagner Algorithm
<span class="lv1">◆</span> Gomory-Hu Tree

### 圖論 VII：Miscellaneous
<span class="lv1">◆</span> 支配樹
<span class="lv1">◆</span> 有向最小生成樹
<span class="lv1">◆</span> Matroid
<span class="lv1">◆</span> Matroid Intersection
<span class="lv1">◆</span> Cycle Space／Cut Space

<!-- ============================================== -->

### 分治／資料結構
<span class="lv4">◆</span> 簡單線段樹
<span class="lv4">◆</span> 懶標線段樹
<span class="lv2">◆</span> 二維線段樹
<span class="lv4">◆</span> 值域線段樹
<span class="lv4">◆</span> 線段樹上二分搜
<span class="lv4">◆</span> 動態開點線段樹
<span class="lv2">◆</span> 持久化線段樹
<span class="lv3">◆</span> 李超線段樹
<span class="lv3">◆</span> 時間線段樹
<span class="lv3">◆</span> 線段樹優化建圖
<span class="lv2">◆</span> Pattern
<span class="lv3">◆</span> Segment Tree Beats
<span class="lv4">◆</span> BIT
<span class="lv4">◆</span> 差分BIT
<span class="lv4">◆</span> Sparse Table
<span class="lv2">◆</span> Merge-Split Treap
<span class="lv2">◆</span> 帶懶標 Merge-Split Treap
<span class="lv1">◆</span> 持久化 Merge-Split Treap
<span class="lv3">◆</span> CDQ 分治

### 根號算法
<span class="lv4">◆</span> 根號分 case
<span class="lv4">◆</span> 序列分塊
<span class="lv1">◆</span> 樹分塊
<span class="lv4">◆</span> 值域分塊
<span class="lv3">◆</span> 數論分塊
<span class="lv4">◆</span> 操作分塊
<span class="lv4">◆</span> 莫隊算法
<span class="lv4">◆</span> 帶修改莫隊算法
<span class="lv3">◆</span> 回滾莫隊

### 計算幾何
<span class="lv4">◆</span> 向量定義、內積、外積
<span class="lv4">◆</span> 方向判定、極角排序
<span class="lv4">◆</span> 線段相交
<span class="lv4">◆</span> 多邊形包含測試
<span class="lv4">◆</span> 鞋帶公式
<span class="lv4">◆</span> 凸包 (Andrew's Monotone Chain)
<span class="lv3">◆</span> 凸包 (Graham's Scan)
<span class="lv4">◆</span> 旋轉卡尺
<span class="lv3">◆</span> Pick's Theorem
<span class="lv1">◆</span> 極角掃描線
<span class="lv1">◆</span> 旋轉掃描線
<span class="lv1">◆</span> Minkowski Sum
<span class="lv1">◆</span> 最小包覆圓
<span class="lv1">◆</span> Voronoi Diagram
<span class="lv1">◆</span> 模擬退火
<span class="lv1">◆</span> 多邊形聯集面積

### 數學

#### 基礎數論
<span class="lv4">◆</span> 線性質數篩
<span class="lv4">◆</span> 輾轉相除法
<span class="lv3">◆</span> 貝祖定理、擴展歐幾里得
<span class="lv4">◆</span> 模逆元
<span class="lv1">◆</span> 中國剩餘定理
<span class="lv4">◆</span> 費馬小定理、歐拉定理

#### 進階數論
<span class="lv1">◆</span> 原根
<span class="lv1">◆</span> Miller-Rabin 質數檢驗法
<span class="lv1">◆</span> Pollard's rho 因數分解法
<span class="lv1">◆</span> 積性函數
<span class="lv1">◆</span> Dirichlet's Convolution
<span class="lv1">◆</span> $φ, μ, ε, \mathbb{1}, \mathbb{id}$ 性質
<span class="lv1">◆</span> 線性篩蓋積性函數
<span class="lv1">◆</span> 莫比烏斯反演
<span class="lv3">◆</span> 數論分塊
<span class="lv1">◆</span> 杜教篩

#### 多項式／捲積／生成函數
<span class="lv1">◆</span> FFT, NTT
<span class="lv1">◆</span> 多項式除法、帶餘除法
<span class="lv1">◆</span> 多項式指數／對數
<span class="lv1">◆</span> 多項式開根號
<span class="lv1">◆</span> 牛頓法
<span class="lv1">◆</span> 多項式多點求值
<span class="lv1">◆</span> 多項式生成函數
<span class="lv1">◆</span> 指數生成函數
<span class="lv1">◆</span> Lagrange's Inversion Formula

#### 線性代數
<span class="lv4">◆</span> 矩陣乘法
<span class="lv3">◆</span> 行列式
<span class="lv3">◆</span> 高斯消去法
<span class="lv1">◆</span> Xor Basis
<span class="lv3">◆</span> 線性規劃
<span class="lv3">◆</span> Simplex Algorithm
<span class="lv2">◆</span> Duality

#### 排列組合 / 經典題目
<span class="lv4">◆</span> 排容原理
<span class="lv4">◆</span> 重複組合
<span class="lv4">◆</span> 巴斯卡三角形
<span class="lv4">◆</span> 卡塔蘭數
<span class="lv4">◆</span> 約瑟夫問題
<span class="lv3">◆</span> Burnside's Lemma

### 組合賽局
<span class="lv4">◆</span> 定義、分類
#### 標準無偏賽局
<span class="lv4">◆</span> 賽局和、型別、等價賽局
<span class="lv4">◆</span> Nim
<span class="lv4">◆</span> Choose Nim
<span class="lv4">◆</span> MEX Principle
<span class="lv4">◆</span> Sprague–Grundy Theorem
#### 標準有偏賽局
<span class="lv2">◆</span> Red-Blue-Hackenbush
<span class="lv2">◆</span> 二進分數
<span class="lv1">◆</span> Simplicity Principle

### 字串
<span class="lv4">◆</span> Rolling Hash
<span class="lv2">◆</span> Trie
<span class="lv3">◆</span> KMP
<span class="lv3">◆</span> Z-Value
<span class="lv2">◆</span> Manacher's Algorithm
<span class="lv1">◆</span> AC 自動機
<span class="lv3">◆</span> Suffix Array
<span class="lv1">◆</span> Suffix BST
<span class="lv1">◆</span> 後綴自動機 (SAM)

### 隨機算法
<span class="lv3">◆</span> 生日悖論
<span class="lv3">◆</span> 失敗機率估算
<span class="lv2">◆</span> Hash
<span class="lv2">◆</span> Color Coding
<span class="lv1">◆</span> 環狀序列鍊轉化
<span class="lv1">◆</span> 最近點對
<span class="lv1">◆</span> 最小包覆圓
<span class="lv1">◆</span> 模擬退火
<span class="lv1">◆</span> 最大團
<span class="lv1">◆</span> TSP