基礎

#

入門知識

#

• 輸入輸出
• 變數、資料型態
• 運算子
  • 算術、關係、邏輯、位元、賦值、條件運算子
  • 指標與引用
• 判斷式
  • if / else
  • switch
• 迴圈
  • for
  • ranged-based for
  • while
  • do-while
• 陣列
• 字串
• 函式
  • 參考與指標
  • 傳值、傳址、傳參考
• 時間 / 空間複雜度觀念

STL

#

• pair
• tuple
• vector
• stack
• queue
• deque
• list
• set / multiset / unordered_set / unordered_multiset
• map / multimap / unordered_map / unordered_multimap\
• priority queue
• bitset
• 常見相關算法工具
  • sort
  • upper_bound / lower_bound
  • next_permutation / prev_permutation
  • accumulate / partial_sum

基本技巧

#

• 排序
  • bubble sort
  • insertion sort
  • counting sort
  • radix sort
  • merge sort
  • quick sort
• 枚舉
  • 暴力枚舉
  • 位元枚舉
  • 枚舉子集
  • 折半枚舉
• 搜尋
  • 基本二分搜
  • 對答案二分搜
  • 整體二分搜
  • 三分搜
• 前綴和
• 差分
• 離散化
• 雙指針/滑動窗口

語言特性與實用技巧

#

• structured binding
• reference &
• Range-based for
• 匿名函數 Lambda
• inline
• define
• IO 優化
• while (n–)
• 字尾空白與行尾換行
• <bits/stdc++.h>
• using
• mt19937

基本資料結構

#

• 所有 STL 內部原理
• BIT 樹狀數組
  • 加上差分達成區間加值
• 併查集 Disjoint Set
• 稀疏表 Sparse Table
• 線性碰撞、自訂雜湊
• pbds

基礎動態規劃

#

• 背包 DP
• 滾動陣列
• LCS/LIS
• 無限背包
• 有限背包
• 路徑 DP
• DAG DP
• 狀態壓縮
• 區間 DP
• 位元 DP
• 數位 DP
• DP 回溯
• 機率/期望值DP

基礎圖論

#

• 圖的表示法
  • 相鄰矩陣
  • 相鄰串列
  • 常數優化 : 鏈式前向星
• 圖的遍歷
  • DFS
  • BFS
• 最短路徑
  • Dijkstra
  • Bellman-Ford and SPFA
  • Floyd-Warshall (多源短路)
• 樹
  • Euler Tour / 樹壓平
  • 最近共同祖先 LCA
  • 樹重心
• 最小生成樹
  • Kruskal
  • Prim
• 拓撲排序
• 二分圖
• 連通性
  • Tarjan’s Algorithm for AP/Bridge
  • 強連通分量
    • Tarjan
    • Kosaraju

進階

#

進階資料結構

#

• 線段樹基礎
  • 懶標記
  • 值域線段樹
  • 線段樹上二分搜
• 線段樹進階
  • 動態開點
  • 持久化
  • 套其他資料結構
  • 線段樹分治
  • 李超線段樹
  • 吉如一線段樹
• 樹堆 Treap
• Splay Tree
• AVL Tree
• 笛卡爾樹
• 回文樹
• CDQ 分治

進階圖論

#

• 最大流/最小割
  • Edmonds-Karps Algorithm
  • Dinic’s Algorithm
• 最小費用流 MCMF
• 二分圖最大匹配
  • Hopcroft-Karp
  • Hungarian
• 樹鏈剖分 Heavy-Light Decomposition
• 樹分治
• 支配樹
• 樹分塊
• 樹套樹
• Matroid
• 2-SAT 問題

字串

#

• 基礎
  • Rolling Hash
  • KMP
  • Z Value
  • Manacher
• 進階
  • Suffix Array / Tree
  • 後綴自動機
• 應用
  • Trie
  • AC 自動機

數學

#

• 生成函數
• 數論
  • 整除性
  • 埃式篩法
  • 最大公因數和最小公倍數
  • 輾轉相除法
  • 擴展歐幾里得算法
• 模運算
  • 同餘性與模數
  • 反元素
  • 費馬小定理
  • 快速冪
  • 矩陣快速冪
  • 乘法反元素表
• 標準無偏賽局
  • 賽局和、型別、等價賽局
  • Nim
  • Choose Nim
  • MEX Principle
  • Sprague–Grundy Theorem
• 標準有偏賽局
  • Red-Blue-Hackenbush
  • 二進分數
  • Simplicity Principle
• 組合計數
  • 加法和乘法原理
  • 排列與組合
• 多項式與快速變換
  • FFT/IFFT
  • NTT
  • FWT
• 線性代數
  • 高斯消去法
  • 線性基 Linear Basis
• 延伸
  • 歐拉函數
  • 中國剩餘定理
  • 卡特蘭數
  • Burnside’s lemma
  • 數論函數
  • 莫比烏斯反演

根號算法

#

• 根號分解
• 序列分塊
• 樹分塊
• 值域分塊
• 數論分塊
• 操作分塊
• 莫隊算法
• 帶修改莫隊算法
• 回滾莫隊

計算幾何

#

• 向量定義、內積、外積
• 方向判定、極角排序
• 線段相交
• 鞋帶公式
• 凸包
• 旋轉卡尺
• Pick’s Theorem
• 極角掃描線
• 旋轉掃描線
• Minkowski Sum

進階動態規劃

#

• DP 優化
  • 前綴優化
  • 單調隊列優化
  • 矩陣快速冪優化
  • 資料結構優化
  • SOS 位元 DP 優化
  • 1D/1D 凹/凸優化
  • 2D/1D 優化
  • 斜率優化
  • Aliens 優化
  • slope trick
  • SMAWK
• 樹形 DP
• 單調隊列優化
• 高維 DP
• 輪廓線 DP
• 插頭 DP

https://oi-wiki.org/
https://cses.fi/book/book.pdf
https://cp-algorithms.com/
https://usaco.guide/