算法模板

能默写的模板，才叫模板

全部用 C++17 写成，每个都用 g++ 的 -Wall -Wextra 零警告编译验证过。按分类筛选，点右上角复制；目标是「五分钟默写」，不是「收藏得全」。

速查

常用算法一览

先在这里定位：点任意一行的算法名（或右边的 ↓）就能跳到下面的模板。复杂度按常见实现给出，实际受常数影响。

算法 / 结构	复杂度	什么时候用	模板
快速读入	`O(1)` 每字符	数据量 ≥ `10⁶`，或时限卡得紧	↓
离散化	`O(n log n)`	值域很大但只关心相对大小	↓
二分 / 二分答案	`O(log V)`	有序查找，或把最优解转成判定	↓
并查集	`O(α(n))`	动态连通性、Kruskal、关系推理	↓
树状数组	`O(log n)`	单点修改 + 前缀和，码量小	↓
线段树（懒标记）	`O(log n)`	区间修改 + 区间查询	↓
ST 表	`O(1)` 查询	静态区间最值，不修改	↓
单调队列	`O(n)`	滑动窗口最值、DP 优化	↓
链式前向星	`O(1)` 加边	图论题的标准存图方式	↓
Dijkstra（堆优化）	`O(m log n)`	非负边权单源最短路	↓
SPFA	`O(km)` 最坏 `O(nm)`	有负边，或需要判负环	↓
Kruskal	`O(m log m)`	最小生成树，稀疏图首选	↓
拓扑排序	`O(n + m)`	依赖关系、DAG 上的 DP	↓
倍增 LCA	`O(n log n)` / `O(log n)`	树上两点祖先与距离	↓
字符串哈希	`O(n)` 预处理	子串相等比较、回文判定	↓
KMP	`O(n + m)`	模式匹配、求最小循环节	↓
快速幂	`O(log b)`	取模幂、矩阵幂	↓
线性筛	`O(n)`	素数表、最小质因子、积性函数	↓
exgcd / 逆元	`O(log p)`	解同余方程、模数为素数时求逆元	↓
组合数	`O(n)` 预处理	模数为素数时的 `C(n,m)`	↓
背包	`O(nV)`	01 / 完全 / 分组，注意循环方向	↓
区间 DP	`O(n³)`	区间合并、括号匹配、石子合并	↓
对拍脚本	—	提交前验证正解与暴力的差异	↓

模板

按分类筛选

快速读入

O(1)

数据量 ≥ 10⁶ 时把 cin 换成它。用 cin/cout 的话，第一行关同步就够了。

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); }
    return x * f;
}

// 用 cin 的时候只需要这一行：
// ios::sync_with_stdio(false); cin.tie(nullptr);

离散化

O(n log n)

值域 10⁹ 但只有 10⁵ 个数参与比较时，先压成排名再上数据结构。

int a[N];                  // 原数组，1-based
int b[N], m;               // 排序去重后的值

void buildDisc(int n) {    // 读入 a[1..n] 之后调用
    memcpy(b + 1, a + 1, n * sizeof(int));
    sort(b + 1, b + n + 1);
    m = int(unique(b + 1, b + n + 1) - (b + 1));   // 不同值的个数
}
inline int id(int x) {     // x 的排名，范围 1..m
    return int(lower_bound(b + 1, b + m + 1, x) - b);
}

二分 / 二分答案

O(log V)

整数二分用「左开右闭」写法不用考虑 +1 偏移；浮点二分直接跑固定次数。

// 求最小的满足 check(x) 的 x，check 满足单调性
int l = L - 1, r = R + 1;          // 答案一定在 [L, R] 内
while (r - l > 1) {
    int mid = l + (r - l) / 2;
    if (check(mid)) r = mid; else l = mid;
}
// 答案 = r；l 是最大的不满足者（可用于判断无解：r == R + 1）

// 浮点二分：固定 100 轮，够用到 1e-27
double lo = 0, hi = 1e9;
for (int t = 0; t < 100; ++t) {
    double mid = (lo + hi) / 2;
    if (check(mid)) hi = mid; else lo = mid;
}

并查集

O(α(n))

路径压缩 + 按大小合并。要维护「到根的距离」时，把 sz 换成 dis 并在 find 里累加。

int fa[N], sz[N];

void init(int n) {
    for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
}
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool merge(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) swap(a, b);
    fa[b] = a, sz[a] += sz[b];
    return true;
}

树状数组

O(log n)

只做「单点加 + 前缀和」时优先用它，比重线段树快且不容易写错。

