oi-algs

ICPC / 算法竞赛资料：C++ 代码模板、STL 速查与比赛注意事项。

目录按算法分类整理，点击模板名或文档标题可直接打开源文件，代码与资料全文在下方展示。

资料导航

子目录	模板	时间复杂度	空间复杂度
—	计数排序	O(n + m)（`m` 为值域上界）	O(n + m)
—	归并排序	O(n \log n)	O(n)（辅助数组与递归栈）
binary	二分答案	O(T_{\mathrm{check}} \cdot \log(R + 2))（R=r-l 为初始区间长度，`T_check` 为单次 `check` 的耗时）	O(1 + S_{\mathrm{check}})（`S_check` 为 `check` 的额外空间）
prefix-sum	二维前缀和（逐维累加）	O(nm)（`n` 行、`m` 列）	O(nm)
prefix-sum	二维前缀和（容斥）	O(nm)（`n` 行、`m` 列）	O(nm)
prefix-sum	一维差分	构建 O(n)	O(n)
prefix-sum	一维前缀和	构建 O(n)	O(n)
prefix-sum	高维前缀和（`SOS DP`）	O(n \cdot 2^n)（`n` 为状态位数）	O(2^n)

搜索 · search（1）

子目录	模板	时间复杂度	空间复杂度
—	精确覆盖（`Dancing Links`）	读入 O(nm)，建表 O(m + s)，搜索最坏为指数级（`n` 行、`m` 列，`s` 为 1 的个数）	O(n + m + s)（稀疏节点与搜索栈）

数据结构 · ds（8）

子目录	模板	时间复杂度	空间复杂度
—	单调队列	O(n)（每个下标至多入队、出队各一次）	O(n)（含输入；队列 O(k)，`k` 为窗口长度）
—	单调栈	O(n)（每个下标至多入栈、出栈各一次）	O(n)
dsu	并查集（路径压缩与按大小合并）	初始化 O(n)，单次 `find` / `unite` 均摊 O(\alpha(n))	O(n)（含递归栈）
fenwick	树状数组（单点加、区间求和）	建树 O(n)，单次修改/查询 O(\log n)	O(n)
fenwick	树状数组（区间加、单点查询）	建树 O(n)，单次修改/查询 O(\log n)	O(n)
seg	线段树（区间加、区间乘、区间求和）	建树 O(n)，单次区间修改/查询 O(\log n)	O(n)
seg	线段树（区间加、区间求和）	建树 O(n)，单次区间修改/查询 O(\log n)	O(n)
sparse-table	`ST` 表（区间最大值）	预处理 O(n \log n)，单次查询 O(1)	O(n \log n)

图论 · graph（12）

子目录	模板	时间复杂度	空间复杂度
bfs	0-1 `BFS`	O(n + m)（边权仅为 0 或 1）	O(n + m)
lca	最近公共祖先（倍增 `LCA`）	预处理 O(n \log n)，单次查询 O(\log n)	O(n \log n)（含祖先表与 `DFS` 栈）
mst	最小生成树（`Kruskal`）	O(n + m \log(m + 1))（排序边并使用并查集）	O(n + m)
mst	最小生成树（`Prim`）	O(n + m \log(m + 1))（懒删除堆）	O(n + m)（堆最多存放 O(m) 个候选项）
save	边集数组	单次加边 O(1)，存入或遍历 `m` 条边 O(m)	O(m)
save	链式前向星	单次加边 O(1)，遍历 `u` 的出边 O(\deg^{+}(u))	O(n + m)
shortest-path	单源最短路（`Bellman-Ford`）	O(n + nm)（最坏；提前无松弛时退出）	O(n + m)
shortest-path	全源最短路（`Floyd-Warshall`）	O(n^3 + m)（含读入 `m` 条边）	O(n^2)
shortest-path	单源最短路（堆优化 `Dijkstra`）	O(n + m \log(m + 1))（懒删除堆；边权非负）	O(n + m)（堆最多存放 O(m) 个候选项）
shortest-path	单源最短路（朴素 `Dijkstra`）	O(n^2 + m)（边权非负）	O(n + m)
shortest-path	单源最短路（SPFA）	O(n + nm)（最坏情况）	O(n + m)
topo	拓扑排序（`Kahn`）	O(n + m)	O(n + m)

动态规划 · dp（7）

子目录	模板	时间复杂度	空间复杂度
—	划分 `DP`	O(mn^2)（`n` 个元素划分为 `m` 段）	O(n^2 + mn)（区间权值表与 `DP` 表）
basic	最长公共子序列（`LCS`）	O(nm)（两个序列长度分别为 `n`、`m`）	O(nm)
basic	最长严格递增子序列（`LIS`）	O(n \log n)	O(n)
basic	最长不下降子序列（`LNDS`）	O(n \log n)	O(n)
interval	区间 `DP`（石子合并）	O(n^3)	O(n^2)
knapsack	0/1 背包	O(nm)（`n` 件物品，容量为 `m`）	O(n + m)（含输入；`DP` 数组 O(m)）
knapsack	完全背包	O(nm)（`n` 种物品，容量为 `m`）	O(n + m)（含输入；`DP` 数组 O(m)）

数学 · math（8）

子目录	模板	时间复杂度	空间复杂度
binary-exponentiation	快速幂	O(\log(b + 2))（`b` 为非负指数）	O(1)
number-theory/gcd	最大公约数（欧几里得算法）	O(\log(\min(\lvert a\rvert, \lvert b\rvert) + 2))	O(\log(\min(\lvert a\rvert, \lvert b\rvert) + 2))（递归栈）
number-theory/gcd	扩展欧几里得算法	O(\log(\min(\lvert a\rvert, \lvert b\rvert) + 2))	O(\log(\min(\lvert a\rvert, \lvert b\rvert) + 2))（递归栈）
number-theory/inverse	批量求逆元（前缀积）	O(n + \log \mathrm{mod})（各 `a[i]` 与 `mod` 互质，\mathrm{mod} > 1）	O(n + \log \mathrm{mod})（前缀积、答案数组与递归栈）
number-theory/inverse	乘法逆元（扩展欧几里得）	O(\log \mathrm{mod})（\mathrm{mod} > 1，且 \gcd(a,\mathrm{mod})=1）	O(\log \mathrm{mod})（递归栈）
number-theory/inverse	乘法逆元（费马小定理）	O(\log p)（`p` 为质数，且 `a` 不被 `p` 整除）	O(1)
number-theory/inverse	线性递推逆元	O(n)（`p` 为质数，且 1 \le n < p）	O(n)
permutation	逆序对计数（归并排序）	O(n \log n)	O(n)（辅助数组与递归栈）

杂项 · misc（1）

子目录	模板	时间复杂度	空间复杂度
discrete	离散化	O(n \log n)	O(n)

比赛工具 · contest（1）

子目录	模板	时间复杂度	空间复杂度
io	快速读写	O(L)（L 为实际读取或输出的字符数）	O(1)（固定宽度 `int`）

C++ 源码

基础算法 · basic

8 个模板

计数排序

时间复杂度： O(n + m)（m 为值域上界）

空间复杂度： O(n + m)

适用条件： 整数排序，所有输入满足 0 \le a_i \le m，且值域能装入计数数组。

注意事项：

n \le N、m \le M
当前实现不直接支持负数，需先平移或调整索引
值域过大时换比较排序或离散化。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 10000, M = 100;
int n, m, a[N + 1], tmp[N + 1], ps[M + 1];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) ps[a[i]]++;
    for (int i = 1; i <= m; i++) ps[i] += ps[i - 1];
    for (int i = n; i >= 1; i--) tmp[ps[a[i]]--] = a[i];
    swap(tmp, a);
    for (int i = 1; i <= n; i++) cout << a[i] << ' ';
}

归并排序

时间复杂度： O(n \log n)

空间复杂度： O(n)（辅助数组与递归栈）

适用条件： 对可比较元素进行稳定升序排序，使用 1..n 下标。

注意事项：

输入和辅助数组容量至少覆盖 n
合并时保留 <= 才能保持等价元素的原相对顺序。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 10000;
int n, a[N + 1], tmp[N + 1];
void merge_sort(int l, int r) {
    if (l >= r) return;
    int m = l + ((r - l) >> 1);
    merge_sort(l, m); merge_sort(m + 1, r);
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
        }
    }
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    while (k--) a[l + k] = tmp[k];
    return;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    merge_sort(1, n);
    for (int i = 1; i <= n; i++) cout << a[i] << ' ';
    return 0;
}

二分答案

时间复杂度： O(T_{\mathrm{check}} \cdot \log(R + 2))（R=r-l 为初始区间长度，T_check 为单次 check 的耗时）

空间复杂度： O(1 + S_{\mathrm{check}})（S_check 为 check 的额外空间）

