附录 D：竞赛常用算法模板

🏆 快速参考： 这些模板经过实战验证，可直接复制粘贴使用，专为算法竞赛场景设计。每个模板均注明了时间复杂度和典型应用场景。

在深入模板之前，先用这棵决策树，根据数据规模 N 选择合适的算法：

算法选择决策树

D.1 并查集（DSU / Union-Find）

适用场景： 动态连通性、Kruskal 最小生成树、环检测、元素分组。

复杂度： 每次操作 O(α(N)) ≈ O(1)（阿克曼函数的反函数，极小的常数）。

📄 C++ 完整代码

// =============================================================
// DSU（并查集）：路径压缩 + 按秩合并
// =============================================================
struct DSU {
    vector<int> parent, rank_;
    int components;  // 连通分量数

    DSU(int n) : parent(n), rank_(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0);  // parent[i] = i
    }

    // 带路径压缩的 find
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // 路径压缩
        return parent[x];
    }

    // 按秩合并：若真正合并了（两者在不同集合）则返回 true
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;  // 已连通
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;
        if (rank_[x] == rank_[y]) rank_[x]++;
        components--;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
};

// 使用示例：
int main() {
    int n = 5;
    DSU dsu(n);
    dsu.unite(0, 1);
    dsu.unite(2, 3);
    cout << dsu.connected(0, 1) << "\n";  // 1（连通）
    cout << dsu.connected(0, 2) << "\n";  // 0（不连通）
    cout << dsu.components << "\n";       // 3
    return 0;
}

D.2 线段树（单点更新，区间求和）

适用场景： 支持单点更新的区间求和/最大/最小查询。

复杂度： 建树 O(N)，每次查询/更新 O(log N)。

📄 C++ 完整代码

// =============================================================
// 线段树：单点更新，区间求和
// =============================================================
struct SegTree {
    int n;
    vector<long long> tree;

    SegTree(int n) : n(n), tree(4 * n, 0) {}

    void build(vector<long long>& arr, int node, int start, int end) {
        if (start == end) { tree[node] = arr[start]; return; }
        int mid = (start + end) / 2;
        build(arr, 2*node, start, mid);
        build(arr, 2*node+1, mid+1, end);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    void build(vector<long long>& arr) { build(arr, 1, 0, n-1); }

    void update(int node, int start, int end, int idx, long long val) {
        if (start == end) { tree[node] = val; return; }
        int mid = (start + end) / 2;
        if (idx <= mid) update(2*node, start, mid, idx, val);
        else update(2*node+1, mid+1, end, idx, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    // 将 arr[idx] 更新为 val
    void update(int idx, long long val) { update(1, 0, n-1, idx, val); }

    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0;  // 求和的单位元
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return query(2*node, start, mid, l, r)
             + query(2*node+1, mid+1, end, l, r);
    }
    // 查询 arr[l..r] 的区间和
    long long query(int l, int r) { return query(1, 0, n-1, l, r); }
};

// 使用示例：
int main() {
    vector<long long> arr = {1, 3, 5, 7, 9, 11};
    SegTree st(arr.size());
    st.build(arr);
    cout << st.query(2, 4) << "\n";   // 5+7+9 = 21
    st.update(2, 10);                 // arr[2] = 10
    cout << st.query(2, 4) << "\n";   // 10+7+9 = 26
    return 0;
}

D.3 BFS 模板

适用场景： 无权图/网格中的最短路径、层序遍历、多源距离。

复杂度： O(V + E)。

📄 C++ 完整代码

// =============================================================
// BFS：无权图最短路径
// =============================================================
#include <bits/stdc++.h>
using namespace std;

// 返回 dist[]，其中 dist[v] = src 到 v 的最短距离
// dist[v] = -1 表示不可达
vector<int> bfs(int src, int n, vector<vector<int>>& adj) {
    vector<int> dist(n, -1);
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

// 网格 BFS（四方向）
const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

int gridBFS(vector<string>& grid, int sr, int sc, int er, int ec) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<int>> dist(R, vector<int>(C, -1));
    queue<pair<int,int>> q;
    dist[sr][sc] = 0;
    q.push({sr, sc});
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr >= 0 && nr < R && nc >= 0 && nc < C
                && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }
    return dist[er][ec];  // 不可达时返回 -1
}

D.4 DFS 模板

适用场景： 连通分量、环检测、拓扑排序、洪水填充。

复杂度： O(V + E)。

📄 C++ 完整代码

// =============================================================
// DFS：迭代版与递归版模板
// =============================================================

vector<vector<int>> adj;
vector<int> color;  // 0=白（未访问），1=灰（栈中），2=黑（已完成）

// 递归 DFS + 环检测（有向图）
bool hasCycle = false;
void dfs(int u) {
    color[u] = 1;  // 标记为"进行中"
    for (int v : adj[u]) {
        if (color[v] == 0) dfs(v);
        else if (color[v] == 1) hasCycle = true;  // 后向边 → 有环！
    }
    color[u] = 2;  // 标记为"已完成"
}

// 利用 DFS 后序做拓扑排序
vector<int> topoOrder;
void dfsToposort(int u) {
    color[u] = 1;
    for (int v : adj[u]) {
        if (color[v] == 0) dfsToposort(v);
    }
    color[u] = 2;
    topoOrder.push_back(u);  // 处理完所有子节点后再加入
}
// 最后将 topoOrder 反转即得拓扑序列

// 迭代 DFS（避免大图递归时栈溢出）
void dfsIterative(int src, int n) {
    vector<bool> visited(n, false);
    stack<int> st;
    st.push(src);
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        // 在此处理 u
        for (int v : adj[u]) {
            if (!visited[v]) st.push(v);
        }
    }
}