struct BIT {
    int n; long long t[N];

    void init(int n_) {
        n = n_;
        fill(t + 1, t + n + 1, 0);
    }
    void add(int i, long long v) {
        for (; i <= n; i += i & -i) t[i] += v;
    }
    long long sum(int i) const {          // 前缀和 [1, i]
        long long s = 0;
        for (; i > 0; i -= i & -i) s += t[i];
        return s;
    }
    long long range(int l, int r) const { // 区间和 [l, r]
        return sum(r) - sum(l - 1);
    }
};

线段树（区间加 + 区间和）

O(log n)

要改乘、改赋值、维护最值或最大子段和时，改 apply 与 push 两处即可。

struct Seg {
    int n;
    long long sum[N << 2], tag[N << 2];

    void build(int p, int l, int r, long long *a) {
        tag[p] = 0;
        if (l == r) { sum[p] = a[l]; return; }
        int m = (l + r) >> 1;
        build(p << 1, l, m, a); build(p << 1 | 1, m + 1, r, a);
        sum[p] = sum[p << 1] + sum[p << 1 | 1];
    }
    void apply(int p, int l, int r, long long v) {
        sum[p] += v * (r - l + 1), tag[p] += v;
    }
    void push(int p, int l, int r) {
        if (!tag[p]) return;
        int m = (l + r) >> 1;
        apply(p << 1, l, m, tag[p]);
        apply(p << 1 | 1, m + 1, r, tag[p]);
        tag[p] = 0;
    }
    void add(int p, int l, int r, int L, int R, long long v) {
        if (L <= l && r <= R) { apply(p, l, r, v); return; }
        push(p, l, r);
        int m = (l + r) >> 1;
        if (L <= m) add(p << 1, l, m, L, R, v);
        if (R > m) add(p << 1 | 1, m + 1, r, L, R, v);
        sum[p] = sum[p << 1] + sum[p << 1 | 1];
    }
    long long query(int p, int l, int r, int L, int R) {
        if (L <= l && r <= R) return sum[p];
        push(p, l, r);
        int m = (l + r) >> 1;
        long long s = 0;
        if (L <= m) s += query(p << 1, l, m, L, R);
        if (R > m) s += query(p << 1 | 1, m + 1, r, L, R);
        return s;
    }
};

ST 表（静态 RMQ）

O(n log n) 建表 / O(1) 查询

只查询不修改时最快。改成 max 就是区间最大值，二维就是把第二维换成行。

int lg[N], st[20][N];

void build(int n, int *a) {
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) st[0][i] = a[i];
    for (int k = 1; (1 << k) <= n; ++k)
        for (int i = 1; i + (1 << k) - 1 <= n; ++i)
            st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
}
int query(int l, int r) {
    int k = lg[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

单调队列

O(n)

滑动窗口最值标准写法。DP 优化时把「值」换成 f[j] - j*w 之类的式子即可。

// 长度为 k 的滑动窗口最大值：a[1..n] -> ans[1..n-k+1]
void slidingMax(int n, int k, const int *a, int *ans) {
    int q[N], head = 1, tail = 0;   // q 存下标
    for (int i = 1; i <= n; ++i) {
        while (head <= tail && a[q[tail]] <= a[i]) --tail;
        q[++tail] = i;
        if (q[head] <= i - k) ++head;
        if (i >= k) ans[i - k + 1] = a[q[head]];
    }
}

链式前向星

O(1) 加边

比 vector 快，卡常时的标准存图方式。无向图记得加两次。

int head[N], to[M], w[M], nxt[M], tot;

void init(int n) {
    tot = 0;
    fill(head + 1, head + n + 1, 0);
}
void add(int u, int v, int c) {
    to[++tot] = v, w[tot] = c, nxt[tot] = head[u], head[u] = tot;
}
// 遍历：for (int e = head[u]; e; e = nxt[e]) { int v = to[e]; ... }

Dijkstra（堆优化）

O(m log n)

边权非负时的单源最短路。有负边就换 SPFA；求全源且 n ≤ 500 用 Floyd。

typedef pair<long long, int> pli;
long long dis[N];
bool vis[N];

void dijkstra(int s, int n) {
    fill(dis + 1, dis + n + 1, LLONG_MAX / 2);
    fill(vis + 1, vis + n + 1, false);
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    dis[s] = 0, pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            long long nd = d + w[e];
            if (nd < dis[v]) { dis[v] = nd; pq.push({nd, v}); }
        }
    }
}

SPFA（含负环判定）