适用条件： 整数区间上的 check 单调，左端可行、右端不可行，用于寻找最后一个可行值。

注意事项：

先初始化 l、r 并实现 check
答案为 l。若单调方向相反需调整转移，端点和中点计算要防溢出。

#include <bits/stdc++.h>
using namespace std;
int l, r;
bool check(int mid);
int main() {
    while (l + 1 < r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
}

二维前缀和（逐维累加）

时间复杂度： O(nm)（n 行、m 列）

空间复杂度： O(nm)

适用条件： 静态 n 行 m 列矩阵，构建后用于矩形区间求和。

注意事项：

先用原矩阵初始化 ps，再逐维累加
第 0 行、列保持为 0
不能在旧前缀和上重复构建，大和改用 long long。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 100;
int n, m, a[N + 1][M + 1], ps[N + 1][M + 1];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) ps[i][j] = a[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ps[i][j] += ps[i - 1][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ps[i][j] += ps[i][j - 1];
        }
    }
}

二维前缀和（容斥）

时间复杂度： O(nm)（n 行、m 列）

空间复杂度： O(nm)

适用条件： 静态 n 行 m 列矩阵，构建后用于矩形区间求和。

注意事项：

按行列递增顺序构建，第 0 行、列保持为 0
矩形查询使用四项容斥，检查下标及累加值是否溢出。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 100;
int n, m, a[N + 1][M + 1], ps[N + 1][M + 1];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + a[i][j];
        }
    }
}

一维差分

时间复杂度： 构建 O(n)

空间复杂度： O(n)

适用条件： 一维数组的差分构建，可配合区间加和最终一次前缀和还原。

注意事项：

先填充 a[1..n] 并设 a[0] = 0
区间加需修改 diff[l] 和 diff[r+1]，使用时为 r+1 额外预留空间。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100;
int n, a[N + 1], diff[N + 1];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        diff[i] = a[i] - a[i - 1];
    }
}

一维前缀和

时间复杂度： 构建 O(n)

空间复杂度： O(n)

适用条件： 静态一维数组，构建后用于区间求和。

注意事项：

先填充 a[1..n] 并设 ps[0] = 0
闭区间 [l,r] 的和为 ps[r]-ps[l-1]
大和改用 long long。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100;
int n, a[N + 1], ps[N + 1];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        ps[i] = ps[i - 1] + a[i];
    }
}

高维前缀和（`SOS DP`）

时间复杂度： O(n \cdot 2^n)（n 为状态位数）

空间复杂度： O(2^n)

适用条件： 用 n 位掩码表示状态，求每个 mask 的所有子集状态值之和。

注意事项：

n \le N，数组至少有 2^n 个元素
本实现累加子集而非超集，移位范围和累加类型都要足够。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 10;
int n, a[1 << N], ps[1 << N];
int main() {
    cin >> n;
    for (int i = 0; i < (1 << n); i++) cin >> a[i];
    for (int i = 0; i < (1 << n); i++) ps[i] = a[i];
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if (mask & (1 << i)) {
                ps[mask] += ps[mask ^ (1 << i)];
            }
        }
    }
}

搜索 · search

1 个模板

精确覆盖（`Dancing Links`）

时间复杂度： 读入 O(nm)，建表 O(m + s)，搜索最坏为指数级（n 行、m 列，s 为 1 的个数）

空间复杂度： O(n + m + s)（稀疏节点与搜索栈）

适用条件： 0/1 矩阵精确覆盖：选择若干行，使每一列恰好被一个 1 覆盖。

注意事项：

不是允许重复覆盖的问题
矩阵行列及 1 的个数分别不超过 N、M、MAX_ONE
恢复顺序要与删除相反，搜索最坏为指数级。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 500, M = 500, MAX_ONE = 5000;
constexpr int MAX_NODE = 1 + M + MAX_ONE;
int n, m, cnt, h[N + 1], sz[M + 1];
int L[MAX_NODE], R[MAX_NODE], U[MAX_NODE], D[MAX_NODE];
int row[MAX_NODE], col[MAX_NODE];
deque<int> q;
void build() {
    cnt = m;
    for (int i = 0; i <= m; i++) {
        U[i] = i, D[i] = i;
        L[i] = i - 1, R[i] = i + 1;
    }
    L[0] = m, R[m] = 0;
}
void insert(int r, int c) {
    cnt++;
    row[cnt] = r, col[cnt] = c;
    U[cnt] = c, D[cnt] = D[c];
    D[c] = U[D[c]] = cnt;
    if (!h[r]) {
        h[r] = cnt;
        L[cnt] = R[cnt] = cnt;
    } else {
        L[cnt] = h[r], R[cnt] = R[h[r]];
        R[h[r]] = L[R[h[r]]] = cnt;
    }
    sz[c]++;
}
void remove(int c) {
    int i, j;
    L[R[c]] = L[c], R[L[c]] = R[c];
    for (i = D[c]; i != c; i = D[i]) {
        for (j = R[i]; j != i; j = R[j]) {
            U[D[j]] = U[j], D[U[j]] = D[j];
            sz[col[j]]--;
        }
    }
}
void recover(int c) {
    int i, j;
    L[R[c]] = R[L[c]] = c;
    for (i = U[c]; i != c; i = U[i]) {
        for (j = L[i]; j != i; j = L[j]) {
            U[D[j]] = D[U[j]] = j;
            sz[col[j]]++;
        }
    }
}
bool dance() {
    int i, j, c = R[0];
    if (!R[0]) return true;
    for (i = R[0]; i != 0; i = R[i])
        if (sz[i] < sz[c]) c = i;
    remove(c);
    for (i = D[c]; i != c; i = D[i]) {
        q.push_back(row[i]);
        for (j = R[i]; j != i; j = R[j]) remove(col[j]);
        if (dance()) return true;
        for (j = L[i]; j != i; j = L[j]) recover(col[j]);
        q.pop_back();
    }
    recover(c);
    return false;
}
int main() {
    cin >> n >> m;
    build();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x; cin >> x;
            if (x) insert(i, j);
        }
    if (dance())
        while (!q.empty()) {
            cout << q.front() << ' ';
            q.pop_front();
        }
    else
        cout << "No Solution!";
    return 0;
}

数据结构 · ds

8 个模板

单调队列

时间复杂度： O(n)（每个下标至多入队、出队各一次）

空间复杂度： O(n)（含输入；队列 O(k)，k 为窗口长度）

适用条件： 求数组每个固定长度 k 滑动窗口的最大值，1 \le k \le n。

注意事项：

队列保存下标并先清理过期项
当前 <= 弹尾会保留较新的相等值，下标从 1 开始。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 10000;
int n, k, a[N + 1];
deque<int> q;
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && q.front() <= i - k) q.pop_front();
        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
        q.push_back(i);
        if (i >= k) cout << a[q.front()] << ' ';
    }
    return 0;
}

单调栈

时间复杂度： O(n)（每个下标至多入栈、出栈各一次）

空间复杂度： O(n)

适用条件： 求每个元素左侧最近的严格更大元素下标。

注意事项：

当前 <= 弹栈会排除相等值
找大于等于元素时需调整比较
输出 0 表示不存在，模板采用 1..n 下标。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 10000;
int n, a[N + 1];
stack<int> stk;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
        cout << (!stk.empty() ? stk.top() : 0) << ' ';
        stk.push(i);
    }
    return 0;
}

并查集（路径压缩与按大小合并）

时间复杂度： 初始化 O(n)，单次 find / unite 均摊 O(\alpha(n))

空间复杂度： O(n)（含递归栈）

适用条件： 维护集合合并和连通性，支持增量加边或合并，不直接支持删除与撤销。

注意事项：

先初始化 fa[i] = i、sz[i] = 1，索引为 1..n
路径压缩会改父指针，回滚并查集不能直接照搬此实现。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100;
int n, fa[N + 1], sz[N + 1];
int find(int x) {
    // path compression
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    // union by size
    if (sz[x] < sz[y]) swap(x, y);
    fa[y] = x;
    sz[x] += sz[y];
    return true;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        fa[i] = i; sz[i] = 1;
    }
    return 0;
}

树状数组（单点加、区间求和）

时间复杂度： 建树 O(n)，单次修改/查询 O(\log n)

空间复杂度： O(n)

适用条件： 一维数组上的单点加、前缀求和及区间求和，索引为 1..n。

注意事项：

更新下标不能为 0，否则 lowbit 循环不前进
当前为线性建树，不要再对初值重复 add
大和改用 long long。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 10000;
int n, a[N + 1], tree[N + 1];
int lowbit(int x) {
    return x & -x;
}
void add(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += k;
    }
}
int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) {
        res += tree[i];
    }
    return res;
}
int sum(int l, int r) {
    return query(r) - query(l - 1);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        tree[i] += a[i];
        int j = i + lowbit(i);
        if (j <= n) tree[j] += tree[i];
    }
}