D.5 Dijkstra 算法

适用场景： 边权非负的有权图最短路径。

复杂度： O((V + E) log V)。

📄 C++ 完整代码

// =============================================================
// Dijkstra 最短路 — O((V+E) log V)
// =============================================================
#include <bits/stdc++.h>
using namespace std;

typedef pair<long long, int> pli;  // {距离, 节点}
const long long INF = 1e18;

vector<long long> dijkstra(int src, int n,
                            vector<vector<pair<int,int>>>& adj) {
    // adj[u] = { {v, 边权}, ... }
    vector<long long> dist(n, INF);
    priority_queue<pli, vector<pli>, greater<pli>> pq;  // 小根堆

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();

        if (d > dist[u]) continue;  // ← 关键：跳过过时条目

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;  // dist[v] = src → v 的最短距离，INF 表示不可达
}

// 使用示例：
int main() {
    int n = 5;
    vector<vector<pair<int,int>>> adj(n);
    // 添加无向边 u-v，权重 w：
    auto addEdge = [&](int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    };
    addEdge(0, 1, 4);
    addEdge(0, 2, 1);
    addEdge(2, 1, 2);
    addEdge(1, 3, 1);
    addEdge(2, 3, 5);

    auto dist = dijkstra(0, n, adj);
    cout << dist[3] << "\n";  // 4（路径 0→2→1→3，代价 1+2+1=4）
    return 0;
}

D.6 二分查找模板

适用场景： 在有序数组中搜索，或"对答案二分"（参数搜索）。

复杂度： 每次搜索 O(log N)，对答案二分 O(f(N) × log V)。

📄 C++ 完整代码

// =============================================================
// 二分查找模板
// =============================================================

// 1. 查找精确值（返回下标或 -1）
int binarySearch(vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// 2. 第一个 arr[i] >= target 的下标（lower_bound）
int lowerBound(vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;  // 若所有元素 < target 则返回 arr.size()
}

// 3. 第一个 arr[i] > target 的下标（upper_bound）
int upperBound(vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 4. 对答案二分——找到最大的 X 使得 check(X) 为 true
// 模板：根据题目调整 lo、hi 和 check() 函数
long long bsOnAnswer(long long lo, long long hi,
                     function<bool(long long)> check) {
    long long answer = lo - 1;  // 哨兵：无合法答案
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (check(mid)) {
            answer = mid;
            lo = mid + 1;  // 尝试更大的答案
        } else {
            hi = mid - 1;
        }
    }
    return answer;
}

// STL 封装（实际使用中优先采用）：
// lower_bound(v.begin(), v.end(), x) → 指向第一个 >= x 的迭代器
// upper_bound(v.begin(), v.end(), x) → 指向第一个 >  x 的迭代器
// binary_search(v.begin(), v.end(), x) → bool，判断 x 是否存在

lower_bound / upper_bound 速查表：

目标	代码
第一个 ≥ x 的下标	`lower_bound(v.begin(), v.end(), x) - v.begin()`
第一个 > x 的下标	`upper_bound(v.begin(), v.end(), x) - v.begin()`
x 的出现次数	`upper_bound(..., x) - lower_bound(..., x)`
最大的 ≤ x 的值	`prev(upper_bound(..., x))` （需确认存在）
最小的 ≥ x 的值	`*lower_bound(..., x)` （需确认 < end）

D.7 模运算模板

适用场景： 大数运算、组合数学、大值 DP。

复杂度： 基本运算 O(1)，快速幂 O(log exp)。

📄 C++ 完整代码

// =============================================================
// 模运算模板
// =============================================================
const long long MOD = 1e9 + 7;  // 或 998244353（NTT 友好素数）

long long mod(long long x) { return ((x % MOD) + MOD) % MOD; }
long long add(long long a, long long b) { return (a + b) % MOD; }
long long sub(long long a, long long b) { return mod(a - b); }
long long mul(long long a, long long b) { return a % MOD * (b % MOD) % MOD; }

// 快速幂：base^exp mod MOD — O(log exp)
long long power(long long base, long long exp, long long mod = MOD) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;  // 当前位为 1
        base = base * base % mod;                    // 底数平方
        exp >>= 1;                                   // 右移
    }
    return result;
}

