###### 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
Last changed by  
 
71630 Penguin Hello, world!
688

Read more

03/04 電影團

時間軸 集合時間：待定 行程選項 電影 :::success 鈴芽之旅 ::: :::info

3/3/2023
競賽／教學經歷

競賽經歷 2020 資訊之芽 一階結業 2021 資訊之芽 兩階段優秀結業 2021 TOI 初選 29 名 2021 北市賽三等獎 2021 NPSC 網路賽 17 名 2022 ICPC Regional 銀獎 APCS 5/5 CF Max Rating 1899

12/16/2022
PPT 弄數學公式

插入方程式 alt + = 輸入數學指令後按一下 space 就可以得到指令的效果，如果沒有出現代表 PPT 不支援該語法，以下會列出常見的指令。 上下標 上標：^（例：輸入 a^k 後按 space 即可呈現 $a^k$） 下標：_（例：輸入 a_k 後按 space 即可呈現 $a_k$）

10/28/2022
Overleaf 使用方法

Overleaf 介紹 LaTeX 是一款非常好用的文件編輯器，透過類似寫程式的編輯方式，可以弄出很漂亮的數學式還有自動弄出整齊的排版。Overleaf 是最主流的 LaTeX 線上編輯器。推薦大家有空學 > < 做報告真的很方便。 共編連結 https://www.overleaf.com/2228648893cxncjkcdjyzg 調整環境 Overleaf 整體介面長這樣： 點左上角的 Menu 可以進入環境設定：

9/26/2022
Read more from 71630 Penguin
Published on HackMD