树状数组（区间加、单点查询）

时间复杂度： 建树 O(n)，单次修改/查询 O(\log n)

空间复杂度： O(n)

适用条件： 用差分维护一维区间加、单点查询，索引为 1..n。

注意事项：

更新下标不能为 0
初始树保存差分，query(x) 才是位置 x 的值
本实现不能直接提供区间和。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 10000;
int n, a[N + 1], tree[N + 1];
int lowbit(int x) {
    return x & -x;
}
void add(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += k;
    }
}
int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) {
        res += tree[i];
    }
    return res;
}
void update(int l, int r, int k) {
    add(l, k);
    add(r + 1, -k);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        tree[i] += a[i] - a[i - 1];
        int j = i + lowbit(i);
        if (j <= n) tree[j] += tree[i];
    }
}

线段树（区间加、区间乘、区间求和）

时间复杂度： 建树 O(n)，单次区间修改/查询 O(\log n)

空间复杂度： O(n)

适用条件： 一维数组，支持区间加、区间乘、区间求和，结果对 \mathrm{mod} 取模；操作区间位于 [1,n]。

注意事项：

先初始化 mul 为 1，再 build
add 初始为 0，mul 初始为 1
区间加 v：update(..., 1, v)
区间乘 k：update(..., k, 0)
懒标记表示 x \gets \mathrm{mul}\cdot x+\mathrm{add}
push 时先乘后加，不能交换顺序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 10000;
ll a[N + 1], tree[(N << 2) + 1], add[(N << 2) + 1], mul[(N << 2) + 1];
int n, mod;
void pull(int p) {
    tree[p] = (tree[p << 1] + tree[(p << 1) + 1]) % mod;
}
void apply(int p, int l, int r, ll k, ll v) {
    k %= mod;
    v %= mod;
    tree[p] = (tree[p] * k + (r - l + 1) * v) % mod;
    mul[p] = mul[p] * k % mod;
    add[p] = (add[p] * k + v) % mod;
}
void push(int p, int l, int r) {
    if (add[p] == 0 && mul[p] == 1) return;
    int m = l + ((r - l) >> 1);
    apply(p << 1, l, m, mul[p], add[p]);
    apply((p << 1) + 1, m + 1, r, mul[p], add[p]);
    mul[p] = 1;
    add[p] = 0;
}
void build(int p, int l, int r) {
    if (l == r) {
        tree[p] = a[l] % mod;
        return;
    }
    int m = l + ((r - l) >> 1);
    build(p << 1, l, m);
    build((p << 1) + 1, m + 1, r);
    pull(p);
}
void update(int p, int l, int r, int ql, int qr, ll k, ll v) {
    if (ql <= l && r <= qr) {
        apply(p, l, r, k, v);
        return;
    }
    push(p, l, r);
    int m = l + ((r - l) >> 1);
    if (ql <= m) update(p << 1, l, m, ql, qr, k, v);
    if (qr > m) update((p << 1) + 1, m + 1, r, ql, qr, k, v);
    pull(p);
}
ll query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[p];
    push(p, l, r);
    int m = l + ((r - l) >> 1);
    ll res = 0;
    if (ql <= m) res = (res + query(p << 1, l, m, ql, qr)) % mod;
    if (qr > m) res = (res + query((p << 1) + 1, m + 1, r, ql, qr)) % mod;
    return res;
}
int main() {
    cin >> n >> mod;
    fill(mul + 1, mul + (n << 2) + 1, 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
}

线段树（区间加、区间求和）

时间复杂度： 建树 O(n)，单次区间修改/查询 O(\log n)

空间复杂度： O(n)

适用条件： 一维数组的区间加和区间求和，所有操作区间位于 1..n。

注意事项：

先 build
lazy 标记对应加法，不能直接用于区间赋值
区间长度乘增量和总和仍可能超过 long long。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 10000;
ll a[N + 1], tree[(N << 2) + 1], lazy[(N << 2) + 1];
int n;
void pull(int p) {
    tree[p] = tree[p << 1] + tree[(p << 1) + 1];
}
void apply(int p, int l, int r, ll v) {
    tree[p] += (r - l + 1) * v;
    lazy[p] += v;
}
void push(int p, int l, int r) {
    if (!lazy[p]) return;
    int m = l + ((r - l) >> 1);
    apply(p << 1, l, m, lazy[p]);
    apply((p << 1) + 1, m + 1, r, lazy[p]);
    lazy[p] = 0;
}
void build(int p, int l, int r) {
    if (l == r) {
        tree[p] = a[l];
        return;
    }
    int m = l + ((r - l) >> 1);
    build(p << 1, l, m);
    build((p << 1) + 1, m + 1, r);
    pull(p);
}
void update(int p, int l, int r, int ql, int qr, ll v) {
    if (ql <= l && r <= qr) {
        apply(p, l, r, v);
        return;
    }
    push(p, l, r);
    int m = l + ((r - l) >> 1);
    if (ql <= m) update(p << 1, l, m, ql, qr, v);
    if (qr > m) update((p << 1) + 1, m + 1, r, ql, qr, v);
    pull(p);
}
ll query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[p];
    push(p, l, r);
    int m = l + ((r - l) >> 1);
    ll res = 0;
    if (ql <= m) res += query(p << 1, l, m, ql, qr);
    if (qr > m) res += query((p << 1) + 1, m + 1, r, ql, qr);
    return res;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
}

`ST` 表（区间最大值）

时间复杂度： 预处理 O(n \log n)，单次查询 O(1)

空间复杂度： O(n \log n)

适用条件： 静态数组上的区间最大值查询，构建后不再修改数组。

注意事项：

LOGN 至少覆盖 \lfloor\log_2 N\rfloor
查询满足 1 \le l \le r \le n
重叠区间依赖 max 的幂等性，不能直接换成求和。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1000, LOGN = 9;
int n, q, a[N + 1], st[LOGN + 1][N + 1], logn[N + 1];
int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) st[0][i] = a[i];
    for (int i = 2; i <= n; i++) logn[i] = logn[i / 2] + 1;
    for (int j = 1; j <= logn[n]; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
        }
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        int k = logn[r - l + 1];
        cout << max(st[k][l], st[k][r - (1 << k) + 1]) << '\n';
    }
    return 0;
}

图论 · graph

12 个模板

0-1 `BFS`

时间复杂度： O(n + m)（边权仅为 0 或 1）

空间复杂度： O(n + m)

适用条件： 边权仅为 0 或 1 的图上求单源最短路。

注意事项：

0 边入队首、1 边入队尾
当前按有向边读入，无向边需双向存储
结果在 dis[t]，不可达时为 INF，需按题目输出。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 1000, INF = 0x3f3f3f3f;
int n, m, s, t, head[N + 1], dis[N + 1];
deque<int> dq;
// linked forward star: file:///graph/save/linked-forward-star.cpp
struct Edge {
    int to, w, nxt;
} e[M + 1];
int main() {
    cin >> n >> m;
    cin >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {v, w, head[u]};
        head[u] = i;
    };
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    dq.push_front(s);
    while (!dq.empty()) {
        int u = dq.front(); dq.pop_front();
        if (u == t) break;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to, w = e[i].w;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                if (!w) dq.push_front(v); else dq.push_back(v);
            }
        }
    }
    return 0;
}

最近公共祖先（倍增 `LCA`）

时间复杂度： 预处理 O(n \log n)，单次查询 O(\log n)

空间复杂度： O(n \log n)（含祖先表与 DFS 栈）

适用条件： 给定合法根的连通树，预处理后回答最近公共祖先查询。

注意事项：

LOGN 必须覆盖树规模
无向边双向存储，长链 DFS 可能耗尽调用栈
不是树或需要处理森林时要调整遍历与判定。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1000, LOGN = 9;
int n, q, root, lg, head[N + 1], dep[N + 1], fa[LOGN + 1][N + 1];
// linked forward star: file:///graph/save/linked-forward-star.cpp
struct E {
    int to, nxt;
} e[2 * N + 1];
void dfs(int u) {
    for (int j = 1; j <= LOGN; j++) {
        fa[j][u] = fa[j - 1][fa[j - 1][u]];
    }
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dep[v]) {
            dep[v] = dep[u] + 1;
            fa[0][v] = u;
            dfs(v);
        }
    }
}
int main() {
    cin >> n >> q >> root;
    for (int i = 1; i <= n - 1; i++) {
        int u, v; cin >> u >> v;
        e[i] = {v, head[u]}; head[u] = i;
        e[n + i] = {u, head[v]}; head[v] = n + i;
    }
    lg=__lg(n);
    dep[root] = 1;
    dfs(root);
    while (q--) {
        int u, v; cin >> u >> v;
        if (dep[u] < dep[v]) swap(u, v);
        for (int j = LOGN; j >= 0; j--) {
            if (dep[fa[j][u]] >= dep[v]) {
                u = fa[j][u];
            }
        }
        if (u == v)
            cout << u << '\n';
        else {
            for (int j = LOGN; j >= 0; j--) {
                if (fa[j][u] != fa[j][v]) {
                    u = fa[j][u];
                    v = fa[j][v];
                }
            }
            cout << fa[0][u] << '\n';
        }
    }
    return 0;
}