O(km)，最坏 O(nm)

有负边才用。判负环看「入队次数 ≥ n」或「最短路经过边数 ≥ n」。

long long dis[N];
bool inq[N];
int cnt[N];      // 最短路经过的边数

bool spfa(int s, int n) {   // 返回 false 表示存在负环
    fill(dis + 1, dis + n + 1, LLONG_MAX / 2);
    fill(inq + 1, inq + n + 1, false);
    fill(cnt + 1, cnt + n + 1, 0);
    queue<int> q;
    dis[s] = 0, inq[s] = true, q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inq[u] = false;
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (dis[u] + w[e] < dis[v]) {
                dis[v] = dis[u] + w[e];
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return false;
                if (!inq[v]) inq[v] = true, q.push(v);
            }
        }
    }
    return true;
}

Kruskal（最小生成树）

O(m log m)

边排序 + 并查集。判连通看选中的边数是否等于 n - 1。

struct Edge { int u, v, w; } e[M];
int fa[N];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

long long kruskal(int n, int m) {   // 不连通返回 -1
    for (int i = 1; i <= n; ++i) fa[i] = i;
    sort(e + 1, e + m + 1, [](const Edge &a, const Edge &b) { return a.w < b.w; });
    long long ans = 0;
    int used = 0;
    for (int i = 1; i <= m; ++i) {
        int u = find(e[i].u), v = find(e[i].v);
        if (u == v) continue;
        fa[u] = v, ans += e[i].w;
        if (++used == n - 1) return ans;
    }
    return -1;
}

拓扑排序

O(n + m)

Kahn 算法，顺便判有向图是否成环（结果长度 < n 即存在环）。

int deg[N], ord[N];

bool topo(int n) {          // 返回 false 表示有环
    queue<int> q;
    for (int i = 1; i <= n; ++i) if (!deg[i]) q.push(i);
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        ord[++cnt] = u;
        for (int e = head[u]; e; e = nxt[e])
            if (--deg[to[e]] == 0) q.push(to[e]);
    }
    return cnt == n;
}

倍增 LCA

O(n log n) 预处理 / O(log n)

dep[0] = 0、fa[root][0] = 0，靠「深度为 0」挡住向上越界。树上的距离 = dep[u] + dep[v] - 2*dep[lca]。

const int LOG = 20;
int dep[N], fa[N][LOG];

void dfs(int u, int p) {
    dep[u] = dep[p] + 1, fa[u][0] = p;
    for (int k = 1; k < LOG; ++k) fa[u][k] = fa[fa[u][k - 1]][k - 1];
    for (int e = head[u]; e; e = nxt[e])
        if (to[e] != p) dfs(to[e], u);
}
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int k = LOG - 1; k >= 0; --k)
        if (dep[fa[u][k]] >= dep[v]) u = fa[u][k];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; --k)
        if (fa[u][k] != fa[v][k]) u = fa[u][k], v = fa[v][k];
    return fa[u][0];
}

字符串哈希

O(n) 预处理 / O(1) 比较

用 unsigned long long 的自然溢出当模数。怕被卡就换随机底数，或用双哈希（两个质数分别算）。

typedef unsigned long long ull;
const ull B = 131;          // 建议换成随机底数
ull h[N], pw[N];

void init(const char *s) {  // s 从 1 开始存
    pw[0] = 1, h[0] = 0;
    for (int i = 1; s[i]; ++i) {
        h[i] = h[i - 1] * B + (ull)s[i];
        pw[i] = pw[i - 1] * B;
    }
}
ull sub(int l, int r) {     // 子串 [l, r] 的哈希
    return h[r] - h[l - 1] * pw[r - l + 1];
}

KMP

O(n + m)

匹配用上面的 match；求最小循环节用 m - nxt[m]，能整除则循环。

// 所有字符串都从 1 开始存：s[1..n]
void getNext(const char *s, int *nxt) {
    int n = int(strlen(s + 1));
    nxt[1] = 0;
    for (int i = 2, j = 0; i <= n; ++i) {
        while (j && s[i] != s[j + 1]) j = nxt[j];
        if (s[i] == s[j + 1]) ++j;
        nxt[i] = j;
    }
}
void match(const char *t, const char *p, int *nxt) {   // 输出所有出现位置
    int n = int(strlen(t + 1)), m = int(strlen(p + 1));
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j && t[i] != p[j + 1]) j = nxt[j];
        if (t[i] == p[j + 1]) ++j;
        if (j == m) { printf("%d\n", i - m + 1); j = nxt[j]; }
    }
}

