競程技能樹 - HackMD

###### tags: `Competitive Programming` # 競程技能樹 <style> .lv1 { color: #bf0b0b; } .lv2 { color: #cf7a0c; } .lv3 { color: #b5af00; } .lv4 { color: #078c1f; } </style> ## 等級 ◆ = 連聽都沒聽過。 ◆ = 知道在幹嘛，但不會寫 or 沒寫過。 ◆ = 實作過一兩次，現在寫還是會很卡。 ◆ = 已經寫過很多次，但還需要多練習題目。 ## 知識 ### 實用技巧 ◆ 掃描線 ◆ 位元運算 ◆ 前綴和 ◆ 差分 ◆ 雙指標 ◆ 倍增法 ◆ 離散化 ◆ I/O優化 ◆ 壓常：#pragma、static、branch predictor ◆ #define／template／operator overload ◆ 啟發式合併 ### STL/PBDS ◆ vector ◆ queue、stack、deque ◆ set、map、unordered_set、unordered_map、priority_queue ◆ pair ◆ tuple ◆ 黑魔法 (\_\_gnu_pbds) - tree - 可合併priority_queue ### 排序與搜尋 ◆ comparator ◆ 二分搜、三分搜、三分搜轉二分搜 ◆ 二分搜實作細節 ◆ 對答案二分搜 ◆ 整體二分搜 ◆ bubble sort、insertion sort ◆ merge sort、quick sort ◆ counting sort、radix sort ### 枚舉 ◆ 枚舉排列、組合 ◆ $O(2^n)$ 枚舉子集 ◆ $O(3^n)$ 枚舉子集的子集 ◆ 折半枚舉 ### Greedy ◆ 習題 ### DP題型 ◆ 線性DP ◆ 路徑DP ◆ 背包DP ◆ 區間DP ◆ DAG DP ◆ DP 回溯 ◆ 機率/期望值DP ◆ 賽局DP ◆ 數位DP ◆ 位元DP ◆ 輪廓線DP ◆ 插頭DP ### DP優化 ◆ 前綴優化 ◆ 單調隊列優化 ◆ 矩陣快速冪優化 ◆ 資料結構優化 ◆ SOS 位元DP優化 ◆ 1D/1D 凹/凸優化 ◆ 2D/1D 優化 ◆ 分治優化 ◆ 斜率優化 ◆ Aliens 優化 ◆ Slope Trick ◆ SMAWK 優化  ### 圖論 I：Basic Knowledge ◆ DFS、BFS ◆ 並查集 ◆ 拓樸排序 ◆ Bellman-Ford ◆ SPFA ◆ Dijkstra (Sparse Graph) ◆ Dijkstra (Dense Graph) ◆ Floyd-Warshall ◆ 分層Dijkstra ◆ Eulerian Path ◆ Hamilton Path ◆ 差分約束系統 ◆ 同餘最短路 ### 圖論 II：Basic Tree Knowledge ◆ 樹直徑 ◆ 樹重心 ◆ 樹 DP ◆ Prim (Sparse Graph) ◆ Prim (Dense Graph) ◆ Kruskal ◆ 倍增 LCA ◆ Tarjan $O(n)$ 離線 LCA ◆ 全方位木 DP ### 圖論 III：Tree Decomposition ◆ 樹壓平 ◆ 樹鏈剖分 ◆ 重心剖分 ### 圖論 IV：Connectivity ◆ DFS Tree ◆ 關節點、點BCC ◆ 橋、邊BCC ◆ SCC (Tarjan) ◆ SCC (Kosaraju) ◆ 2-SAT ### 圖論 V：Matching ◆ Berge's Lemma ◆ 匈牙利演算法 ◆ Hopcroft-Karp ◆ Kőnig's Theorem ◆ 最小點覆蓋 ◆ 最小邊覆蓋 ◆ 最大點獨立集 ◆ 最大邊獨立集 ◆ Hall's Marriage Theorem ◆ Kuhn-Munkres $O(|V|^4)$ ◆ Kuhn-Munkres $O(|V|^3)$ ### 圖論 VI：Flow ◆ 網路流名詞定義 ◆ 最大流／最小割 ◆ Edmonds-Karps Algorithm ◆ Dinic's Algorithm ◆ Dinic's Algorithm (ISAP 優化) ◆ MCMF ◆ 建模方法 ◆ 循環流、有上下界限制的流 ◆ Stoer-Wagner Algorithm ◆ Gomory-Hu Tree ### 圖論 VII：Miscellaneous ◆ 支配樹 ◆ 有向最小生成樹 ◆ Matroid ◆ Matroid Intersection ◆ Cycle Space／Cut Space  ### 分治／資料結構 ◆ 簡單線段樹 ◆ 懶標線段樹 ◆ 二維線段樹 ◆ 值域線段樹 ◆ 線段樹上二分搜 ◆ 動態開點線段樹 ◆ 持久化線段樹 ◆ 李超線段樹 ◆ 時間線段樹 ◆ 線段樹優化建圖 ◆ Pattern 線段樹 ◆ Segment Tree Beats ◆ BIT ◆ 差分BIT ◆ Sparse Table ◆ Merge-Split Treap ◆ 帶懶標 Merge-Split Treap ◆ 持久化 Merge-Split Treap ◆ CDQ 分治 ### 根號算法 ◆ 根號分 case ◆ 序列分塊 ◆ 樹分塊 ◆ 值域分塊 ◆ 數論分塊 ◆ 操作分塊 ◆ 莫隊算法 ◆ 帶修改莫隊算法 ◆ 回滾莫隊 ### 計算幾何 ◆ 向量定義、內積、外積 ◆ 方向判定、極角排序 ◆ 線段相交 ◆ 多邊形包含測試 ◆ 鞋帶公式 ◆ 凸包 (Andrew's Monotone Chain) ◆ 凸包 (Graham's Scan) ◆ 旋轉卡尺 ◆ Pick's Theorem ◆ 極角掃描線 ◆ 旋轉掃描線 ◆ Minkowski Sum ◆ 最小包覆圓 ◆ Voronoi Diagram ◆ 模擬退火 ◆ 多邊形聯集面積 ### 數學 #### 基礎數論 ◆ 線性質數篩 ◆ 輾轉相除法 ◆ 貝祖定理、擴展歐幾里得 ◆ 模逆元 ◆ 中國剩餘定理 ◆ 費馬小定理、歐拉定理 #### 進階數論 ◆ 原根 ◆ Miller-Rabin 質數檢驗法 ◆ Pollard's rho 因數分解法 ◆ 積性函數 ◆ Dirichlet's Convolution ◆ $φ, μ, ε, \mathbb{1}, \mathbb{id}$ 性質 ◆ 線性篩蓋積性函數 ◆ 莫比烏斯反演 ◆ 數論分塊 ◆ 杜教篩 #### 多項式／捲積／生成函數 ◆ FFT, NTT ◆ 多項式除法、帶餘除法 ◆ 多項式指數／對數 ◆ 多項式開根號 ◆ 牛頓法 ◆ 多項式多點求值 ◆ 多項式生成函數 ◆ 指數生成函數 ◆ Lagrange's Inversion Formula #### 線性代數 ◆ 矩陣乘法 ◆ 行列式 ◆ 高斯消去法 ◆ Xor Basis ◆ 線性規劃 ◆ Simplex Algorithm ◆ Duality #### 排列組合 / 經典題目 ◆ 排容原理 ◆ 重複組合 ◆ 巴斯卡三角形 ◆ 卡塔蘭數 ◆ 約瑟夫問題 ◆ Burnside's Lemma ### 組合賽局 ◆ 定義、分類 #### 標準無偏賽局 ◆ 賽局和、型別、等價賽局 ◆ Nim ◆ Choose Nim ◆ MEX Principle ◆ Sprague–Grundy Theorem #### 標準有偏賽局 ◆ Red-Blue-Hackenbush ◆ 二進分數 ◆ Simplicity Principle ### 字串 ◆ Rolling Hash ◆ Trie ◆ KMP ◆ Z-Value ◆ Manacher's Algorithm ◆ AC 自動機 ◆ Suffix Array ◆ Suffix BST ◆ 後綴自動機 (SAM) ### 隨機算法 ◆ 生日悖論 ◆ 失敗機率估算 ◆ Hash ◆ Color Coding ◆ 環狀序列鍊轉化 ◆ 最近點對 ◆ 最小包覆圓 ◆ 模擬退火 ◆ 最大團 ◆ TSP