最小生成树（`Kruskal`）

时间复杂度： O(n + m \log(m + 1))（排序边并使用并查集）

空间复杂度： O(n + m)

适用条件： 无向带权图的最小生成树；连通时存在完整生成树，边权可为负数。

注意事项：

先读入 e[1..m]，当前 main 尚未读取边
结束后检查 cnt == n-1
需要总权值时自行累加并选择足够宽的类型。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 1000;
int n, m, cnt, fa[N + 1], sz[N + 1];
// edge list: file:///graph/save/edge-list.cpp
struct Edge {
    int u, v, w;
} e[M + 1];
bool cmp(const Edge &a, const Edge &b) {
    return a.w < b.w;
}
// dsu: file:///ds/dsu/dsu.cpp
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (sz[x] < sz[y]) swap(x, y);
    fa[y] = x;
    sz[x] += sz[y];
    return true;
}
int main() {
    cin >> n >> m;
    sort(e + 1, e + m + 1, cmp);
    for (int i = 1; i <= n; i++) {
        fa[i] = i; sz[i] = 1;
    }
    for (int i = 1; i <= m; i++) {
        if (unite(e[i].u, e[i].v)) {
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    return 0;
}

最小生成树（`Prim`）

时间复杂度： O(n + m \log(m + 1))（懒删除堆）

空间复杂度： O(n + m)（堆最多存放 O(m) 个候选项）

适用条件： 无向带权连通图的最小生成树，边权可为负数。

注意事项：

先补充双向边输入
当前 cnt 统计顶点，结束条件应为 cnt == n，不能写成 n-1
还需检查连通性并按需累加权值。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 1000, INF = 0x3f3f3f3f;
int n, m, cnt, head[N + 1], dis[N + 1];
bool vis[N + 1];
// linked forward star: file:///graph/save/linked-forward-star.cpp
struct Edge {
    int to, w, nxt;
} e[2 * M + 1];
struct Node {
    int u, w;
};
bool operator<(const Node &a, const Node &b) {
    return a.w > b.w;
}
priority_queue<Node> q;
int main() {
    cin >> n >> m;
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    q.push({1, 0});
    while (!q.empty()) {
        int u = q.top().u; q.pop();
        if (!vis[u]) {
            vis[u] = true;
            cnt++;
            if (cnt == n - 1) break;
            for (int i = head[u]; i; i = e[i].nxt) {
                int v = e[i].to, w = e[i].w;
                if (w < dis[v]) {
                    dis[v] = w;
                    q.push({v, w});
                }
            }
        }
    }
    return 0;
}

边集数组

时间复杂度： 单次加边 O(1)，存入或遍历 m 条边 O(m)

空间复杂度： O(m)

适用条件： 按条存储边，适合需要遍历全体边的 Kruskal、Bellman-Ford 等算法。

注意事项：

main 仅为骨架，需读边并调用 add
边编号从 1 开始，cnt 不超过 M
无法直接按出度高效枚举某个点的邻居。

#include <iostream>
using namespace std;
constexpr int N = 100, M = 1000;
int n, m, cnt;
struct Edge {
    int u, v, w;
} e[M + 1];
void add(int u, int v, int w) {
    e[++cnt] = {u, v, w};
}
int main() {
    cin >> n >> m;
    return 0;
}

链式前向星

时间复杂度： 单次加边 O(1)，遍历 u 的出边 O(\deg^{+}(u))

空间复杂度： O(n + m)

适用条件： 用数组维护邻接表，需要按顶点枚举出边，且预先知道存边数量上界。

注意事项：

main 仅为骨架，需读边并调用 add
head 初值为 0，边从 1 编号
无向图存两条边，多测重置 head 与 cnt。

#include <iostream>
using namespace std;
constexpr int N = 100, M = 1000;
int n, m, cnt, head[N + 1];
struct Edge {
    int to, w, nxt;
} e[M + 1];
void add(int u, int v, int w) {
    e[++cnt] = {v, w, head[u]};
    head[u] = cnt;
}
int main() {
    cin >> n >> m;
    return 0;
}

单源最短路（`Bellman-Ford`）

时间复杂度： O(n + nm)（最坏；提前无松弛时退出）

空间复杂度： O(n + m)

适用条件： 允许负边的单源最短路，要求源点可达部分无负环时最短距离有定义。

注意事项：

当前仅进行最多 n-1 轮松弛
判可达负环需额外一轮检查
答案在 dis 中，需自行输出，大距离注意溢出。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 1000, INF = 0x3f3f3f3f;
int n, m, s, t, dis[N + 1];
// edge list: file:///graph/save/edge-list.cpp
struct Edge {
    int u, v, w;
} e[M + 1];
int main() {
    cin >> n >> m;
    cin >> s >> t;
    for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    bool ok = true;
    for (int i = 1; i <= n - 1; i++) {
        ok = true;
        for (int j = 1; j <= m; j++) {
            int u = e[j].u, v = e[j].v, w = e[j].w;
            if (dis[u] != INF && dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                ok = false;
            }
        }
        if (ok) break;
    }
    return 0;
}

全源最短路（`Floyd-Warshall`）

时间复杂度： O(n^3 + m)（含读入 m 条边）

空间复杂度： O(n^2)

适用条件： 当前读边方式适用于小规模无向非负权图，计算全源最短路。

注意事项：

重边应取最小边权，正权自环不能覆盖对角线的 0，当前直接赋值需调整
改为有向或负权图时需调整读边、检查可达性并处理负环
k 必须在最外层。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, INF = 0x3f3f3f3f;
int n, m, dis[N + 1][N + 1];
int main() {
    cin >> n >> m;
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= n; i++) dis[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dis[u][v] = dis[v][u] = w;
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    return 0;
}

单源最短路（堆优化 `Dijkstra`）

时间复杂度： O(n + m \log(m + 1))（懒删除堆；边权非负）

空间复杂度： O(n + m)（堆最多存放 O(m) 个候选项）

适用条件： 非负边权图的单源最短路，适合邻接表与优先队列。

注意事项：

先补充边输入并填充 head、e
保留 d == dis[u] 过滤过期项
答案在 dis[t]，当前未输出，大权值需更宽的距离类型。

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
constexpr int N = 100, M = 1000, INF = 0x3f3f3f3f;
int n, s, t, head[N + 1], dis[N + 1];
priority_queue<pii, vector<pii>, greater<pii>> q;
// linked forward star: file:///graph/save/linked-forward-star.cpp
struct Edge {
    int to, w, nxt;
} e[M + 1];
int main() {
    cin >> n;
    cin >> s >> t;
    memset(dis, 0x3f, sizeof(dis));
    q.push({dis[s] = 0, s});
    while (!q.empty()) {
        auto [d, u] = q.top(); q.pop();
        if (d == dis[u]) {
            if (u == t) break;
            for (int i = head[u]; i; i = e[i].nxt) {
                int v = e[i].to, w = e[i].w;
                if (dis[u] + w < dis[v]) q.push({dis[v] = dis[u] + w, v});
            }
        }
    }
    return 0;
}

单源最短路（朴素 `Dijkstra`）

时间复杂度： O(n^2 + m)（边权非负）

空间复杂度： O(n + m)

适用条件： 非负边权图的单源最短路，适用于顶点数较小、可接受 O(n^2) 扫描的情形。

注意事项：

先补充边输入并填充 head、e
不可达距离保持 INF
答案在 dis[t]，当前未输出，大权值需更宽的距离类型。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 1000, INF = 0x3f3f3f3f;
int n, s, t, head[N + 1], dis[N + 1];
bool vis[N + 1];
// linked forward star: file:///graph/save/linked-forward-star.cpp
struct Edge {
    int to, w, nxt;
} e[M + 1];
int main() {
    cin >> n;
    cin >> s >> t;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (int j = 1; j <= n; j++) if (!vis[j] && (u == 0 || dis[j] < dis[u])) u = j;
        if (dis[u] == INF) break;
        if (u == t) break;
        vis[u] = true;
        for (int j = head[u]; j; j = e[j].nxt) {
            int v = e[j].to, w = e[j].w;
            if (!vis[v] && dis[u] + w < dis[v]) dis[v] = dis[u] + w;
        }
    }
    return 0;
}

单源最短路（SPFA）

时间复杂度： O(n + nm)（最坏情况）

空间复杂度： O(n + m)

适用条件： 允许负边的单源最短路，并检测从源点可达的负环。

注意事项：

最坏仍为 O(nm)
cnt 记录松弛路径的边数而非入队次数，ok=false 表示检测到可达负环
距离加法注意溢出。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 1000;
int n, m, s, t, head[N + 1], dis[N + 1], cnt[N + 1];
bool inq[N + 1];
queue<int> q;
// linked forward star: file:///graph/save/linked-forward-star.cpp
struct Edge {
    int to, w, nxt;
} e[M + 1];
int main() {
    cin >> n >> m;
    cin >> s >> t;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {v, w, head[u]};
        head[u] = i;
    };
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push(s); inq[s] = true;
    bool ok = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to, w = e[i].w;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] == n) {
                    ok = false;
                    break;
                }
                if (!inq[v]) {
                    q.push(v); inq[v] = true;
                }
            }
        }
        if (!ok) break;
    }
    return 0;
}