// 模逆元（base^(MOD-2) mod MOD，仅当 MOD 为素数时成立）
long long inv(long long x) { return power(x, MOD - 2); }

// 模意义下的除法
long long divide(long long a, long long b) { return mul(a, inv(b)); }

// 预处理阶乘，用于组合数
const int MAXN = 200005;
long long fact[MAXN], inv_fact[MAXN];

void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[MAXN-1] = inv(fact[MAXN-1]);
    for (int i = MAXN-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

// C(n, k) = 组合数 mod MOD
long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

D.8 快速幂（二进制取幂）

适用场景： 计算大指数 a^b（独立版或模运算版）。

复杂度： O(log b)。

📄 C++ 完整代码

// =============================================================
// 二进制取幂：O(log b) 计算 a^b
// =============================================================

// 整数幂（无取模）——大 a、b 时注意溢出
long long fastPow(long long a, long long b) {
    long long result = 1;
    while (b > 0) {
        if (b & 1) result *= a;  // 当前位为 1
        a *= a;                   // 底数平方
        b >>= 1;                  // 下一位
    }
    return result;
}

// 模意义快速幂：a^b mod m
long long modPow(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) result = result * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return result;
}

// 矩阵快速幂：用于 O(log N) 计算 Fibonacci 等
typedef vector<vector<long long>> Matrix;
// 注意：使用 D.7 中定义的 MOD（const long long MOD = 1e9 + 7）

Matrix multiply(const Matrix& A, const Matrix& B) {
    int n = A.size();
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            if (A[i][k])
                for (int j = 0; j < n; j++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

Matrix matPow(Matrix M, long long b) {
    int n = M.size();
    Matrix result(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1;  // 单位矩阵
    while (b > 0) {
        if (b & 1) result = multiply(result, M);
        M = multiply(M, M);
        b >>= 1;
    }
    return result;
}

// 示例：O(log N) 计算 Fibonacci(N)
// [F(n+1)]   [1 1]^n   [F(1)]
// [F(n)  ] = [1 0]   * [F(0)]
long long fibonacci(long long n) {
    if (n <= 1) return n;
    Matrix M = {{1, 1}, {1, 0}};
    Matrix result = matPow(M, n - 1);
    return result[0][0];  // F(n)
}

D.9 其他实用模板

前缀和（一维与二维）

📄 查看代码：前缀和（一维与二维）

// 一维前缀和
vector<long long> prefSum(n + 1, 0);
for (int i = 1; i <= n; i++) prefSum[i] = prefSum[i-1] + arr[i];
// 查询 arr[l..r] 的区间和（1-indexed）：prefSum[r] - prefSum[l-1]

// 二维前缀和
long long psum[N+1][M+1] = {};
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= M; j++)
        psum[i][j] = grid[i][j] + psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1];
// 查询矩形 [r1,c1]..[r2,c2] 的区间和：
// psum[r2][c2] - psum[r1-1][c2] - psum[r2][c1-1] + psum[r1-1][c1-1]

竞赛编程头文件模板

📄 查看代码：竞赛编程头文件模板

// 竞赛编程标准头文件模板
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define mp make_pair

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // 在此填写你的解答
    return 0;
}

速查卡片

算法	复杂度	需要包含的头文件
并查集（DSU）	`O(α(N))` 每次操作	—
线段树	`O(N)` 建树，`O(log N)` 每次操作	—
BFS	`O(V+E)`	`<queue>`
DFS	`O(V+E)`	`<stack>`
Dijkstra	`O((V+E) log V)`	`<queue>`
二分查找	`O(log N)`	`<algorithm>`
排序	`O(N log N)`	`<algorithm>`
模意义快速幂	`O(log exp)`	—
lower/upper_bound	`O(log N)`	`<algorithm>`

✅ 所有示例均在 C++17（-std=c++17 -O2）下编译通过并经过验证。

C++ 竞赛编程：USACO 学习指南