快速幂

O(log b)

第一个 1 % p 是给 p = 1 兜底的。矩阵版把乘法换成矩阵乘、初值换成单位矩阵。

long long qpow(long long a, long long b, long long p) {
    long long r = 1 % p;
    for (a %= p; b; b >>= 1, a = a * a % p)
        if (b & 1) r = r * a % p;
    return r;
}

线性筛

O(n)

顺便得到每个数的最小质因子 lp，可以在此基础上线性筛积性函数（φ、μ、约数个数）。

int primes[N], pcnt, lp[N];   // lp[i] = i 的最小质因子

void sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!lp[i]) primes[++pcnt] = lp[i] = i;
        for (int j = 1; j <= pcnt && primes[j] <= lp[i] && 1LL * i * primes[j] <= n; ++j)
            lp[i * primes[j]] = primes[j];
    }
}

exgcd 与逆元

O(log)

p 是素数时也能用费马小定理：inv(a) = qpow(a, p - 2, p)，比 exgcd 短一点。

long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (!b) { x = 1, y = 0; return a; }
    long long d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
// a 在模 p 下的逆元（要求 gcd(a, p) = 1）
long long inv(long long a, long long p) {
    long long x, y;
    exgcd(a, p, x, y);
    return (x % p + p) % p;
}

组合数（阶乘 + 逆元）

O(n) 预处理 / O(1) 查询

要求模数为素数且 n < p。模数不固定就用 Lucas，或改用递推 C(i,j)=C(i-1,j)+C(i-1,j-1)。

long long fac[N], ifac[N];
long long MOD;

long long qpow(long long a, long long b) {
    long long r = 1 % MOD;
    for (a %= MOD; b; b >>= 1, a = a * a % MOD)
        if (b & 1) r = r * a % MOD;
    return r;
}
void initComb(int n, long long p) {
    MOD = p, fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % MOD;
    ifac[n] = qpow(fac[n], MOD - 2);
    for (int i = n; i >= 1; --i) ifac[i - 1] = ifac[i] * i % MOD;
}
long long C(int n, int m) {
    if (m < 0 || m > n || n < 0) return 0;
    return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}

背包（01 / 完全）

O(nV)

只差一个循环方向：01 背包倒序，完全背包正序。多重背包二进制拆分后按 01 做。

// 01 背包：每件最多选一次 —— 体积倒序
for (int i = 1; i <= n; ++i)
    for (int j = V; j >= v[i]; --j)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

// 完全背包：每件可选无限次 —— 体积正序
for (int i = 1; i <= n; ++i)
    for (int j = v[i]; j <= V; ++j)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

// 多重背包：把 c 件拆成 1,2,4,...,余数，再按 01 做
for (int k = 1; c > 0; c -= k, k <<= 1) {
    int take = min(k, c), vv = take * v[i], ww = take * w[i];
    for (int j = V; j >= vv; --j) f[j] = max(f[j], f[j - vv] + ww);
}

区间 DP

O(n³)

按区间长度从小到大推。区间长度 ≤ 500 时可行，再大就要加平行四边形优化或换思路。

// f[l][r] 表示区间 [l, r] 的最优值
for (int i = 1; i <= n; ++i) f[i][i] = 0;
for (int len = 2; len <= n; ++len)
    for (int l = 1; l + len - 1 <= n; ++l) {
        int r = l + len - 1;
        f[l][r] = INF;
        for (int k = l; k < r; ++k)
            f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + cost(l, r));
    }

对拍脚本

—

生成器带随机种子，出错那一组可以复现。先在小数据上跑几百组，再放大数据。

# Linux / macOS
for i in $(seq 1 500); do
  ./gen $i > in.txt
  ./brute < in.txt > a.txt
  ./solve < in.txt > b.txt
  diff -q a.txt b.txt > /dev/null || { echo "WA at $i"; break; }
done

:: Windows（保存成 .bat）
for /l %%i in (1,1,500) do (
  gen.exe %%i > in.txt
  brute.exe < in.txt > a.txt
  solve.exe < in.txt > b.txt
  fc a.txt b.txt > nul || (echo WA at %%i & pause)
)

每个模板都通过了 g++ -std=c++17 -Wall -Wextra 的语法检查；空数组、N、INF 等按自己的习惯定。复制前记得把 N 改成实际需要的大小。

模板只是起点

会默写不等于会用。把它套到题上、卡住了再回来看，比在这里读十遍更有效。

找一道题练手回到专题地图