拓扑排序（`Kahn`）

时间复杂度： O(n + m)

空间复杂度： O(n + m)

适用条件： 有向图的拓扑排序与有环判定；只有 DAG 才有完整拓扑序。

注意事项：

算法会消耗入度数组
多测或重复运行需重建入度、队列与计数
重边按条计入入度，cnt < n 时表示存在环。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 10000, M = 20000;
int n, m, cnt, head[N + 1], in[N + 1], topo[N + 1];
struct Edge {
    int to, nxt;
} e[M + 1];
queue<int> q;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e[i] = {v, head[u]};
        head[u] = i;
        in[v]++;
    }
    for (int i = 1; i <= n; i++) {
        if (!in[i]) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo[++cnt] = u;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            in[v]--;
            if (!in[v]) {
                q.push(v);
            }
        }
    }
    if (cnt < n) {
        cout << -1;
    } else {
        for (int i = 1; i <= n; i++) {
            cout << topo[i] << ' ';
        }
    }
    return 0;
}

动态规划 · dp

7 个模板

划分 `DP`

时间复杂度： O(mn^2)（n 个元素划分为 m 段）

空间复杂度： O(n^2 + mn)（区间权值表与 DP 表）

适用条件： 将序列划分为恰好 m 个非空连续段，1 \le m \le n，每段收益由 w[l][r] 给出；当前零初值用于非负段收益。

注意事项：

若允许负收益，应将不可达状态及待取最大值的初值设为负无穷
区间收益表与 DP 表都要留足容量，总收益可能需要 long long。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1000, M = 100;
int n, m, w[N + 1][N + 1], dp[M + 1][N + 1];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> w[i][j];
    for (int i = 1; i <= n; i++) dp[1][i] = w[1][i];
    for (int j = 2; j <= m; j++) {
        for (int i = j; i <= n; i++) {
            for (int k = j - 1; k < i; k++) {
                dp[j][i] = max(dp[j][i], dp[j - 1][k] + w[k + 1][i]);
            }
        }
    }
    cout << dp[m][n];
}

最长公共子序列（`LCS`）

时间复杂度： O(nm)（两个序列长度分别为 n、m）

空间复杂度： O(nm)

适用条件： 求两个序列的最长公共子序列长度，允许所选元素不连续。

注意事项：

答案在 dp[n][m]，需按题目输出
不要与最长公共子串混淆，二维 DP 的容量和时间要能覆盖 nm。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 100;
int n, m, a[N + 1], b[M + 1], dp[N + 1][M + 1];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = a[i] == b[j] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return 0;
}

最长严格递增子序列（`LIS`）

时间复杂度： O(n \log n)

空间复杂度： O(n)

适用条件： 求序列的最长严格递增子序列长度。

注意事项：

答案为 len，当前未输出
lower_bound 使相等值不增加长度，此模板不直接恢复具体子序列。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100;
int n, len, a[N + 1], tail[N + 1];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(tail + 1, tail + len + 1, a[i]) - tail;
        tail[pos] = a[i];
        if (pos == len + 1) len++;
    }
}

最长不下降子序列（`LNDS`）

时间复杂度： O(n \log n)

空间复杂度： O(n)

适用条件： 求序列的最长不下降子序列长度，允许相邻选中值相等。

注意事项：

答案为 len，当前未输出
upper_bound 与严格递增版本不同，此模板不直接恢复具体子序列。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100;
int n, len, a[N + 1], tail[N + 1];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        int pos = upper_bound(tail + 1, tail + len + 1, a[i]) - tail;
        tail[pos] = a[i];
        if (pos == len + 1) len++;
    }
}

区间 `DP`（石子合并）

时间复杂度： O(n^3)

空间复杂度： O(n^2)

适用条件： 非负重量的线性石子合并，每次只能合并相邻两段，合并代价为该段总重量。

注意事项：

n \ge 1
dp[i][i] = 0，按区间长度递增转移
答案在 dp[1][n]，注意 INF 与总成本范围，不能直接用于环形版本。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100;
int n, w[N + 1], ps[N + 1], dp[N + 1][N + 1];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        ps[i] = ps[i - 1] + w[i];
        dp[i][i] = 0;
    }
    for (int l = 2; l <= n; l++) {
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            for (int k = i; k <= j - 1; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + ps[j] - ps[i - 1]);
            }
        }
    }
    return 0;
}

0/1 背包

时间复杂度： O(nm)（n 件物品，容量为 m）

空间复杂度： O(n + m)（含输入；DP 数组 O(m)）

适用条件： 每件物品至多使用一次，整数非负容量，求不超过容量的最大价值。

注意事项：

当前需补充 w、v 的读入
容量倒序遍历以避免重复使用同一物品
若要求恰好装满，需把不可达状态初始化为负无穷。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 1000;
int n, m, w[N + 1], v[N + 1], dp[M + 1];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
}

完全背包

时间复杂度： O(nm)（n 种物品，容量为 m）

空间复杂度： O(n + m)（含输入；DP 数组 O(m)）

适用条件： 每种物品可无限使用，重量为正整数，求不超过容量的最大价值。

注意事项：

当前需补充 w、v 的读入
容量正序遍历
零重量正价值会使答案无界，恰好装满版本需单独初始化不可达状态。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100, M = 1000;
int n, m, w[N + 1], v[N + 1], dp[M + 1];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = w[i]; j <= m; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
}

数学 · math

8 个模板

快速幂

时间复杂度： O(\log(b + 2))（b 为非负指数）

空间复杂度： O(1)

适用条件： 计算 a^b \bmod \mathrm{mod}，要求 b \ge 0 且 \mathrm{mod} > 0。

注意事项：

模乘及负数归一化可能溢出，大模数用 __int128 等处理
mod=1 且 b=0 时应返回 0，初值需改为 1%mod
不支持负指数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll a, b, mod;
ll fpow(ll a, ll b, ll mod) {
    ll res = 1;
    a = (a % mod + mod) % mod;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int main() {
    cin >> a >> b >> mod;
    fpow(a, b, mod);
}

最大公约数（欧几里得算法）

时间复杂度： O(\log(\min(\lvert a\rvert, \lvert b\rvert) + 2))

空间复杂度： O(\log(\min(\lvert a\rvert, \lvert b\rvert) + 2))（递归栈）

适用条件： 非负整数 a、b 的最大公约数，约定 \gcd(0,0)=0。

注意事项：

负数输入先安全归一化
INT_MIN 的绝对值不能存回 int，可先提升类型
本实现使用递归栈。

#include <bits/stdc++.h>
using namespace std;
int a, b;
int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}
int main() {
    cin >> a >> b;
    cout << gcd(a, b);
}

扩展欧几里得算法

时间复杂度： O(\log(\min(\lvert a\rvert, \lvert b\rvert) + 2))

空间复杂度： O(\log(\min(\lvert a\rvert, \lvert b\rvert) + 2))（递归栈）

适用条件：

对非负整数 a,b，求下列方程的一组整数解：

ax + by = \gcd(a,b)

注意事项：

系数与 a/b*x 的中间运算可能超出 int，应按范围改用 long long 或 __int128
负数输入需统一符号约定。

