---
# System prepended metadata

title: 競程技能樹
tags: [Competitive Programming]

---

###### 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="lv1">◆</span> 掃描線
<span class="lv4">◆</span> 位元運算
<span class="lv4">◆</span> 前綴和
<span class="lv3">◆</span> 差分
<span class="lv2">◆</span> 雙指標
<span class="lv2">◆</span> 倍增法
<span class="lv1">◆</span> 離散化
<span class="lv4">◆</span> I/O優化
<span class="lv1">◆</span> 壓常：#pragma、static、branch predictor
<span class="lv4">◆</span> #define／template／operator overload -----overload不太會使用
<span class="lv1">◆</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="lv4">◆</span> tuple
<span class="lv3">◆</span> 黑魔法 (\_\_gnu_pbds)
- tree
- 可合併priority_queue


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


### 枚舉
<span class="lv4">◆</span> 枚舉排列、組合
<span class="lv1">◆</span> $O(2^n)$ 枚舉子集 ---我不知道這是什麼
<span class="lv1">◆</span> $O(3^n)$ 枚舉子集的子集 ---我也不知道這什麼
<span class="lv1">◆</span> 折半枚舉 ---更不知道


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


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


### DP優化 -----我連DP都不會要他幹嘛XD
<span class="lv1">◆</span> 前綴優化
<span class="lv1">◆</span> 單調隊列優化
<span class="lv1">◆</span> 矩陣快速冪優化
<span class="lv1">◆</span> 資料結構優化
<span class="lv1">◆</span> SOS 位元DP優化
<span class="lv1">◆</span> 1D/1D 凹/凸優化
<span class="lv1">◆</span> 2D/1D 優化
<span class="lv1">◆</span> 斜率優化
<span class="lv1">◆</span> Aliens 優化
<span class="lv1">◆</span> slope trick
<span class="lv1">◆</span> SMAWK


### 基礎圖論
<span class="lv4">◆</span> DFS、BFS
<span class="lv2">◆</span> 並查集
<span class="lv2">◆</span> 拓樸排序
<span class="lv1">◆</span> Bellman-Ford
<span class="lv2">◆</span> SPFA
<span class="lv2">◆</span> Dijkstra
<span class="lv1">◆</span> Floyd-Warshall
<span class="lv1">◆</span> 分層Dijkstra
<span class="lv1">◆</span> Eulerian Path
<span class="lv1">◆</span> Hamilton Path


### 基礎樹論
<span class="lv3">◆</span> 樹直徑
<span class="lv1">◆</span> 樹重心
<span class="lv1">◆</span> 樹 DP
<span class="lv1">◆</span> Prim (Sparse Graph)
<span class="lv1">◆</span> Prim (Dense Graph)
<span class="lv2">◆</span> Kruskal
<span class="lv2">◆</span> LCA
<span class="lv1">◆</span> 全方位木 DP


### 進階圖論
<span class="lv1">◆</span> 差分約束系統
<span class="lv1">◆</span> 同餘最短路
<span class="lv1">◆</span> DFS Tree
<span class="lv1">◆</span> 關節點、點BCC
<span class="lv1">◆</span> 橋、邊BCC
<span class="lv1">◆</span> SCC (Tarjan)
<span class="lv1">◆</span> SCC (Kosaraju)
<span class="lv1">◆</span> 2-SAT
<span class="lv1">◆</span> 不帶權二分圖匹配
<span class="lv1">◆</span> 帶權二分圖匹配
<span class="lv1">◆</span> Matroid
<span class="lv1">◆</span> Cycle Space／Cut Space


### 進階樹論
<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> Edmonds-Karps Algorithm
<span class="lv1">◆</span> Dinic's Algorithm
<span class="lv1">◆</span> MCMF
<span class="lv1">◆</span> 建模方法


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


### 根號算法
<span class="lv1">◆</span> 根號分 case
<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> 回滾莫隊


### 計算幾何
<span class="lv3">◆</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> Pick's Theorem
<span class="lv1">◆</span> 極角掃描線
<span class="lv1">◆</span> 旋轉掃描線
<span class="lv1">◆</span> Minkowski Sum


### 數學
#### 離散數論
<span class="lv4">◆</span> 線性質數篩
<span class="lv2">◆</span> 輾轉相除法 ---知道沒用過
<span class="lv1">◆</span> 貝祖定理、擴展歐幾里得
<span class="lv3">◆</span> 模逆元
<span class="lv1">◆</span> 中國剩餘定理
<span class="lv2">◆</span> 費馬小定理、歐拉定理
<span class="lv1">◆</span> 莫比烏斯反演
<span class="lv1">◆</span> 生成函數
<span class="lv2">◆</span> FFT, NTT
#### 線性代數
<span class="lv4">◆</span> 矩陣、行列式
<span class="lv2">◆</span> 高斯消去法 ---還沒教不會
#### 排列組合 / 經典題目
<span class="lv4">◆</span> 排容原理
<span class="lv3">◆</span> 重複組合
<span class="lv4">◆</span> 巴斯卡三角形
<span class="lv3">◆</span> 卡塔蘭數
<span class="lv4">◆</span> 約瑟夫問題
<span class="lv1">◆</span> Burnside's Lemma


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


### 字串
<span class="lv1">◆</span> Rolling Hash
<span class="lv1">◆</span> Trie
<span class="lv1">◆</span> KMP
<span class="lv1">◆</span> Z-Value
<span class="lv1">◆</span> Manacher's Algorithm
<span class="lv1">◆</span> AC自動機
<span class="lv1">◆</span> Suffix Array


### 隨機算法
<span class="lv1">◆</span> Color Coding
<span class="lv2">◆</span> Hash
<span class="lv1">◆</span> 失敗機率估算
<span class="lv1">◆</span> 生日悖論
