本頁目錄
- 基礎模板
- 資料結構
- BIT (Fenwick Tree / 樹狀數組)
- Segment Tree (線段樹 - 迭代式)
- Sparse Table (稀疏表)
- DSU (Disjoint Set Union / 並查集)
- Monotone Stack (單調棧)
- Monotone Deque (單調雙端佇列)
- 圖論
- BFS (廣度優先搜尋)
- 0-1 BFS
- DFS (深度優先搜尋)
- Dijkstra (最短路徑)
- Floyd-Warshall (全源最短路)
- Topological Sort (拓撲排序 / Kahn's Algorithm)
- Kruskal (最小生成樹)
- LCA (最近公共祖先 - Binary Lifting)
- Binary Lifting (倍增法 - 通用)
- Bipartite Check (二分圖判定)
- Cycle Detection (環偵測)
- Tree Diameter (樹直徑)
- Euler Tour (DFS 序)
- Subtree Size (子樹大小)
- DSU 離線刪邊 (反向加邊)
- 動態規劃
- 0/1 Knapsack (0/1 背包)
- Unbounded Knapsack (完全背包)
- Coin Change (硬幣問題)
- LIS (最長遞增子序列)
- LCS (最長公共子序列)
- Edit Distance (編輯距離)
- Grid DP (網格 DP)
- Interval DP (區間 DP)
- Bitmask DP (狀態壓縮 DP)
- Game DP (Nim / SG)
- Tree DP (樹 DP)
- Weighted Job Scheduling (加權工作排程)
- 貪心
- 區間排程 (Interval Scheduling)
- 多機區間排程 (k-Screen Scheduling)
- 最小化完成時間 (Task Scheduling)
- 截止時間排程 - Reverse Sweep (Deadline Job Scheduling)
- 截止時間排程 - Forward Sweep (EDF)
- 最小費用合併 (Huffman / Min Cost Merge)
- Multiset 貪心配對 - 最大匹配 (Ticket Assignment)
- Multiset 貪心配對 - 最小費用 (Min Cost Matching)
- 遞增陣列 (Increasing Array)
- 集合等分 (Set Partition)
- 間隔覆蓋 (Minimum Intervals to Cover Range)
- 間距最小化 (Gap Minimization)
- PQ 貪心移除 (Priority Queue Greedy Removal)
- 掃描線 (Sweep Line)
- 滑動中位數 (Sliding Median)
- 搜尋與排序
- Binary Search (二分搜)
- Ternary Search (三分搜)
- Two Pointers / Sliding Window (雙指標 / 滑動視窗)
- Meet in the Middle (折半搜尋)
- Merge Sort - Inversion Count (逆序對計數)
- 數學
- Fast Exponentiation (快速冪)
- Sieve of Eratosthenes (埃氏篩)
- Factorial Trailing Zeros (階乘尾零)
- Kadane's Algorithm (最大子陣列和)
- 前綴和
- 1D Prefix Sum (一維前綴和)
- 2D Prefix Sum (二維前綴和)
- 3D Prefix Sum (三維前綴和)
- 其他技巧
- Permutation (排列枚舉)
- Gray Code (格雷碼)
- Fast Hash (防 hack 雜湊)
- 四數之和 (Hash)
- Josephus Problem (約瑟夫問題)
- Pragma 加速
基礎模板
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
const long long INF = numeric_limits<int>::max();
const long long mod = 1000000007;
signed main() {
IO
}資料結構
BIT (Fenwick Tree / 樹狀數組)
用途:支援單點修改、前綴和查詢的資料結構。
複雜度:修改
struct BIT {
int n;
vector<int> tree;
vector<int> v; // v[i] 記錄位置 i 的原始值
BIT (int n = 0) : n(n), tree(n + 1, 0), v(n + 1, 0) {}
void upd(int i, int x) { // 位置 i 加上 x
v[i] += x;
for (;i <= n;i += i & -i) tree[i] += x;
}
int get(int i) { // 查詢前綴和 [1, i]
int s = 0;
for (;i > 0;i -= i & -i) s += tree[i];
return s;
}
int sum(int l, int r) {return get(r) - get(l - 1);} // 區間和 [l, r]
};用法:
BIT bit(n);
bit.upd(i, x); // 位置 i 加上 x
bit.sum(l, r); // 查詢區間 [l, r] 的和單點覆蓋(把位置 x 的值改成 y):
bit.upd(x, -bit.v[x]); // 先扣掉舊值
bit.upd(x, y); // 再加上新值簡化版 BIT(不需記錄原值,適合只做加法的場景):
struct BIT {
int n;
vector<int> tree;
BIT (int n = 0) : n(n), tree(n + 1, 0) {}
void upd(int i, int x = 1) {for (;i <= n;i += i & -i) tree[i] += x;}
int get(int i) {
int s = 0;
for (;i > 0;i -= i & -i) s += tree[i];
return s;
}
int sum(int l, int r) {return get(r) - get(l - 1);}
};Segment Tree (線段樹 - 迭代式)
用途:支援單點修改、區間查詢的資料結構。比 BIT 更泛用(可處理 min/max/sum 等)。
複雜度:建樹
以下為區間最小值查詢 + 單點修改版本:
struct segment_tree {
int sz; // 葉節點數量(補到 2 的冪次)
vector<int> t; // t[1] 為根,t[sz..2*sz-1] 為葉節點
segment_tree(int n = 0) {init(n);}
void init(int n) {
for (sz = 1;sz < n;sz *= 2); // sz 為 >= n 的最小 2 冪次
t.assign(2 * sz, INF); // 初始化為單位元素
}
void build(vector<int> &v) {
for (int i = 0;i < v.size();i++) t[sz + i] = v[i]; // 填入葉節點
for (int i = sz - 1;i > 0;i--) t[i] = min(t[i * 2], t[(i * 2) | 1]); // 自底向上合併
}
void upd(int x, int k) { // 把位置 x 的值改成 k(1-indexed)
int i = sz + x - 1;
t[i] = k;
for (i /= 2;i > 0;i /= 2) t[i] = min(t[i * 2], t[(i * 2) | 1]);
}
int ask(int l, int r) { // 查詢 [l, r] 的最小值(1-indexed)
int ans = INF;
for (l = sz + l - 1, r = sz + r - 1;l <= r;l /= 2, r /= 2) {
if (l & 1) ans = min(ans, t[l++]); // l 是右子 -> 單獨計入,l 右移
if (!(r & 1)) ans = min(ans, t[r--]); // r 是左子 -> 單獨計入,r 左移
}
return ans;
}
};用法:
segment_tree st(n);
st.build(v); // 用陣列 v 建樹(v 為 0-indexed)
st.upd(x, k); // 把位置 x 的值改成 k(1-indexed)
st.ask(l, r); // 查詢區間 [l, r] 的最小值(1-indexed)改成區間和:把所有
min改成+,初始值INF改成0。
Sparse Table (稀疏表)
用途:靜態陣列上 O(1) 回答區間 min/max 查詢(不支援修改)。
複雜度:建表
利用兩個有重疊的區間取 max/min 結果仍正確的性質(冪等性),可以
// 建表:st[i][j] = 從位置 i 開始、長度 2^j 的區間最大值
vector<vector<int>> st(m, vector<int>(20));
for (int i = 0;i < m;i++) st[i][0] = v[i];
for (int j = 1;j < 20;j++)
for (int i = 0;i + (1 << j) - 1 < m;i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
// 查詢 [l, r] 的最大值(0-indexed)
int lg = log2(r - l + 1);
int ans = max(st[l][lg], st[r - (1 << lg) + 1][lg]);DSU (Disjoint Set Union / 並查集)
用途:維護不相交集合的合併與查詢,常用於判斷連通性。
複雜度:均攤
基本版(含路徑壓縮 + 啟發式合併):
struct DSU {
vector<int> p, sz; // p[i] = i 的父節點,sz[i] = i 所在集合大小
DSU (int n = 0) {init(n);}
void init(int x) {
p.resize(x);
sz.assign(x, 1);
for (int i = 0;i < x;i++) p[i] = i; // 初始時每個元素是自己的根
}
int find(int x) {
return (p[x] == x ? x : p[x] = find(p[x])); // 路徑壓縮
}
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return 0; // 已在同一集合
if (sz[a] < sz[b]) swap(a, b); // 小的接到大的下面
p[b] = a;
sz[a] += sz[b];
return 1;
}
};附帶連通分量數 + 最大分量大小(適合需要即時查詢這些資訊的場景):
struct DSU {
vector<int> p, sz;
int mx, cnt; // mx = 最大集合大小,cnt = 集合數量
DSU (int n = 0) {init(n);}
void init(int x) {
cnt = x;
mx = 1;
p.resize(x);
sz.assign(x, 1);
for (int i = 0;i < x;i++) p[i] = i;
}
int find(int x) {
return (p[x] == x ? x : p[x] = find(p[x]));
}
void unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
mx = max(mx, sz[a]);
cnt--;
}
};不帶路徑壓縮版(需要可撤銷 / rollback 時使用,搭配啟發式合併仍為
int find(int x) {
if (p[x] == x) return x;
return find(p[x]); // 不做 p[x] = find(p[x]),因此可以撤銷
}Monotone Stack (單調棧)
用途:在 O(n) 內找到每個元素左/右邊第一個比它大或小的元素。
複雜度:
找每個元素左邊第一個比它小的位置(v 存的是下標,棧底放哨兵 0):
vector<int> v, a(n + 1);
v.push_back(0); // 哨兵,代表「沒有更小的」
for (int i = 1;i <= n;i++) {
cin >> a[i];
while (v.size() > 1 and a[i] <= a[v.back()]) v.pop_back(); // 彈出不再有用的
cout << v.back() << ' '; // v.back() 就是左邊第一個 < a[i] 的位置
v.push_back(i);
}最大矩形面積(histogram)- 雙 pass:對每個柱子找左右邊界,再算面積。
vector<int> h(m), l(m), r(m); // h = 高度,l[j] = 左邊第一個 < h[j] 的位置
vector<int> st;
// 左邊界
for (int j = 0;j < m;j++) {
while (!st.empty() and h[j] <= h[st.back()]) st.pop_back();
l[j] = (st.empty() ? -1 : st.back());
st.push_back(j);
}
st.clear();
// 右邊界
for (int j = m - 1;j >= 0;j--) {
while (!st.empty() and h[j] < h[st.back()]) st.pop_back();
r[j] = (st.empty() ? n : st.back());
st.push_back(j);
}
// 計算面積:以 h[j] 為高度,寬度 = r[j] - l[j] - 1(開區間)
for (int j = 0;j < m;j++) ans = max(ans, 1ll * h[j] * (r[j] - l[j]));最大矩形面積(histogram)- 單 pass(在右端點處結算):
vector<int> v, a(n + 2); // a[n+1] = 0 作為結尾哨兵
v.push_back(0); // 底部哨兵
int ans = 0;
for (int i = 1;i <= n + 1;i++) {
if (i <= n) cin >> a[i];
while (v.size() > 0 and a[i] < a[v.back()]) {
int h = v.back(); // 被彈出的柱子(以它為高度)
v.pop_back();
ans = max(ans, (i - v.back() - 1) * a[h]); // 寬度 = i - 左邊界 - 1
}
v.push_back(i);
}Monotone Deque (單調雙端佇列)
用途:在滑動視窗中 O(1) 查詢最大/最小值。
複雜度:整體
滑動視窗最小值(視窗大小在 [a, b] 之間):
deque<int> q; // 存下標,隊列中的值單調遞增
int ans = -INF;
for (int r = a;r <= n;r++) {
int i = r - a; // 新進入視窗的元素
while (!q.empty() and x[i] <= x[q.back()]) q.pop_back(); // 維護遞增
q.push_back(i);
while (!q.empty() and q.front() < r - b) q.pop_front(); // 移除超出視窗的
ans = max(ans, x[r] - x[q.front()]); // q.front() 是視窗內最小值的位置
}同時維護最大值和最小值(固定視窗大小 m):
deque<int> q, p; // q: 遞減隊列(max),p: 遞增隊列(min)
for (int i = 1;i <= n;i++) {
while (!q.empty() and q.front() <= i - m) q.pop_front(); // 移除過期
while (!p.empty() and p.front() <= i - m) p.pop_front();
while (!q.empty() and h[q.back()] <= h[i]) q.pop_back(); // 維護遞減
while (!p.empty() and h[p.back()] >= h[i]) p.pop_back(); // 維護遞增
q.push_back(i);
p.push_back(i);
// 此時 h[q.front()] = 視窗最大值,h[p.front()] = 視窗最小值
}圖論
BFS (廣度優先搜尋)
用途:在無權圖上求最短路徑、探索連通分量。
複雜度:
最短路徑 + 路徑回溯(從節點 1 到節點 n):
vector<vector<int>> v(n + 1); // 鄰接表
vector<bool> vis(n + 1); // 是否拜訪過
vector<int> pa(n + 1); // pa[x] = x 的前一個節點(用於回溯路徑)
queue<int> q;
vis[1] = 1;
q.push(1);
while (!q.empty()) {
int t = q.front();
q.pop();
for (auto x : v[t]) {
if (!vis[x]) {
q.push(x);
vis[x] = 1;
pa[x] = t;
}
}
}
// 從終點回溯路徑
vector<int> ans;
int now = n;
while (now) {
ans.push_back(now);
now = pa[now];
}
reverse(ans.begin(), ans.end());網格 BFS(上下左右四方向):
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
queue<pair<int, int>> q;
q.push({si, sj}); // 起點座標
vis[si][sj] = 1;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int k = 0;k < 4;k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 or ny < 0 or nx >= n or ny >= m) continue; // 越界
if (vis[nx][ny] or a[nx][ny] != '.') continue; // 已訪問或障礙
q.push({nx, ny});
vis[nx][ny] = 1;
}
}0-1 BFS
用途:邊權只有 0 和 1 時的最短路,用 deque 取代 priority_queue。
複雜度:
權重 0 的邊放隊首(push_front),權重 1 的邊放隊尾(push_back):
deque<tuple<int, int, int>> q; // {節點, 距離, 狀態}
q.push_back({start, 0, init_state});
while (!q.empty()) {
auto [x, l, t] = q.front();
q.pop_front();
// 花費 0 的轉移 -> push_front(保持隊列的距離單調性)
if (/* 0-cost transition */) {
q.push_front({x, l, !t});
}
// 花費 1 的轉移 -> push_back
for (auto i : v[t][x]) {
if (vis.count({i, t})) continue;
vis[{i, t}] = 1;
q.push_back({i, l + 1, t});
}
}DFS (深度優先搜尋)
用途:圖的遍歷、連通分量計數、環偵測、拓撲排序等。
複雜度:
連通分量計數(網格版,每個連通區域呼叫一次 dfs):
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void dfs(int x, int y) {
vis[x][y] = 1;
for (int k = 0;k < 4;k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 or ny < 0 or nx >= n or ny >= m) continue;
if (vis[nx][ny] or a[nx][ny] == '#') continue;
dfs(nx, ny);
}
}Dijkstra (最短路徑)
用途:求單源最短路(邊權非負)。
複雜度:
vector<vector<pair<int, int>>> v(n + 1); // v[a] = {{b, w}, ...} 表示 a->b 權重 w
vector<int> dis(n + 1, INF);
dis[1] = 0;
// min-heap,{距離, 節點}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, 1});
while (!q.empty()) {
auto [w, t] = q.top();
q.pop();
if (w != dis[t]) continue; // 已有更短路,跳過(懶刪除)
for (auto [nt, nw] : v[t]) {
if (dis[nt] > w + nw) { // 鬆弛
dis[nt] = w + nw;
q.push({dis[nt], nt});
}
}
}變體:同時記錄最短路數量、最少邊數、最多邊數:
vector<int> dis(n + 1, INF), way(n + 1, 0), mn(n + 1, INF), mx(n + 1, 0);
dis[1] = mn[1] = 0, way[1] = 1;
// ... 在鬆弛時:
if (d + nd < dis[nt]) { // 發現更短路
dis[nt] = d + nd;
way[nt] = way[t]; // 路徑數繼承
mn[nt] = mn[t] + 1;
mx[nt] = mx[t] + 1;
q.push({d + nd, nt});
}
else if (d + nd == dis[nt]) { // 等長路徑
way[nt] = (way[t] + way[nt]) % mod; // 路徑數累加
mn[nt] = min(mn[nt], mn[t] + 1);
mx[nt] = max(mx[nt], mx[t] + 1);
}K-th 最短路(允許同一節點被拜訪多次,第 k 次到達即為第 k 短路):
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
vector<int> cnt(n + 1); // cnt[t] = 節點 t 被拜訪的次數
q.push({0, 1});
while (!q.empty()) {
auto [d, t] = q.top();
q.pop();
if (++cnt[t] > k) continue; // 第 k+1 次以後不需要
if (t == n) cout << d << ' '; // 第 cnt[t] 次到達終點
for (auto [nt, nd] : v[t]) q.push({d + nd, nt});
}網格 Dijkstra(Trapping Rain Water 2D:從邊界開始,向內推水位高度):
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
// 先把邊界所有格子放入 heap
while (!q.empty()) {
auto [h, x, y] = q.top(); // h = 目前的水位高度
q.pop();
for (int i = 0;i < 4;i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
if (vis[nx][ny]) continue;
vis[nx][ny] = 1;
if (v[nx][ny] < h) ans += h - v[nx][ny]; // 可以蓄水
q.push({max(h, v[nx][ny]), nx, ny}); // 水位取 max
}
}Floyd-Warshall (全源最短路)
用途:求所有點對之間的最短路。適合節點數少(
複雜度:
核心思想:
const long long INF = numeric_limits<int>::max() / 2; // 注意用 INF/2 避免溢位
vector<vector<int>> dis(n, vector<int>(n, INF));
for (int i = 0;i < n;i++) dis[i][i] = 0;
// 建圖:dis[a][b] = w
for (int k = 0;k < n;k++) {
for (int i = 0;i < n;i++) {
if (dis[i][k] == INF) continue; // 剪枝:i 到 k 不通就跳過
for (int j = 0;j < n;j++) {
if (dis[k][j] == INF) continue;
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}離線刪邊技巧:把刪邊反轉成加邊,每次加入新中繼點
// 加入邊 (a[x], b[x]) 權重 w[x] 後,a[x] 和 b[x] 可作為新中繼點
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
dis[i][j] = min({dis[i][j], dis[i][a[x]] + w[x] + dis[b[x]][j], dis[i][b[x]] + w[x] + dis[a[x]][j]});
}
}Topological Sort (拓撲排序 / Kahn's Algorithm)
用途:將 DAG(有向無環圖)的節點排成線性序列,使得所有邊都從前指向後。
複雜度:
做法:反覆取出入度為 0 的節點。如果最終排序長度 ≠ n,代表圖有環。
vector<vector<int>> v(n + 1); // 鄰接表
vector<int> cnt(n + 1); // cnt[i] = 節點 i 的入度
// 建圖時:v[a].push_back(b); cnt[b]++;
queue<int> q;
for (int i = 1;i <= n;i++) if (!cnt[i]) q.push(i); // 入度 0 的先進隊
vector<int> ans;
while (!q.empty()) {
int x = q.front();
q.pop();
ans.push_back(x);
for (auto nx : v[x]) {
cnt[nx]--; // 移除 x 後,nx 的入度減 1
if (!cnt[nx]) q.push(nx); // 入度變 0,可以排序了
}
}
if (ans.size() != n) cout << "IMPOSSIBLE"; // 有環DAG 上最長路徑(拓撲排序 + DP:在拓撲序上做 DP):
dp[1] = 1; // dp[i] = 到達 i 的最長路徑長
while (!q.empty()) {
auto t = q.front();
q.pop();
for (auto nt : v[t]) {
dp[nt] = max(dp[nt], dp[t] + 1); // 或計數: dp[nt] = (dp[nt] + dp[t]) % mod;
if (!--cnt[nt]) q.push(nt);
}
}Kruskal (最小生成樹)
用途:找出連接所有節點的最小權重邊集合。
複雜度:
做法:將所有邊按權重排序,依序加入不會形成環的邊(用 DSU 判斷)。
DSU dsu(n);
vector<tuple<int, int, int>> edges(m); // {權重, 端點a, 端點b}
for (auto &[w, a, b] : edges) {
cin >> a >> b >> w;
a--, b--;
}
sort(edges.begin(), edges.end()); // 按權重排序
int cost = 0;
for (auto [w, a, b] : edges) if (dsu.unite(a, b)) cost += w; // 不在同一集合才加LCA (最近公共祖先 - Binary Lifting)
用途:求樹上兩點的最近公共祖先,也可以算兩點距離。
複雜度:預處理
做法:up[t][i] = 節點
vector<vector<int>> v, up; // v = 鄰接表,up = 倍增表
vector<int> deep; // deep[i] = 節點 i 的深度
void dfs(int t, int p) {
up[t][0] = p; // 父節點
for (int i = 1;i < 20;i++) up[t][i] = up[up[t][i - 1]][i - 1]; // 倍增
for (auto nt : v[t]) {
if (nt == p) continue;
deep[nt] = deep[t] + 1;
dfs(nt, t);
}
}
int lca(int a, int b) {
if (deep[a] < deep[b]) swap(a, b); // 確保 a 更深
// 第一步:把 a 跳到跟 b 同深度
for (int i = 0;i < 20;i++) if (((deep[a] - deep[b]) >> i) & 1) a = up[a][i];
if (a == b) return a; // b 就是 LCA
// 第二步:a, b 一起往上跳,找到 LCA 的正下方
for (int i = 19;i >= 0;i--) if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
return up[a][0]; // 再跳一步就是 LCA
}用法:
v.resize(n + 1);
deep.resize(n + 1);
up.resize(n + 1, vector<int>(20));
dfs(1, 1); // 以 1 為根做 DFS
int dist = deep[a] - deep[lca(a, b)] + deep[b] - deep[lca(a, b)]; // 兩點距離K-th Ancestor(查詢節點 start 的第 k 個祖先):
int x = start;
for (int i = 0;i < 20;i++) {
if (k & (1 << i)) x = up[x][i]; // k 的二進位拆解,逐步跳
}
// x == 0 表示不存在(跳超過根了)Binary Lifting (倍增法 - 通用)
用途:在任意「下一步」函數上做倍增,快速跳
複雜度:預處理
// up[i][j] = 從 j 出發跳 2^i 步到達的位置
vector<vector<int>> up(20, vector<int>(2 * n + 1, 2 * n)); // 2*n 作為「不存在」
up[0] = nxt; // nxt[j] = j 的下一步位置
for (int i = 1;i < 20;i++)
for (int j = 0;j <= 2 * n;j++)
up[i][j] = up[i - 1][up[i - 1][j]]; // 跳 2^i = 跳兩次 2^(i-1)
// 從 i 開始,跳最多步使得不超過 limit(貪心從大到小嘗試)
int now = i, cnt = 0;
for (int j = 19;j >= 0;j--)
if (up[j][now] < limit) now = up[j][now], cnt += (1 << j);Bipartite Check (二分圖判定)
用途:判斷圖是否能二著色(即是否為二分圖)。
複雜度:
做法:BFS 染色,相鄰節點必須不同色。若發現衝突則非二分圖。
vector<int> color(n + 1); // 0 = 未染色,1 / 2 = 兩種顏色
queue<int> q;
q.push(1);
color[1] = 1;
while (!q.empty()) {
int t = q.front();
q.pop();
for (auto nt : v[t]) {
if (color[nt] == color[t]) { // 相鄰同色 -> 非二分圖
cout << "IMPOSSIBLE";
return 0;
}
if (color[nt]) continue; // 已染色
q.push(nt);
color[nt] = 3 - color[t]; // 1 -> 2, 2 -> 1
}
}Cycle Detection (環偵測)
用途:偵測圖中是否存在環,並找出環上的節點。
無向圖找環(DFS,用 parent 陣列回溯路徑):
vector<int> p(n + 1); // p[x] = DFS 中 x 的父節點
void dfs(int x, int pa) {
for (auto nx : v[x]) {
if (nx == pa) continue; // 不走回頭路
if (p[nx]) {
// 找到環:從 x 沿 p[] 回溯到 nx 即為環
vector<int> ans = {nx};
while (x != nx) {
ans.push_back(x);
x = p[x];
}
ans.push_back(nx);
exit(0);
}
p[nx] = x;
dfs(nx, x);
}
}有向圖找環(DFS + 回溯棧:vis2 記錄「目前正在 DFS 路徑上」的節點):
vector<bool> vis, vis2; // vis = 全域已訪問,vis2 = 當前路徑上
vector<int> ans; // 當前 DFS 路徑
void dfs(int t) {
vis[t] = 1;
vis2[t] = 1;
ans.push_back(t);
for (auto nt : v[t]) {
if (!vis[nt]) dfs(nt);
else if (vis2[nt]) {
// nt 在當前路徑上 -> 找到環(ans 中從 nt 到末尾就是環)
exit(0);
}
}
ans.pop_back();
vis2[t] = 0; // 離開當前路徑
}Tree Diameter (樹直徑)
用途:找樹上距離最遠的兩點之間的距離。
複雜度:
做法:從任意點 BFS 找最遠點 u,再從 u BFS 找最遠點 v,u-v 距離即為直徑。
pair<int, int> bfs(int x) { // 回傳 {最遠點, 最遠距離}
vector<int> dis(n + 1), vis(n + 1);
queue<int> q;
q.push(x);
vis[x] = 1;
pair<int, int> ans = {0, 0};
while (!q.empty()) {
auto t = q.front();
q.pop();
for (auto nt : v[t]) {
if (vis[nt]) continue;
q.push(nt);
vis[nt] = 1;
dis[nt] = dis[t] + 1;
if (dis[nt] > ans.second) ans = {nt, dis[nt]};
}
}
return ans;
}
// 使用:先從 1 找最遠點,再從該點找直徑
// cout << bfs(bfs(1).first).second;Euler Tour (DFS 序)
用途:把樹壓平成一維陣列,使子樹對應到一段連續區間,搭配 BIT/線段樹做子樹查詢。
複雜度:
vector<int> in, out; // in[t] = 進入時間戳,out[t] = 離開時間戳
int now = 0;
void dfs(int t, int d) {
in[t] = ++now; // 進入 t
for (auto nt : v[t]) dfs(nt, d + 1);
out[t] = now; // 離開 t
}
// 節點 t 的子樹 = 區間 [in[t], out[t]]Subtree Size (子樹大小)
用途:算每個節點的子樹大小。
複雜度:
vector<int> vis(n + 1); // vis[t] = t 的子樹中有多少個子孫
void dfs(int t) {
for (auto nt : v[t]) {
dfs(nt);
vis[t] += vis[nt] + 1; // 子孫數 = 所有兒子的子樹大小之和 + 兒子本身
}
}DSU 離線刪邊 (反向加邊)
用途:需要刪邊的場景,因為 DSU 只支援合併,所以把操作反轉:先刪完再反向加回來。
複雜度:
DSU dsu(n);
vector<pair<int, int>> v(m);
for (auto &[x, y] : v) { cin >> x >> y; x--, y--; }
reverse(v.begin(), v.end()); // 反轉順序:最後刪的最先加
int now = n * (n - 1) / 2; // 初始所有點都不連通時的某個值
vector<int> ans;
for (auto [x, y] : v) {
ans.push_back(now);
int px = dsu.find(x), py = dsu.find(y);
if (px == py) continue; // 已連通
now -= dsu.sz[px] * dsu.sz[py]; // 合併後更新答案
dsu.unite(px, py);
}
reverse(ans.begin(), ans.end()); // 反轉回正確順序動態規劃
0/1 Knapsack (0/1 背包)
用途:
複雜度:
狀態:
int dp[n + 1][x + 1] = {};
for (int i = 1;i <= n;i++) {
for (int j = 0;j <= x;j++) {
dp[i][j] = dp[i - 1][j]; // 不選第 i 個
if (j >= w[i]) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]); // 選第 i 個
}
}
}空間壓縮版(倒序遍歷確保每個物品只用一次):
vector<int> dp(x + 1);
while (n--) {
int w, v;
cin >> w >> v;
for (int i = x;i >= w;i--) dp[i] = max(dp[i], dp[i - w] + v);
}可行性背包(判斷哪些總和可達,用 bool 陣列):
vector<bool> dp(100001);
dp[0] = 1; // 總和 0 一定可達
for (int i = 0;i < n;i++) {
for (int j = 100000;j >= v[i];j--) {
dp[j] = (dp[j] or dp[j - v[i]]);
}
}Unbounded Knapsack (完全背包)
用途:每個物品可以選無限次。
複雜度:
差異:正序遍歷(
dp[0][0] = 1;
for (int i = 1;i <= n;i++) {
int t;
cin >> t;
for (int j = 0;j <= x;j++) {
dp[i][j] = dp[i - 1][j]; // 不選
if (j >= t) dp[i][j] = (dp[i][j] + dp[i][j - t]) % mod; // 選(可重複)
}
}Coin Change (硬幣問題)
用途:用若干種面額的硬幣湊出目標金額。
方法數(排列:外層遍歷金額,內層遍歷硬幣 → 不同順序算不同方案):
vector<int> dp(k + 1);
dp[0] = 1;
for (int i = 1;i <= k;i++) {
for (auto x : coins) {
if (x > i) break;
dp[i] = (dp[i] + dp[i - x]) % mod;
}
}最少硬幣數:
vector<int> dp(k + 1, INF);
dp[0] = 0;
for (int i = 1;i <= k;i++) {
for (auto x : coins) {
if (x > i) break;
dp[i] = min(dp[i], dp[i - x] + 1);
}
}LIS (最長遞增子序列)
用途:找出陣列中最長的嚴格遞增子序列長度。
複雜度:
做法(patience sort):維護一個遞增陣列 ans,新元素若大於尾端就 append,否則用 lower_bound 替換。
vector<int> ans; // ans[i] = 長度為 i+1 的 LIS 的最小末尾值
while (n--) {
int x;
cin >> x;
if (ans.empty() or x > ans.back()) ans.push_back(x); // 延伸 LIS
else *lower_bound(ans.begin(), ans.end(), x) = x; // 替換,保持潛力
}
cout << ans.size();multiset 版(適合需要求最長非遞增子序列等變體):
multiset<int> ans;
while (n--) {
int x;
cin >> x;
auto it = ans.upper_bound(x); // 找第一個 > x 的位置
if (it == ans.end()) ans.insert(x);
else {
ans.erase(it); // 替換掉它
ans.insert(x);
}
}
cout << ans.size();LCS (最長公共子序列)
用途:找兩個序列的最長公共子序列。
複雜度:
狀態:
vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1));
for (int i = 1;i <= a.size();i++) {
for (int j = 1;j <= b.size();j++) {
if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; // 匹配
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 不匹配
}
}回溯路徑(pa 記錄每一步的來源方向:1=左上, 2=上, 3=左):
string ans;
int i = a.size(), j = b.size();
while (i > 0 and j > 0) {
if (pa[i][j] == 1) { ans += a[i - 1]; i--; j--; } // 匹配,取字元
else if (pa[i][j] == 2) i--;
else j--;
}
reverse(ans.begin(), ans.end());Edit Distance (編輯距離)
用途:把字串
複雜度:
狀態:
vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1));
for (int i = 0;i <= a.size();i++) dp[i][0] = i; // 刪除 i 個字元
for (int i = 0;i <= b.size();i++) dp[0][i] = i; // 插入 i 個字元
for (int i = 1;i <= a.size();i++) {
for (int j = 1;j <= b.size();j++) {
dp[i][j] = min({dp[i - 1][j] + 1, // 刪除
dp[i][j - 1] + 1, // 插入
dp[i - 1][j - 1] + (a[i - 1] != b[j - 1])}); // 替換或不變
}
}Grid DP (網格 DP)
路徑計數(從左上到右下,只能往右或往下,'#' 不可走):
複雜度:
狀態:
int dp[h + 1][w + 1] = {};
dp[1][1] = 1;
for (int i = 1;i <= h;i++) {
for (int j = 1;j <= w;j++) {
char c;
cin >> c;
if (c == '.') dp[i][j] = (1ll * dp[i][j] + dp[i - 1][j] + dp[i][j - 1]) % mod;
}
}最大正方形(在 01 矩陣中找最大的全 1 正方形,空間壓縮版):
狀態:
vector<int> dp(m + 1); // 上一列的 dp 值
for (int i = 1;i <= n;i++) {
vector<int> now(m + 1);
for (int j = 1;j <= m;j++) {
if (grid[i][j] == '0') continue;
now[j] = min({dp[j], now[j - 1], dp[j - 1]}) + 1; // 上、左、左上取 min + 1
ans = max(now[j], ans);
}
dp = now;
}Interval DP (區間 DP)
用途:處理「合併/分割區間」類的問題。
複雜度:
狀態:
合併石頭(每次合併相鄰兩堆,花費 = 兩堆的和,求最小總花費):
vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF / 2));
vector<int> pre(n + 1); // 前綴和,用來快速算區間和
for (int i = 1;i <= n;i++) {
pre[i] = pre[i - 1] + v[i];
dp[i][i] = 0; // 單個石頭不需要合併
}
for (int l = n;l >= 1;l--) { // 從小區間開始
for (int r = l + 1;r <= n;r++) {
for (int k = l;k < r;k++) { // 枚舉分割點
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + pre[r] - pre[l - 1]);
}
}
}博弈取石頭(兩人輪流從頭或尾取石頭,求先手最大得分):
狀態:
for (int l = n;l >= 1;l--) {
for (int r = l + 1;r <= n;r++) {
// 先手取左邊或右邊,剩下的給對手(對手得分 = 總分 - 先手得分)
dp[l][r] = max(pre[r] - pre[l - 1] - dp[l + 1][r], pre[r] - pre[l - 1] - dp[l][r - 1]);
}
}Bitmask DP (狀態壓縮 DP)
用途:用二進位表示集合的狀態,適合
複雜度:
Hamiltonian Path 計數(經過每個節點恰好一次的路徑數):
狀態:
vector<vector<int>> dp(1 << n, vector<int>(n));
dp[1][0] = 1; // 從節點 0 出發,已拜訪 {0}
for (int i = 1;i < (1 << n);i += 2) { // 只看包含節點 0 的狀態
for (int t = 0;t < n;t++) {
if (!dp[i][t]) continue;
for (auto nt : v[t]) {
if (i & (1 << nt)) continue; // nt 已在集合中
dp[i | (1 << nt)][nt] = (dp[i | (1 << nt)][nt] + dp[i][t]) % mod;
}
}
}
cout << dp[(1 << n) - 1][n - 1]; // 所有節點都拜訪過,結束在 n-1賽局 DP(狀態壓縮博弈:用 bitmask 記錄剩餘可選項目):
vector<int> dp(1 << n, -1);
dp[(1 << n) - 1] = 0; // 全部用完 = 敗態
bool win(int t) {
if (dp[t] != -1) return dp[t];
// 嘗試所有可能的移動
for (...) {
if (!win(next_state)) return dp[t] = 1; // 對手會輸 -> 我贏
}
return dp[t] = 0; // 所有移動都讓對手贏 -> 我輸
}Game DP (Nim / SG)
用途:判斷博弈的先手勝負。
狀態:
vector<bool> dp(k + 1); // dp[i] = true 表示先手必勝
for (int i = 1;i <= k;i++) {
for (auto x : moves) { // 每次可以拿 x 個
if (i < x) break;
if (!dp[i - x]) { // 存在一步讓對手進入敗態
dp[i] = 1;
break;
}
}
}
cout << (dp[k] ? "First" : "Second");Tree DP (樹 DP)
用途:在樹結構上做 DP,自葉向根合併資訊。
獨立集計數(選出的節點兩兩不相鄰的方案數):
狀態:
vector<vector<int>> dp; // dp[0][t], dp[1][t]
vector<bool> vis;
void dfs(int t) {
vis[t] = 1;
for (auto nt : v[t]) {
if (vis[nt]) continue;
dfs(nt);
dp[0][t] = (dp[0][t] * (dp[0][nt] + dp[1][nt]) % mod) % mod; // 不選 t -> 子可選可不選
dp[1][t] = dp[1][t] * dp[0][nt] % mod; // 選 t -> 子必不選
}
}DAG 上最長路(記憶化 DFS):
vector<int> dp;
int dfs(int t) {
if (dp[t] != -1) return dp[t];
dp[t] = 0;
for (auto nt : v[t]) dp[t] = max(dp[t], dfs(nt) + 1);
return dp[t];
}Weighted Job Scheduling (加權工作排程)
用途:
複雜度:
狀態:
做法:按結束時間排序,對每個工作二分搜找「開始前最晚結束的工作」。
vector<array<int, 3>> v(n); // {開始, 結束, 報酬}
for (auto &[x, y, w] : v) cin >> x >> y >> w;
sort(v.begin(), v.end(), [](auto x, auto y) {
if (x[1] == y[1]) return x[0] < y[0];
return x[1] < y[1]; // 按結束時間排序
});
vector<int> a, dp(n + 1);
for (auto [x, y, w] : v) a.push_back(y); // 結束時間陣列(用於二分搜)
for (int i = 1;i <= n;i++) {
auto [x, y, w] = v[i - 1];
// lower_bound 找第一個結束時間 >= x 的位置 -> 前一個就是不衝突的最後一個
dp[i] = max(dp[i - 1], dp[lower_bound(a.begin(), a.end(), x) - a.begin()] + w);
}貪心
區間排程 (Interval Scheduling)
用途:從一堆區間中選出最多個不重疊的區間。
複雜度:
策略:按結束時間排序,每次選結束最早且不衝突的區間。
sort(v.begin(), v.end(), [](auto a, auto b) {return a.second < b.second;});
int last = -1, ans = 0; // last = 上一個選的區間的結束時間
for (auto [x, y] : v) {
if (x >= last) { // 開始時間 >= 上一個結束 -> 不衝突
ans++;
last = y;
}
}多機區間排程 (k-Screen Scheduling)
用途:有
複雜度:
策略:按結束時間排序,用 multiset 記錄每個機器目前的結束時間,優先使用「結束時間最接近開始時間」的機器。
sort(v.begin(), v.end(), [](auto a, auto b) {return a.second < b.second;});
multiset<int> st; // 每個機器目前的結束時間
int ans = 0;
for (auto [x, y] : v) {
auto it = st.upper_bound(x); // 找結束時間 <= x 的最大值
if (it != st.begin()) {
st.erase(prev(it)); // 替換該機器的結束時間
st.insert(y);
ans++;
continue;
}
if (st.size() < k) { // 還有空閒機器
st.insert(y);
ans++;
}
}最小化完成時間 (Task Scheduling)
用途:
複雜度:
策略:按處理時間排序(SPT rule),讓短的工作先做。
sort(v.begin(), v.end()); // v[i] = {處理時間, 截止時間}
int sum = 0, ans = 0; // sum = 目前的累計完成時間
for (auto [a, d] : v) {
sum += a;
ans += (d - sum); // 截止時間 - 完成時間 = 剩餘彈性
}截止時間排程 - Reverse Sweep (Deadline Job Scheduling)
用途:
複雜度:
策略:從最後一天開始往前掃,每天從可用工作中選報酬最高的。
vector<vector<int>> v(m + 1); // v[s] = 最早可開始在第 s 天做的工作報酬們
for (int i = 0;i < n;i++) {
int a, b; // a = 需要的天數(截止期限),b = 報酬
cin >> a >> b;
int s = m - a + 1; // 最晚開始日
if (s >= 1 and s <= m) v[s].push_back(b);
}
priority_queue<int> q; // max-heap,存可用工作的報酬
int ans = 0;
for (int i = m;i >= 1;i--) { // 從最後一天往前
for (auto x : v[i]) q.push(x); // 第 i 天新可用的工作加入
if (!q.empty()) {
ans += q.top(); // 選報酬最高的
q.pop();
}
}截止時間排程 - Forward Sweep (EDF)
用途:
複雜度:
策略:正向模擬時間,用 min-heap 優先處理截止時間最早的。
sort(v.begin(), v.end()); // 按開始時間排序
int now = 0, ans = 0, pos = 0;
priority_queue<int, vector<int>, greater<int>> q; // min-heap,存截止時間
while (pos < n or !q.empty()) {
now++;
if (q.empty()) now = max(now, v[pos].first); // 跳到下一個有工作的時間
while (pos < n and v[pos].first <= now) {
q.push(v[pos].second); // 把已開始的工作放進 heap
pos++;
}
while (!q.empty() and q.top() < now) q.pop(); // 移除已過期的
if (!q.empty()) {
ans++; // 做截止時間最早的
q.pop();
}
}最小費用合併 (Huffman / Min Cost Merge)
用途:每次選兩個合併,費用 = 兩者之和,求最小總費用。經典問題:合併竹棍、Huffman 編碼。
複雜度:
策略:每次合併最小的兩個(讓大的晚被合併,減少重複計費)。
priority_queue<int, vector<int>, greater<int>> q; // min-heap
while (n--) { int t; cin >> t; q.push(t); }
int ans = 0;
while (q.size() >= 2) {
int a = q.top(); q.pop();
int b = q.top(); q.pop();
ans += a + b; // 這次合併的費用
q.push(a + b); // 合併結果放回
}Multiset 貪心配對 - 最大匹配 (Ticket Assignment)
用途:每個需求找一個
複雜度:
multiset<int> st;
// 先把所有選項插入 st
while (m--) {
int t;
cin >> t;
auto it = st.upper_bound(t); // 第一個 > t 的位置
if (it == st.begin()) cout << -1 << '\n'; // 沒有 <= t 的
else {
--it; // 退一步 = 最大的 <= t
cout << *it << '\n';
st.erase(it); // 配對後移除
}
}Multiset 貪心配對 - 最小費用 (Min Cost Matching)
用途:每個需求找一個
複雜度:
multiset<int> st;
// 先把所有選項插入 st
int ans = 0;
for (int i = 0;i < m;i++) {
int t;
cin >> t;
auto it = st.lower_bound(t); // 第一個 >= t 的
if (it == st.end()) { /* 無法匹配 */ }
ans += *it;
st.erase(it); // 配對後移除
}遞增陣列 (Increasing Array)
用途:把陣列變成非遞減的最小代價(只能增加元素值)。
複雜度:
策略:遇到比前一個小的就補到跟前一個一樣大。
int ans = 0;
for (int i = 1;i < n;i++) {
if (v[i] < v[i - 1]) {
ans += v[i - 1] - v[i]; // 需要增加的量
v[i] = v[i - 1]; // 補到跟前一個一樣
}
}集合等分 (Set Partition)
用途:把
複雜度:
策略:從大到小,能放就放(先填目標總和小的那邊)。
int cnt = (n * (n + 1)) / 4; // 每個集合的目標總和
vector<int> a, b;
for (int i = n;i >= 1;i--) {
if (i <= cnt) { // 還裝得下就放進集合 a
a.push_back(i);
cnt -= i;
}
else b.push_back(i);
}間隔覆蓋 (Minimum Intervals to Cover Range)
用途:用最少的區間覆蓋一段指定範圍
複雜度:
策略:排序後,每次從所有起點 <= 當前位置的區間中,選終點最遠的。
sort(v.begin(), v.end()); // 按起點排序
int now = start, l = 0, cnt = 0;
while (now < finish) {
int t = now;
while (l < n and v[l].first <= now) { // 所有可用的區間
t = max(t, v[l].second); // 找最遠的終點
l++;
}
if (t <= now) break; // 無法前進 -> 覆蓋不了
now = t;
cnt++;
}間距最小化 (Gap Minimization)
用途:
複雜度:
策略:排序、算相鄰間距、取最小的
sort(x.begin(), x.end());
vector<int> dis(m - 1); // 相鄰兩點的間距
for (int i = 0;i < m - 1;i++) dis[i] = x[i + 1] - x[i];
sort(dis.begin(), dis.end());
int ans = 0;
for (int i = 0;i < m - n;i++) ans += dis[i]; // 取最小的 m-n 個PQ 貪心移除 (Priority Queue Greedy Removal)
用途:依序移除代價最小的元素,移除時更新鄰居的代價。
複雜度:
策略:用 min-heap 存 {代價, 節點},移除後更新鄰居並重新入堆(懶刪除)。
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
vector<int> sz(n + 1); // sz[i] = 節點 i 的鄰居權重和
for (int i = 1;i <= n;i++) q.push({sz[i], i});
int ans = 0;
while (cnt < n) {
auto [w, t] = q.top();
q.pop();
if (vis[t]) continue; // 懶刪除:已移除的跳過
vis[t] = 1;
ans = max(w, ans);
cnt++;
for (auto nt : v[t]) {
if (vis[nt]) continue;
sz[nt] -= a[t]; // 鄰居少了 t,更新代價
q.push({sz[nt], nt}); // 重新入堆
}
}掃描線 (Sweep Line)
用途:求最大重疊區間數(同時進行的事件數上限)。
複雜度:
策略:把區間拆成
vector<pair<int, int>> v(2 * n); // {時間點, +1 或 -1}
for (int i = 0;i < 2 * n;i += 2) {
cin >> v[i].first;
v[i].second = 1; // 區間開始
cin >> v[i + 1].first;
v[i + 1].second = -1; // 區間結束
}
sort(v.begin(), v.end());
int ans = 0, sum = 0;
for (auto [x, s] : v) {
sum += s; // 目前重疊數
ans = max(ans, sum);
}滑動中位數 (Sliding Median)
用途:在滑動視窗中即時查詢中位數。
複雜度:每次插入/刪除
策略:用兩個 multiset,a 存較小的一半,b 存較大的一半,保持 a 多一個。
multiset<int> a, b; // a: 較小的一半,b: 較大的一半
// 插入 x
if (a.empty() or x < *a.rbegin()) a.insert(x);
else b.insert(x);
// 平衡兩邊大小(讓 a 比 b 多一個或相等)
while (b.size() > k / 2) { a.insert(*b.begin()); b.erase(b.begin()); }
while (b.size() < k / 2) { b.insert(*a.rbegin()); a.erase(prev(a.end())); }
// 中位數 = *a.rbegin()(a 的最大值)另見「搜尋與排序」中的排序配對 (Ferris Wheel) 和排序匹配 (Apartments),也屬於貪心。
搜尋與排序
Binary Search (二分搜)
用途:在單調性上找分界點。
複雜度:
int l = 0, r = 1e18, ans;
while (l <= r) {
int m = (l + r) / 2;
if (check(m)) { // check(m) = true 代表 m 可行
r = m - 1;
ans = m; // 記錄可行解,繼續找更小的
}
else {
l = m + 1;
}
}Ternary Search (三分搜)
用途:在單峰/單谷函數上找極值。
複雜度:
凸函數找最小值:
int l = lo, r = hi;
while (r - l >= 3) {
int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
if (f(m1) > f(m2)) l = m1 + 1; // 最小值在右邊
else r = m2 - 1; // 最小值在左邊
}
int ans = INF;
for (int i = l;i <= r;i++) ans = min(ans, f(i)); // 剩餘幾個暴力比較Two Pointers / Sliding Window (雙指標 / 滑動視窗)
用途:利用兩個指標在排序陣列或子陣列上高效搜尋。
複雜度:
三數之和(排序後固定一個,剩下兩個用雙指標搜尋):
sort(v.begin(), v.end());
for (int i = 0;i < n;i++) {
int l = i + 1, r = n - 1; // 在 i 右邊找兩個數
while (l < r) {
if (v[i] + v[l] + v[r] == x) {
// 找到
return 0;
}
else if (v[i] + v[l] + v[r] > x) r--; // 太大,右邊縮
else l++; // 太小,左邊擴
}
}最長不重複子陣列(維護視窗內每個元素出現次數):
map<int, int> mp; // 元素出現次數
int ans = 0;
for (int i = 0, j = 0;i < n;i++) { // i = 右端,j = 左端
mp[v[i]]++;
while (mp[v[i]] > 1) { // 有重複就縮左端
mp[v[j]]--;
j++;
}
ans = max(ans, i - j + 1);
}至多 k 種不同元素的子陣列計數:
map<int, int> mp;
int cnt = 0, ans = 0; // cnt = 目前不同元素數
for (int i = 0, j = 0;i < n;i++) {
mp[v[i]]++;
if (mp[v[i]] == 1) cnt++; // 新元素
while (cnt > k) { // 超過 k 種就縮左端
mp[v[j]]--;
if (!mp[v[j]]) cnt--;
j++;
}
ans += i - j + 1; // 以 i 為右端的合法子陣列數
}排序後配對(Ferris Wheel:兩人一組,總重 <= x,求最少組數):
sort(v.begin(), v.end());
int ans = 0, i = 0, j = n - 1; // i = 最輕,j = 最重
while (i <= j) {
if (i < j and v[i] + v[j] <= x) i++; // 配對成功,輕的右移
ans++; // 不管有沒有配對,重的都要一組
j--;
}排序後匹配(Apartments:a 和 b 差在 k 以內就算匹配,求最多配對數):
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int i = 0, ans = 0;
for (auto x : a) {
while (i < m and b[i] + k < x) i++; // b[i] 太小,右移
if (i >= m) break;
if (x - k <= b[i] and b[i] <= x + k) { ans++; i++; } // 在範圍內,配對
}Meet in the Middle (折半搜尋)
用途:把
複雜度:
例:找子集和等於
// 前半部分:枚舉前 n/2 個元素的所有子集
unordered_map<int, int> cnt; // cnt[sum] = 和為 sum 的子集數
for (int i = 0;i < (1 << (n / 2));i++) {
int sum = 0;
for (int j = 0;j < n / 2;j++) if (i & (1 << j)) sum += v[j];
cnt[sum]++;
}
// 後半部分:枚舉後 n/2 個元素的所有子集,查表配對
int ans = 0;
for (int i = 0;i < (1 << ((n + 1) / 2));i++) {
int sum = 0;
for (int j = 0;j < (n + 1) / 2;j++) if (i & (1 << j)) sum += v[j + n / 2];
if (cnt.count(k - sum)) ans += cnt[k - sum];
}Merge Sort - Inversion Count (逆序對計數)
用途:計算陣列中有多少對
複雜度:
做法:在 merge sort 合併時,右半的元素比左半先被放入 → 代表左半剩餘的都比它大。
vector<int> v, a; // v = 原陣列,a = 暫存
int f(int l, int r) {
if (l >= r) return 0;
int m = (l + r) / 2;
int ans = f(l, m) + f(m + 1, r); // 遞迴排序左右半
int i = l, j = m + 1, k = l;
while (i <= m and j <= r) {
if (v[i] <= v[j]) a[k++] = v[i++];
else a[k++] = v[j++], ans += m - i + 1; // 左半 i~m 的都比 v[j] 大
}
while (i <= m) a[k++] = v[i++];
while (j <= r) a[k++] = v[j++];
for (int i = l;i <= r;i++) v[i] = a[i];
return ans;
}BIT 版逆序對(用離散化 + BIT 計算每個元素前面有多少比它大的):
BIT bit(n);
vector<pair<int, int>> v(n);
for (int i = 0;i < n;i++) { cin >> v[i].first; v[i].second = i; }
sort(v.begin(), v.end()); // 離散化:排序後給每個值一個排名
vector<int> rk(n);
for (int i = n - 1;i >= 0;i--) rk[v[i].second] = i + 1;
int ans = 0;
for (int i = n - 1;i >= 0;i--) { // 從右到左掃
ans += bit.get(rk[i] - 1); // 已插入的排名 < rk[i] 的數量 = 逆序對
bit.upd(rk[i]);
}數學
Fast Exponentiation (快速冪)
用途:計算
複雜度:
long long ans = 1;
void f(long long a, long long b) {
if (b <= 1) {
ans = ((ans % mod) * (a % mod)) % mod;
return;
}
if (b % 2) { // b 是奇數:先乘一個 a
ans = ((ans % mod) * (a % mod)) % mod;
}
a = ((a % mod) * (a % mod)) % mod; // a = a²
f(a, b / 2); // 遞迴處理 b/2
}Sieve of Eratosthenes (埃氏篩)
用途:找出某範圍內的所有質數。
區間篩(找
vector<bool> not_prime(R - L + 1);
for (int i = 2;i * i <= R;i++) {
int v = R / i * i; // 從 R 往回找 i 的倍數
for (;v >= L && v > i;v -= i) {
not_prime[v - L] = 1; // 標記為合數
}
}Factorial Trailing Zeros (階乘尾零)
用途:計算
複雜度:
int f(int n) {
if (n == 0) return 0;
return n / 5 + f(n / 5); // n/5 + n/25 + n/125 + ...
}Kadane's Algorithm (最大子陣列和)
用途:找出連續子陣列的最大和。
複雜度:
int ans = -1e18, now = 0; // now = 以當前位置結尾的最大子陣列和
for (int i = 0;i < n;i++) {
now += v[i];
ans = max(ans, now);
if (now < 0) now = 0; // 負數不如重新開始
}前綴和
1D Prefix Sum (一維前綴和)
用途:
複雜度:建表
vector<int> pre(n + 1); // pre[i] = a[1] + a[2] + ... + a[i]
for (int i = 1;i <= n;i++) pre[i] = pre[i - 1] + a[i];
// 區間查詢 [l, r]
int sum = pre[r] - pre[l - 1];子陣列和等於 x 的計數(前綴和 + hash map:找有多少個 pre[j] = pre[i] - x):
map<long long, int> mp; // mp[s] = 前綴和為 s 的出現次數
mp[0] = 1; // 空前綴
long long ans = 0;
for (int i = 1;i <= n;i++) {
v[i] += v[i - 1]; // v[i] 變成前綴和
if (mp.find(v[i] - x) != mp.end()) ans += mp[v[i] - x];
mp[v[i]]++;
}2D Prefix Sum (二維前綴和)
用途:
複雜度:建表
使用排容原理:sum(x1,y1,x2,y2) = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]。
int a[n + 2][n + 2] = {};
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
// a[i][j] += 原始值
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]; // 二維前綴和
}
}
// 查詢左上角 (x1,y1) 到右下角 (x2,y2) 的矩形和
int sum = a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];3D Prefix Sum (三維前綴和)
用途:
複雜度:建表
排容原理的三維版本(3 個面 - 3 條邊 + 1 個頂點):
int s[N][N][N] = {};
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
for (int k = 1;k <= n;k++) {
int t;
cin >> t;
s[i][j][k] = s[i - 1][j][k] + s[i][j - 1][k] + s[i][j][k - 1]
- s[i - 1][j - 1][k] - s[i][j - 1][k - 1] - s[i - 1][j][k - 1]
+ s[i - 1][j - 1][k - 1] + t;
}
}
}
// 查詢 (lx,ly,lz) ~ (rx,ry,rz) 的長方體和
int ans = s[rx][ry][rz] - s[lx-1][ry][rz] - s[rx][ly-1][rz] - s[rx][ry][lz-1]
+ s[lx-1][ly-1][rz] + s[rx][ly-1][lz-1] + s[lx-1][ry][lz-1]
- s[lx-1][ly-1][lz-1];其他技巧
Permutation (排列枚舉)
用途:枚舉字串/陣列的所有排列。
複雜度:
string s;
cin >> s;
sort(s.begin(), s.end()); // 先排序,確保從最小排列開始
do {
cout << s << '\n';
} while (next_permutation(s.begin(), s.end()));Gray Code (格雷碼)
用途:產生 n 位元的格雷碼序列(相鄰兩個只差一位元)。
複雜度:
做法:n 位元格雷碼 = 前半加 "0" 前綴,後半為 n-1 位的反轉加 "1" 前綴。
vector<string> f(int n) {
if (n == 1) return {"0", "1"};
vector<string> now;
auto x = f(n - 1);
for (int i = 0;i < x.size();i++) now.push_back("0" + x[i]); // 正序加 "0"
for (int i = x.size() - 1;i >= 0;i--) now.push_back("1" + x[i]); // 逆序加 "1"
return now;
}Fast Hash (防 hack 雜湊)
用途:替 unordered_map 加上隨機化 hash,防止被特殊測資卡 hash 碰撞。
struct FastHash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
x = x ^ (x >> 31);
return x;
}
size_t operator()(long long x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
// 用法:unordered_map<int, int, FastHash> mp;四數之和 (Hash)
用途:在陣列中找四個數和為 x。
複雜度:
做法:枚舉兩兩配對,用 hash map 存前面的配對和。
unordered_map<int, pair<int, int>> mp; // mp[sum] = {i, j} 表示 v[i]+v[j] = sum
for (int i = 0;i < n;i++) {
for (int j = i + 1;j < n;j++) {
if (mp.find(x - v[i] - v[j]) != mp.end()) {
auto [a, b] = mp[x - v[i] - v[j]];
cout << a + 1 << ' ' << b + 1 << ' ' << i + 1 << ' ' << j + 1;
return 0;
}
}
// 把 (i, j<i) 的配對存入 map(確保不跟自己衝突)
for (int j = 0;j < i;j++) {
if (!mp.count(v[i] + v[j])) mp[v[i] + v[j]] = {i, j};
}
}Josephus Problem (約瑟夫問題)
用途:n 人圍一圈,每隔一人淘汰,求淘汰順序。
複雜度:
set<int> st;
for (int i = 1;i <= n;i++) st.insert(i);
auto pos = st.begin();
while (st.size() > 1) {
if (st.upper_bound(*pos) == st.end()) {
cout << *st.begin() << ' ';
st.erase(st.begin());
pos = st.begin();
}
else {
pos = st.upper_bound(*pos); // 跳到下一個人
cout << *pos << ' ';
st.erase(pos);
auto t = st.upper_bound(*pos);
if (t == st.end()) pos = st.begin(); // 繞回開頭
else pos = t;
}
}
cout << *st.begin();Pragma 加速
用途:在 judge 允許的情況下,讓 GCC 做更激進的優化。
#pragma GCC optimize("Ofast,unroll-loops,inline,fast-math")
#pragma GCC target("avx2,bmi2,popcnt,lzcnt")
載入留言中…