#include <bits/stdc++.h>
using namespace std;
int a, b, x, y;
int exgcd(int a, int b, int& x, int& y) {
    if (!b) {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main() {
    cin >> a >> b;
    cout << exgcd(a, b, x, y);
    return 0;
}

批量求逆元（前缀积）

时间复杂度： O(n + \log \mathrm{mod})（各 a[i] 与 mod 互质，\mathrm{mod} > 1）

空间复杂度： O(n + \log \mathrm{mod})（前缀积、答案数组与递归栈）

适用条件： \mathrm{mod} > 1，且每个 a[i] 都与 mod 互质，批量求各元素的乘法逆元。

注意事项：

任一元素不可逆时，前缀积的逆元也不存在
pp[0] = 1
大模数下前缀积和反向乘法应避免 long long 溢出。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 100;
ll n, mod, a[N + 1], pp[N + 1], ans[N + 1];
// inverse by extended euclidean: file:///math/inverse/inverse-by-extended-euclidean.cpp
ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll inv(ll a, ll mod) {
    ll x, y;
    exgcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}
int main() {
    cin >> n >> mod;
    for (int i = 1; i <= n; i++) cin >> a[i];
    pp[0] = 1;
    for (int i = 1; i <= n; i++) pp[i] = pp[i - 1] * a[i] % mod;
    ll ipp = inv(pp[n], mod);
    for (int i = n; i >= 1; i--) {
        ans[i] = ipp * pp[i - 1] % mod;
        ipp = ipp * a[i] % mod;
    }
    return 0;
}

乘法逆元（扩展欧几里得）

时间复杂度： O(\log \mathrm{mod})（\mathrm{mod} > 1，且 \gcd(a,\mathrm{mod})=1）

空间复杂度： O(\log \mathrm{mod})（递归栈）

适用条件： \mathrm{mod} > 1 且 \gcd(a,\mathrm{mod})=1；模数不必为质数。

注意事项：

当前 inv 未验证 exgcd 返回值，调用前需确保互质
系数运算与加 mod 的归一化可能溢出，应按范围选择更宽类型。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll a, mod;
// extended euclidean: file:///math/gcd/extended-euclidean.cpp
ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (!b) {
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll inv(ll a, ll mod) {
    ll x, y;
    exgcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}
int main() {
    cin >> a >> mod;
    cout << inv(a, mod);
    return 0;
}

乘法逆元（费马小定理）

时间复杂度： O(\log p)（p 为质数，且 a 不被 p 整除）

空间复杂度： O(1)

适用条件： p 为质数且 a 不被 p 整除，用 a^{p-2} 求乘法逆元。

注意事项：

不能直接用于任意合数模数或不可逆元素
大模数时模乘及归一化需防溢出，指数为 p-2。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll a, p;
// fast power: file:///math/binary-exponentiation/fast-power.cpp
ll fpow(ll a, ll b, ll p) {
    ll res = 1;
    a = (a % p + p) % p;
    while (b) {
        if (b & 1) {
            res = res * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
ll inv(ll a, ll p) {
    return fpow(a, p - 2, p);
}
int main() {
    cin >> a >> p;
    cout << inv(a, p);
}

线性递推逆元

时间复杂度： O(n)（p 为质数，且 1 \le n < p）

空间复杂度： O(n)

适用条件： p 为质数，求 1..n 的逆元，且满足 1 \le n < p。

注意事项：

不能直接用于合数模数或 n \ge p
n 不超过数组上界，大 p 时递推中的乘法要使用更宽类型。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 1000;
ll n, p, inv[N + 1];
int main() {
    cin >> n >> p;
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
    return 0;
}

逆序对计数（归并排序）

时间复杂度： O(n \log n)

空间复杂度： O(n)（辅助数组与递归栈）

适用条件： 长度 n \ge 1 的序列，统计 i < j 且 a[i] > a[j] 的逆序对。

注意事项：

先读入 a[1..n]，当前 main 尚未读序列
相等值不算逆序对
答案可达 \frac{n(n-1)}{2}，大规模时计数和返回值改为 long long。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100;
int n, a[N + 1], tmp[N + 1];
// merge sort: file:///basic/merge-sort.cpp
int merge_sort(int l, int r) {
    if (l == r) return 0;
    int m = l + ((r - l) >> 1);
    int res = merge_sort(l, m) + merge_sort(m + 1, r);
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            res += m - i + 1;
            tmp[k++] = a[j++];
        }
    }
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    while (k--) a[l + k] = tmp[k];
    return res;
}
int main() {
    cin >> n;
    merge_sort(1, n);
    return 0;
}

杂项 · misc

1 个模板

离散化

时间复杂度： O(n \log n)

空间复杂度： O(n)

适用条件： 离线已知的坐标或数值集合，需要保留大小关系并压缩编号。

注意事项：

排名从 1 开始，重复值同排名
不保留原值间距，计算区间长度或面积时保留原坐标
新值需重新收集后构建。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 100;
int n, a[N + 1], rnk[N + 1], tmp[N + 1];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) tmp[i] = a[i];
    sort(tmp + 1, tmp + n + 1);
    int len = unique(tmp + 1, tmp + n + 1) - (tmp + 1);
    for (int i = 1; i <= n; i++) {
        rnk[i] = lower_bound(tmp + 1, tmp + len + 1, a[i]) - tmp;
    }
    return 0;
}

比赛工具 · contest

1 个模板

快速读写

时间复杂度： O(L)（L 为实际读取或输出的字符数）

空间复杂度： O(1)（固定宽度 int）

适用条件： GNU 或兼容环境中的非交互式 int 整数读写，输入值在 int 范围内。

注意事项：

getchar_unlocked 等接口不是标准 C++
read 返回 false 表示 EOF，write 不自动输出分隔符
不要与关闭同步后的 C++ 流混用。

#include <bits/stdc++.h>
using namespace std;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock
#endif
inline bool read(int &x) {
    bool neg = false;
    int ch = getchar_unlocked();
    while (ch < '0' || '9' < ch) {
        if (ch == EOF) return false;
        if (ch == '-') neg = true;
        ch = getchar_unlocked();
    }
    x = 0;
    if (neg) {
        while ('0' <= ch && ch <= '9') {
            x = x * 10 - (ch - '0');
            ch = getchar_unlocked();
        }
    } else {
        while ('0' <= ch && ch <= '9') {
            x = x * 10 + (ch - '0');
            ch = getchar_unlocked();
        }
    }
    return true;
}
inline void write(int x) {
    int len = 0;
    int buf[10];
    if (x < 0) {
        putchar_unlocked('-');
        do {
            buf[len++] = '0' - x % 10;
            x /= 10;
        } while (x);
    } else {
        do {
            buf[len++] = '0' + x % 10;
            x /= 10;
        } while (x);
    }
    while (len--) putchar_unlocked(buf[len]);
}
int main() {}

STL 速查

以 C++17 为基准；示例默认放在函数体内，已包含 <bits/stdc++.h> 并使用 using namespace std;。 <bits/stdc++.h> 是 GNU 扩展，比赛编译器及语言版本以现场环境为准。复杂度中的 n 表示当前元素数；字符串比较、哈希等操作还需计入字符串长度。

容器选型 · 排序与去重 · 二分与离散化 · 数值与排列 · 迭代器失效

容器选型

容器	常用操作与复杂度	易错点
`vector<T>`	下标 O(1)，尾部插入均摊 O(1)，中间插入/删除 O(n)	`reserve` 只改容量，不能让下标越过 `size()`；扩容会使旧引用和迭代器失效
`array<T, N>`	固定长度，下标 O(1)	`array<int, N> a{};` 会把整型元素初始化为零
`string`	下标 O(1)，`substr(pos, len)` 复制指定片段	`find` 失败返回 `string::npos`；`substr` 第二个参数是长度
`deque<T>`	两端插入/删除 O(1)，下标 O(1)	不是连续内存；修改两端后不要沿用旧迭代器
`stack<T>`	`push/pop/top`，默认底层 `deque` 时 O(1)	取栈顶前先判空；`pop()` 不返回被删除的值
`queue<T>`	`push/pop/front/back`，默认底层 `deque` 时 O(1)	BFS 常用；取队首前先判空
`priority_queue<T>`	`top` O(1)，`push/pop` O(log n)	默认大根堆，不支持直接删除任意元素或修改优先级
`set/map`	按键查找、插入、按键删除 O(log n)	唯一键；`map::operator[]` 在缺少键时会插入默认值
`multiset/multimap`	按键查找 O(log n)，删除全部匹配项 O(log n + k)	`erase(value)` 会删掉所有等价键；删除一个时传迭代器
`unordered_set/map`	单次查找/插入/删除平均 O(1)，最坏 O(n)	无序；哈希退化可能超时，`reserve` 不保证避免碰撞
`bitset<N>`	定长位集合，支持按位运算和 `count()`	`N` 是编译期常量；下标也需要满足范围

vector：容量与长度

vector<int> a;
a.reserve(100);           // a.size() 仍为 0，不能写 a[0]
a.push_back(7);
a.resize(3, 0);           // 现在是 {7, 0, 0}
assert(a.size() == 3 && a[0] == 7 && a[2] == 0);

clear() 清空元素，但不保证归还容量。二维数组用 vector<vector<int>> a(n, vector<int>(m));；需要连续内存和较少分配时，可以用一维数组通过 i * m + j 访问。

map / set：查找与删除

map<int, int> frequency;
++frequency[5];                          // 计数时允许自动插入
assert(frequency.find(9) == frequency.end());
assert(frequency.size() == 1);           // find 不会插入 9

multiset<int> values{2, 2, 5};
auto it = values.find(2);
if (it != values.end()) values.erase(it); // 只删一个 2
assert(values.count(2) == 1);

set 元素和 map 的键不能通过迭代器直接修改；需要改变键时，先删除再插入。 contains 是 C++20 接口；C++17 中判断存在应使用 find(key) != end()。 set/map 自定义比较器也会决定哪些键被视为相同：两个方向的比较都为假即等价。这些语义见 C++ 关联容器要求。

priority_queue：小根堆与过期状态

using State = pair<long long, int>;
priority_queue<State, vector<State>, greater<State>> heap;
heap.push({7, 2});
heap.push({3, 1});
auto [distance, vertex] = heap.top();
heap.pop();
assert(distance == 3 && vertex == 1);

pair 默认按第一项、第二项依次比较。Dijkstra 弹出 (d, u) 后先判断 d != dist[u]，过期状态直接跳过；不要假设同一个顶点只会被压入堆一次。Dijkstra 本身要求边权非负。

string / unordered_map

string text = "icpc-final";
assert(text.find("xyz") == string::npos);
assert(text.substr(5, 5) == "final");

unordered_map<int, int> counts;
counts.max_load_factor(0.7f);
counts.reserve(1000);                 // 已知规模时减少后续 rehash
++counts[42];
assert(counts.at(42) == 1);

哈希表遍历顺序不能作为答案顺序；需要排序后输出。修改哈希表时可能触发 rehash，使已有迭代器失效；平均与最坏复杂度的区别见无序关联容器要求。

排序、去重与删除

STL 范围通常使用左闭右开区间 [first, last)；end() 指向末尾之后，不能解引用。

操作	语义 / 复杂度
`sort(first, last)`	升序，O(n log n) 比较；不保证相等项的原相对顺序
`stable_sort(first, last)`	保留等价项相对顺序；额外内存足够时 O(n log n)，否则最多 O(n log² n) 比较
`reverse(first, last)`	反转区间，O(n)
`unique(first, last)`	把连续相等项合并，O(n)，返回逻辑新末尾；不修改容器长度
`remove(first, last, x)`	把不等于 `x` 的元素移到前面，O(n)；还需要配合 `erase` 缩短容器
`nth_element(first, first + k, last)`	平均 O(n)，把下标 `k` 的元素放到排序后应在的位置，两侧并未排序
`min_element/max_element`	O(n)；空范围返回 `last`，取值前需判空

vector<int> a{3, 1, 3, 2, 2};
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
assert((a == vector<int>{1, 2, 3}));
a.erase(remove(a.begin(), a.end(), 2), a.end());
assert((a == vector<int>{1, 3}));

比较器必须满足严格弱序，不能使用 <=，也不能在排序途中改变比较依据。浮点数用“差小于 eps 就相等”的比较器可能破坏传递性，不适合直接用于 sort/set。要求见 C++17 排序算法。

vector<pair<int, int>> a{{1, 2}, {2, 3}, {1, 4}};
sort(a.begin(), a.end(), [](const auto& x, const auto& y) {
    if (x.first != y.first) return x.first < y.first;
    return x.second > y.second;       // 第一项升序，第二项降序
});
assert(a.front() == make_pair(1, 4));

二分与离散化

对升序序列：lower_bound(x) 找第一个 >= x，upper_bound(x) 找第一个 > x。区间应与使用的比较规则一致；先排序是竞赛中最常见的准备方式。

vector<int> a{1, 2, 2, 4};
auto left = lower_bound(a.begin(), a.end(), 2);
auto right = upper_bound(a.begin(), a.end(), 2);
assert(left - a.begin() == 1);
assert(right - left == 2);           // 值为 2 的元素数
assert(lower_bound(a.begin(), a.end(), 9) == a.end());

set<int> s{1, 2, 4};
auto it = s.lower_bound(3);         // 使用成员函数，O(log n)
assert(it != s.end() && *it == 4);

不要对 set/map 调用通用 lower_bound(begin, end, x) 来追求 O(log n)：比较次数虽然是对数级，非随机访问迭代器的移动仍可能是线性的。distance(s.begin(), it) 也可能是 O(n)。见 C++17 二分算法。

vector<int> original{40, -5, 40, 9};
vector<int> values = original;
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
vector<int> rank;
for (int x : original) {
    rank.push_back(int(lower_bound(values.begin(), values.end(), x) - values.begin()));
}
assert((rank == vector<int>{2, 0, 2, 1}));

离散化保留大小关系，不保留原始数值间的距离；计算区间长度、面积时仍需使用原坐标。

数值、排列与位操作

vector<int> a{1000000000, 1000000000, 1000000000};
long long sum = accumulate(a.begin(), a.end(), 0LL);
assert(sum == 3000000000LL);
vector<int> index(4);
iota(index.begin(), index.end(), 0);
assert((index == vector<int>{0, 1, 2, 3}));
assert(gcd(18, 24) == 6);
assert(lcm(6LL, 8LL) == 24);

accumulate 的累加类型由初始值决定，不能指望赋给 long long 自动挽救内部整型溢出。 gcd/lcm 从 C++17 起提供；输入绝对值以及 lcm 的结果需在相应类型中可表示。累加规则见 C++17 accumulate。

vector<int> p{1, 1, 2};
sort(p.begin(), p.end());
int permutations = 0;
do {
    ++permutations;
} while (next_permutation(p.begin(), p.end()));
assert(permutations == 3);             // 从有序序列开始，重复值不会产生重复排列

unsigned long long mask = 1ULL << 40;
assert(__builtin_popcountll(mask) == 1);
assert(__builtin_ctzll(mask) == 40);   // ctz/clz 对 0 调用是未定义行为

__builtin_* 是 GNU 扩展；C++20 的 std::popcount、std::countr_zero 不能直接当作 C++17 接口。移位量必须小于类型位宽，避免先用 int 的 1 << k 再转换为 64 位。内建位操作的限制见 GCC Bit Operation Builtins。

迭代器、引用与复制

场景	需要记住的规则
`vector` 扩容	旧元素的迭代器、引用、指针全部失效；预留容量只能减少扩容
`vector` 插入但未扩容	插入位置及之后的迭代器/引用失效，旧 `end()` 也不能继续用
`vector::erase`	删除位置及之后的迭代器/引用失效；返回下一个有效位置
`map/set` 插入	不会使已有元素的迭代器/引用失效
`map/set` 删除	被删除元素的迭代器/引用失效，其他元素不受影响
哈希表 `rehash`	迭代器失效，已有元素的引用/指针仍有效；删除元素后对应引用当然失效

vector 的详细规则见 C++17 vector modifiers。

vector<int> a{1, 2, 3, 4};
for (auto it = a.begin(); it != a.end(); ) {
    if (*it % 2 == 0) it = a.erase(it);
    else ++it;
}
assert((a == vector<int>{1, 3}));

map<int, int> counts{{1, 2}};
for (auto& [key, value] : counts) {
    value += key;                    // 引用绑定；auto [key, value] 会复制
}
assert(counts.at(1) == 3);

传大型 vector/string 时优先使用 const T&；只遍历不修改时写 const auto&。 vector<bool> 的元素是代理对象，并非普通 bool&，需要普通可寻址存储时可改用 vector<char>。

ICPC 比赛注意事项

这份清单用于赛前准备、编码和提交前复查；代码以 GNU C++17 为例。资料携带形式、页数、编译器版本和可用工具以本场比赛规定为准。

开题与分工 · 数值与取模 · 边界与初始化 · 算法适用条件 · 调试与提交

开题与分工

先确认输入是否有 T、是否读到 EOF、是否有结束标记，以及多测的总规模限制。
明确下标从 0 还是 1 开始，区间端点是否包含，图是否有向，是否允许重边、自环和负边。
先估时间与空间复杂度，再上机；O(n²) 在 n = 2 × 10^5 时通常需要换思路。
不把“每秒能跑固定次数”当作保证；数据结构、常数、内存访问和评测环境都会影响时间。
队友复核关键不变量和边界；卡题时写清当前结论与反例，再安排下一步。
赛前熟悉编译、运行、重定向输入、对拍和资料查找方式；实际提交前再核对题号。

数值、溢出与取模

运算前提升类型

int n = 1000000000;
long long square = 1LL * n * n;       // 先提升，不能写成 long long square = n * n
assert(square == 1000000000000000000LL);

long long a = 4000000000000000000LL;
long long b = 3;
__int128 product = (__int128)a * b;   // GNU 扩展；乘完后不能强转回溢出的 long long
assert(product / b == a);

在常见 32 位 int、64 位 long long 的比赛环境中，上界分别约为 2.1 × 10^9 和 9.22 × 10^18；需要精确边界时用 numeric_limits<T>。
有符号整数溢出是未定义行为；仅修改接收结果的变量类型无法修复中间运算溢出。
abs(LLONG_MIN) 无法用 long long 表示；取绝对值前应确认输入范围。
1LL << k 仍需检查移位范围；一般掩码优先使用无符号类型并确保 k < 64。

表达式的不可表示结果及未定义行为见 C++17 expressions。

无穷大与不可达状态

const long long INF = numeric_limits<long long>::max() / 4;
long long distance = INF;
long long weight = 7;
if (distance != INF) distance += weight; // 不对不可达状态直接转移
assert(distance == INF);

INF 必须大于所有合法答案，并留出运算余量；不能机械照抄某个常量。上面的加法仍以有限距离与边权之和在类型范围内为前提。

负数取模、乘法和逆元

const long long MOD = 1000000007;
long long x = -8;
long long normalized = (x % MOD + MOD) % MOD;
assert(normalized == MOD - 8);

long long a = 1000000006;
long long b = 1000000006;
long long product = (long long)((__int128)a * b % MOD);
assert(product == 1);

MOD 应为正数；(x % MOD + MOD) % MOD 还要求加法本身不溢出，模数接近 LLONG_MAX 时应使用更宽类型或分支归一化。
模意义下不能直接除法：a / b 通常要改成乘 b 的逆元，且逆元存在要求 gcd(b, MOD) = 1。
使用 b^(MOD-2) 求逆元，需确保 MOD 是质数且 b 不被 MOD 整除；不能套用于任意模数。
负数整数除法向零截断，不等于数学上的向下取整；(a + b - 1) / b 的常见上取整写法适用于 a >= 0, b > 0，还需防止加法溢出。

浮点数

比较精度按题目绝对/相对误差要求选择，1e-9 不是通用答案。
比较大小可考虑 abs(a - b) <= eps * max(1.0, max(abs(a), abs(b)))，但不直接拿这种近似相等规则做排序比较器。
sqrt/acos 等函数先确认定义域；几何叉积、平方距离先估乘法上界，能用整数时优先用整数。
fixed << setprecision(k) 表示保留小数点后 k 位，普通 setprecision(k) 表示有效数字位数。

边界、初始化与多测

项目	提交前检查
数组下标	使用 `1..n` 时至少开到 `n + 1`；访问 `r + 1` 时还要留额外空间
区间约定	STL 使用 `[l, r)`；前缀和与树状数组模板通常有自己的闭区间约定，先对齐再组合
空容器	调用 `front/back/top/pop` 或解引用查找结果前先判空/判 `end()`
二分答案	单调方向、初始可行/不可行边界、循环退出后的答案位置都要明确
初始化	局部基本类型变量要赋初值；数组开大不等于已经设置成当前算法需要的初值
多组测试	清空邻接表、边计数、队列/堆、访问标记、入度、DP 状态和答案
清理规模	若上一组更大，避免旧边或旧状态残留；需要时记录实际使用过的下标
内存	估算元素数量 × 单元素字节数；二维容器和邻接表还存在额外开销
递归	长链 DFS 可能耗尽调用栈；深度无保证时考虑显式栈

memset 按字节填充，不能用 memset(a, 1, sizeof a) 代表每个 int 都是 1。需要设置整型数值时优先使用 fill，不要对 vector/string 等非平凡对象使用 memset。

vector<int> distance(5);
fill(distance.begin(), distance.end(), -1);
assert(distance[0] == -1 && distance[4] == -1);

vector<int> prefix(4, 0);
vector<int> a{2, 3, 5};
for (int i = 0; i < int(a.size()); ++i) prefix[i + 1] = prefix[i] + a[i];
int l = 1, r = 3;                    // 原数组的 [l, r)
assert(prefix[r] - prefix[l] == 8);

避免空容器时计算 size() - 1 后与有符号整数混用；例如倒序循环可以先转换长度：

vector<int> a;
int visits = 0;
for (int i = int(a.size()) - 1; i >= 0; --i) ++visits;
assert(visits == 0);                 // 先确认长度能放入 int

常见算法的适用条件

算法 / 模板	使用前确认
普通 BFS	每条边代价相同；通常首次入队时标记，避免重复入队
0-1 BFS	边权只能是 0 或 1；对应从双端队列不同端加入
Dijkstra	边权非负；注意堆中过期状态、距离类型和不可达输出
Bellman-Ford / SPFA	可有负边；检查可达负环，SPFA 最坏可到 O(nm)
Floyd	三重循环中 `k` 在最外层；不可达距离相加前先判断
拓扑排序	仅对 DAG 存在完整拓扑序；输出顶点数不足 `n` 表示有环
Kruskal / Prim	检查是否连通；不连通时得到森林，不能当作完整生成树
LCA / 树上 DFS	树的根、深度、祖先表边界，以及是否需要覆盖多棵树
0/1 背包	一维优化容量倒序，避免同一物品重复使用
完全背包	一维优化容量通常正序；根据价值/数量语义确定初始状态
前缀和 / 差分	下标、端点、数据类型；差分的 `r + 1` 需要额外位置
离散化	仅保序，区间长度与面积不能直接用离散编号代替原坐标

本地调试与提交清单

先用比赛对应的标准编译；调试示例：

g++ -std=c++17 -O2 -Wall -Wextra -Wshadow main.cpp -o main
./main < input.txt

定位越界、悬空访问、部分未定义行为时，单独使用调试构建：

g++ -std=c++17 -O1 -g -Wall -Wextra -Wshadow \
  -fsanitize=address,undefined -fno-omit-frame-pointer main.cpp -o main-debug
./main-debug < input.txt

检测工具会改变运行时间和内存占用，也无法发现全部逻辑错误；性能以正常构建为准。参数说明见 GCC Instrumentation Options。

先跑样例，再测最小规模、单元素、全相等、严格单调、重复值、负数和极值。
图论额外测试：不连通、长链、星形、重边、自环，以及题目允许的边权边界。
写一个小规模暴力，对拍随机输入；失配时保留随机种子和输入，再缩小反例。
检查多组测试状态是否互相影响，调试输出是否进入标准输出，输出格式是否匹配题目。
确认修改的是最终提交文件，选择了正确题号、语言和标准版本。
WA 优先复核题意、边界与初始化；TLE 复核复杂度及重复工作；RE 复核下标、空容器、失效引用和栈深。

常用程序骨架（题目没有多测时去掉读取 T 的部分）：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (auto& x : a) cin >> x;
        cout << accumulate(a.begin(), a.end(), 0LL) << '\n';
    }
}

关闭同步后避免混用 C 的 scanf/printf 与 C++ 流；'\n' 不强制刷新，endl 会刷新。交互题应按协议主动刷新输出，不能直接照搬普通题的缓冲假设。

自动更新

推送到 main 后，GitHub Actions 会自动同步目录、所有已被 Git 跟踪的 .cpp 文件和 docs/ 下的 Markdown 资料，包括新增、修改、重命名和删除；只有 README 内容变化时才会提交。也可以在 Actions → Update README → Run workflow 手动运行。

本地预览：python3 scripts/generate_readme.py；检查是否同步： python3 scripts/generate_readme.py --check。新增文件需先执行 git add。

模板头部支持 Name、Time、Space、Conditions、Notes 五个字段，分别表示名称、时间复杂度、空间复杂度、适用条件和注意事项。将这些字段写在源文件开头的注释区、#include 之前；名称缺失时使用文件名，其余字段缺失时显示“未标注”。 README 展示整理后的说明，源码块自动隐藏元数据注释；普通注释和代码内容保留。字段内容支持 Markdown 和 LaTeX：复杂度使用行内公式，适用条件和注意事项支持列表、多段文字与独立公式；写法见维护说明。

维护参考资料时直接编辑 docs/*.md，每份文档以 # 标题 开头；README 会自动收录全文。

自动生成标记之间的内容会被覆盖，介绍及本节等标记外的文字可以自由编辑。

oi-algs

资料导航

目录

基础算法 · basic（8）

搜索 · search（1）

数据结构 · ds（8）

图论 · graph（12）

动态规划 · dp（7）

数学 · math（8）

杂项 · misc（1）

比赛工具 · contest（1）

C++ 源码

基础算法 · basic

搜索 · search

数据结构 · ds

图论 · graph

动态规划 · dp

数学 · math

杂项 · misc

比赛工具 · contest

容器选型

vector：容量与长度

map / set：查找与删除

priority_queue：小根堆与过期状态

string / unordered_map

排序、去重与删除

二分与离散化

数值、排列与位操作

迭代器、引用与复制

开题与分工

数值、溢出与取模

运算前提升类型

无穷大与不可达状态

负数取模、乘法和逆元

浮点数

边界、初始化与多测

常见算法的适用条件

本地调试与提交清单

自动更新