CSP-S 必备编程模板

本章把 CSP-S 提高组复赛里反复出现、可以直接套用的核心代码片段集中成「模板库」。统计近 6 年（2019—2024）30 道复赛题，知识点覆盖率为：动态规划约 47%、贪心约 40%、图论约 30%、树约 27%、模拟约 23%、数论/组合约 20%、数据结构（栈/队列/并查集/树状数组/线段树）约 17%。 背熟下面这些模板，并能在 20 分钟内无 bug 默打出来，复赛编程题就稳了。 注意：真题不会考「裸模板」，而是「模板 + 变形 + 建模」，所以每个模板后面都附了复杂度和易错点。

所有代码默认编译选项 -std=c++17，4 空格缩进，关键行带注释。

1. 基础工具与 IO

1.1 万能头文件与常用宏

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 1e5 + 10;          // 数组大小，按题意冗余开
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int IINF = 0x3f3f3f3f;

bits/stdc++.h 在 NOI 系列 Linux 评测环境下可用，平时练习省去逐个包含头文件。

1.2 快读快写（大数据量必备）

当输入规模到 10⁶ 以上，用 scanf/cin 可能超时，用 getchar 快读。

inline int readInt() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
inline void writeInt(int x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) writeInt(x / 10);
    putchar(x % 10 + '0');
}

易错点：文件 IO 题记得 freopen("xxx.in", "r", stdin); freopen("xxx.out", "w", stdout);，文件名大小写必须与题目一致。

1.3 文件操作模板

int main() {
    freopen("problem.in", "r", stdin);
    freopen("problem.out", "w", stdout);
    // 读入、计算、输出
    fclose(stdin); fclose(stdout);
    return 0;
}

2. 排序、二分与离散化

2.1 结构体排序与自定义比较器

struct Node { int a, b; };
// 写法一：重载 <
bool operator<(const Node& x, const Node& y) { return x.a < y.a; }
// 写法二：lambda（更灵活，支持多关键字）
sort(v.begin(), v.end(), [](const Node& x, const Node& y) {
    return x.a != y.a ? x.a < y.a : x.b > y.b;   // 先按 a 升序，再按 b 降序
});

复杂度：O(n log n)。

2.2 二分答案（整数域）

「二分答案」用于求「满足条件的最小值 / 最大值」，核心是把最值问题转成判定问题 check(mid)。

// 求满足条件的最小值（最小化最大值）
int l = 1, r = 1e9, ans = -1;
while (l <= r) {
    int mid = l + (r - l) / 2;        // 防溢出写法
    if (check(mid)) { ans = mid; r = mid - 1; }
    else l = mid + 1;
}
// 求满足条件的最大值（最大化最小值）
int l = 1, r = 1e9, ans = -1;
while (l <= r) {
    int mid = l + (r - l + 1) / 2;    // 注意 +1，避免死循环
    if (check(mid)) { ans = mid; l = mid + 1; }
    else r = mid - 1;
}

易错点：求「最大值」时 mid 必须写成 l + (r - l + 1) / 2，否则 l == r-1 时会死循环。check 函数必须单调（满足则更大的也满足 / 满足则更小的也满足）。

2.3 离散化

把大范围、稀疏的坐标压缩到 1~m，常用于坐标系、权值线段树。

vector<int> xs = a;
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());   // 去重
// 查询值 x 的排名（从 1 开始）
int rank = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;

复杂度：O(n log n)。

3. 前缀和、差分

3.1 一维前缀和

for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
ll sum_lr = s[r] - s[l - 1];          // 区间 [l, r] 的和

3.2 二维前缀和

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
// 矩形 (x1,y1) 到 (x2,y2) 的和
ll sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];

3.3 一维差分（区间加、单点查）

// 区间 [l, r] 全部加 v
d[l] += v; d[r + 1] -= v;
for (int i = 1; i <= n; i++) d[i] += d[i - 1];   // 还原为原数组

易错点：下标从 1 开始；差分末尾 r+1 不要越界。

4. 数据结构

4.1 并查集（路径压缩 + 按秩合并）

维护动态连通性，Kruskal、食物链、奇偶游戏都靠它。2026 年初赛预测并查集正面考核回归，复赛更是常客。

int fa[N], rk[N];
void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i, rk[i] = 0; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }   // 路径压缩
void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (rk[x] < rk[y]) fa[x] = y;
    else { fa[y] = x; if (rk[x] == rk[y]) rk[x]++; }
}

复杂度：近似 O(α(n))（反阿克曼，几乎常数）。易错点：find 里一定要写 fa[x] = find(fa[x]) 赋值回去；带权并查集要额外维护 dis[] 并在 find 中更新。

4.2 树状数组（单点改、区间和）

int tr[N];
int lowbit(int x) { return x & -x; }
void add(int x, int v) { for (; x <= n; x += lowbit(x)) tr[x] += v; }
int query(int x) { int res = 0; for (; x; x -= lowbit(x)) res += tr[x]; return res; }
// 区间 [l, r] 和 = query(r) - query(l - 1)

易错点：下标必须从 1 开始（lowbit(0) 为 0 会死循环）。n 是全局变量或需传入。

4.3 线段树（区间和，单点改）

struct SegTree {
    int n; vector<ll> tr;
    void build(int u, int l, int r, vector<ll>& a) {
        if (l == r) { tr[u] = a[l]; return; }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid, a); build(u << 1 | 1, mid + 1, r, a);
        tr[u] = tr[u << 1] + tr[u << 1 | 1];
    }
    void update(int u, int l, int r, int p, ll v) {
        if (l == r) { tr[u] = v; return; }
        int mid = (l + r) >> 1;
        if (p <= mid) update(u << 1, l, mid, p, v);
        else update(u << 1 | 1, mid + 1, r, p, v);
        tr[u] = tr[u << 1] + tr[u << 1 | 1];
    }
    ll query(int u, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tr[u];
        int mid = (l + r) >> 1; ll res = 0;
        if (ql <= mid) res += query(u << 1, l, mid, ql, qr);
        if (qr > mid) res += query(u << 1 | 1, mid + 1, r, ql, qr);
        return res;
    }
};

易错点：数组 tr 必须开 4 倍原大小；区间修改需加懒惰标记（模板略，思路是 pushdown 下传）。

4.4 单调栈（找左右第一个更大/更小）

vector<int> st, ans(n, -1);
for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.back()] < a[i]) {   // 右侧第一个更大
        ans[st.back()] = i; st.pop_back();
    }
    st.push_back(i);
}

复杂度：O(n)。易错点：栈内存的是下标不是值，方便算距离。

4.5 单调队列（滑动窗口最值）

deque<int> q;                 // 存下标
for (int i = 0; i < n; i++) {
    while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
    q.push_back(i);
    while (q.front() <= i - k) q.pop_front();   // 踢出窗口外
    if (i >= k - 1) res.push_back(a[q.front()]);
}

复杂度：O(n)。常用于单调队列优化 DP。

4.6 堆 / 优先队列（Top-K、反悔贪心）

priority_queue<int> pq;                                          // 大根堆
priority_queue<int, vector<int>, greater<int>> pqmin;            // 小根堆
// 维护前 k 小
if ((int)pq.size() < k) pq.push(x);
else if (x < pq.top()) { pq.pop(); pq.push(x); }

4.7 ST 表（静态区间最值 RMQ）

int f[N][20];    // f[i][j]：区间 [i, i+2^j-1] 的最小值
void build() {
    for (int i = 1; i <= n; i++) f[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int ask(int l, int r) {
    int k = __lg(r - l + 1);     // C++20 的 __lg 求 log2 下取整
    return min(f[l][k], f[r - (1 << k) + 1][k]);
}

复杂度：建表 O(n log n)，查询 O(1)。只适用于不带修改的区间最值。

4.8 链式前向星建图

邻接表存图，空间常数小，图论题标配。

struct Edge { int to, next, w; } e[M];
int head[N], cnt = 0;
void addEdge(int u, int v, int w) { e[++cnt] = {v, head[u], w}; head[u] = cnt; }
// 遍历 u 的所有出边
for (int i = head[u]; i; i = e[i].next) { int v = e[i].to, w = e[i].w; }

5. 图论

5.1 Dijkstra（堆优化，单源最短路）

CSP-S 第一招牌，七年六现。

vector<pair<int, ll>> g[N];
vector<ll> dist(n + 1, INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
dist[s] = 0; pq.push({0, s});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;                 // 懒删除，跳过过期堆顶
    for (auto [v, w] : g[u]) {
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w; pq.push({dist[v], v});
        }
    }
}

复杂度：O((n + m) log n)。易错点：有负权边不能用 Dijkstra；if (d > dist[u]) continue; 不能省，否则重复松弛会退化。

5.2 SPFA（判负环）

vector<pair<int, int>> g[N];
int dist[N], inq[N], cnt[N];
queue<int> q;
// 初始化 dist 为 INF，dist[s] = 0，inq[s] = 1，q.push(s)
while (!q.empty()) {
    int u = q.front(); q.pop(); inq[u] = 0;
    for (auto [v, w] : g[u]) {
        if (dist[v] > dist[u] + w) {
            dist[v] = dist[u] + w;
            if (++cnt[v] >= n) { /* 存在负环 */ }
            if (!inq[v]) { inq[v] = 1; q.push(v); }
        }
    }
}

易错点：SPFA 在稠密图/特殊构造下会被卡成 O(nm)，正权图一律用 Dijkstra。

5.3 Floyd（多源最短路）

for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];

复杂度：O(n³)，适合 n ≤ 300。循环顺序 k 必须在最外层。

5.4 Kruskal（最小生成树）

struct E { int u, v, w; } edges[M];
sort(edges + 1, edges + m + 1, [](E a, E b) { return a.w < b.w; });
ll mst = 0; init(n);
for (int i = 1; i <= m; i++) {
    int x = find(edges[i].u), y = find(edges[i].v);
    if (x != y) { merge(x, y); mst += edges[i].w; }
}

复杂度：O(m log m)。配合并查集。

5.5 Prim（最小生成树，堆优化）

vector<pair<int, ll>> g[N];
vector<ll> dist(n + 1, INF); vector<bool> vis(n + 1, false);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
dist[1] = 0; pq.push({0, 1}); ll mst = 0;
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (vis[u]) continue; vis[u] = true; mst += d;
    for (auto [v, w] : g[u])
        if (!vis[v] && w < dist[v]) { dist[v] = w; pq.push({w, v}); }
}

复杂度：O((n + m) log n)，适合稠密图。

5.6 拓扑排序（判 DAG、DP 顺序）

vector<int> g[N]; int deg[N];
queue<int> q; vector<int> topo;
for (int i = 1; i <= n; i++) if (!deg[i]) q.push(i);
while (!q.empty()) {
    int u = q.front(); q.pop(); topo.push_back(u);
    for (int v : g[u]) if (--deg[v] == 0) q.push(v);
}
// topo.size() == n 说明无环（DAG）

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

int depth[N], up[N][20];
void dfs(int u, int fa) {
    depth[u] = depth[fa] + 1; up[u][0] = fa;
    for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
    for (int v : g[u]) if (v != fa) dfs(v, u);
}
int lca(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    for (int i = 19; i >= 0; i--) if (depth[up[x][i]] >= depth[y]) x = up[x][i];
    if (x == y) return x;
    for (int i = 19; i >= 0; i--) if (up[x][i] != up[y][i]) x = up[x][i], y = up[y][i];
    return up[x][0];
}

易错点：倍增数组第二维一般开 20（2²⁰ > 10⁶ 足够）；dfs 前 depth[0] = -1 让根节点深度为 0。

5.8 Tarjan 求强连通分量（缩点）

int dfn[N], low[N], idx = 0, scc = 0, id[N], stk[N], top = 0; bool ins[N];
vector<int> g[N];
void tarjan(int u) {
    dfn[u] = low[u] = ++idx; stk[++top] = u; ins[u] = true;
    for (int v : g[u]) {
        if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++scc;
        while (true) { int v = stk[top--]; ins[v] = false; id[v] = scc; if (v == u) break; }
    }
}

复杂度：O(n + m)。缩点后图变 DAG，再跑拓扑 DP。

6. 数论与数学

6.1 快速幂

ll qpow(ll a, ll b, ll mod) {
    ll res = 1 % mod; a %= mod;
    while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; }
    return res;
}

复杂度：O(log b)。

6.2 模逆元（费马小定理，mod 为质数）

ll inv(ll x, ll mod) { return qpow(x, mod - 2, mod); }

6.3 gcd 与扩展欧几里得

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll exgcd(ll a, ll b, ll& x, ll& y) {     // 解 a*x + b*y = gcd(a,b)
    if (!b) { x = 1; y = 0; return a; }
    ll d = exgcd(b, a % b, y, x); y -= a / b * x; return d;
}

易错点：exgcd 返回的是 gcd；求 a*x ≡ 1 (mod m) 时要求 gcd(a,m)==1。

6.4 线性筛（欧拉筛）

int prime[N], isNot[N], pcnt = 0;
void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isNot[i]) prime[++pcnt] = i;
        for (int j = 1; j <= pcnt && i * prime[j] <= n; j++) {
            isNot[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;   // 保证每个合数被最小质因子筛掉
        }
    }
}

复杂度：O(n)。

6.5 组合数预处理（阶乘 + 逆元）

ll fact[N], invf[N];
void init(int n, ll mod) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
    invf[n] = qpow(fact[n], mod - 2, mod);
    for (int i = n - 1; i >= 0; i--) invf[i] = invf[i + 1] * (i + 1) % mod;
}
ll C(int n, int m, ll mod) {
    if (m < 0 || m > n) return 0;
    return fact[n] * invf[m] % mod * invf[n - m] % mod;
}

易错点：mod 必须是质数才能用费马小定理求逆元。

6.6 矩阵快速幂

struct Mat { ll a[2][2]; };
Mat mul(Mat x, Mat y, ll mod) {
    Mat z = {};
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                z.a[i][j] = (z.a[i][j] + x.a[i][k] * y.a[k][j]) % mod;
    return z;
}
Mat mpow(Mat x, ll b, ll mod) {
    Mat r = {}; for (int i = 0; i < 2; i++) r.a[i][i] = 1;
    while (b) { if (b & 1) r = mul(r, x, mod); x = mul(x, x, mod); b >>= 1; }
    return r;
}

常用于线性递推（斐波那契、递推式加速），复杂度 O(k³ log n)，k 为矩阵阶数。

7. 字符串

7.1 KMP（模式匹配）

vector<int> getNext(string& p) {
    int m = p.size(); vector<int> nxt(m + 1);
    for (int i = 2, j = 0; i <= m; i++) {
        while (j && p[i - 1] != p[j]) j = nxt[j];
        if (p[i - 1] == p[j]) j++;
        nxt[i] = j;
    }
    return nxt;
}
vector<int> kmp(string& s, string& p) {
    vector<int> nxt = getNext(p); vector<int> pos;
    for (int i = 1, j = 0; i <= (int)s.size(); i++) {
        while (j && s[i - 1] != p[j]) j = nxt[j];
        if (s[i - 1] == p[j]) j++;
        if (j == (int)p.size()) { pos.push_back(i - p.size()); j = nxt[j]; }
    }
    return pos;
}

易错点：nxt 数组从 0 开始；匹配成功后 j = nxt[j] 继续找下一个，不能 j = 0。

7.2 字符串哈希（子串比较 O(1)）

const ull base = 131;
vector<ull> h, pw;
void initHash(string& s) {
    int n = s.size(); h.assign(n + 1, 0); pw.assign(n + 1, 1);
    for (int i = 0; i < n; i++) { h[i + 1] = h[i] * base + s[i]; pw[i + 1] = pw[i] * base; }
}
ull getHash(int l, int r) { return h[r + 1] - h[l] * pw[r - l + 1]; }   // [l, r] 0-indexed

易错点：自然溢出用 unsigned long long（自动 mod 2⁶⁴），但容易被卡，重要题用双哈希。

7.3 Trie（字典树，前缀统计）

int trie[N * 26][26], cnt = 0;
void insert(string& s) {
    int p = 0;
    for (char c : s) { int x = c - 'a'; if (!trie[p][x]) trie[p][x] = ++cnt; p = trie[p][x]; }
}
bool find(string& s) {
    int p = 0;
    for (char c : s) { int x = c - 'a'; if (!trie[p][x]) return false; p = trie[p][x]; }
    return true;
}

8. 动态规划模板

8.1 01 背包

for (int i = 1; i <= n; i++)
    for (int j = V; j >= w[i]; j--)          // 逆序！保证每件只用一次
        f[j] = max(f[j], f[j - w[i]] + v[i]);

8.2 完全背包

for (int i = 1; i <= n; i++)
    for (int j = w[i]; j <= V; j++)          // 正序！每件可用多次
        f[j] = max(f[j], f[j - w[i]] + v[i]);

8.3 多重背包（二进制优化）

vector<pair<int, int>> items;     // (w, v)
for (int i = 1; i <= n; i++) {
    int c = k[i];
    for (int p = 1; p <= c; p <<= 1) { items.push_back({w[i] * p, v[i] * p}); c -= p; }
    if (c) items.push_back({w[i] * c, v[i] * c});
}
// 之后按 01 背包处理 items

复杂度：O(n log k * V)。

8.4 最长上升子序列 LIS（O(n log n)）

vector<int> tail;
for (int x : a) {
    auto it = lower_bound(tail.begin(), tail.end(), x);
    if (it == tail.end()) tail.push_back(x); else *it = x;
}
int lis = tail.size();

8.5 区间 DP（石子合并）

// dp[i][j]：把 [i, j] 合成一堆的最小代价，sum 为前缀和
for (int len = 2; len <= n; len++)
    for (int i = 1; i + len - 1 <= n; i++) {
        int j = i + len - 1; dp[i][j] = IINF;
        for (int k = i; k < j; k++)
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
    }

8.6 树形 DP（树的直径）

int maxd = 0, far = 1;
void dfs(int u, int fa, int d) {
    if (d > maxd) { maxd = d; far = u; }
    for (int v : g[u]) if (v != fa) dfs(v, u, d + 1);
}
dfs(1, 0, 0); maxd = 0; dfs(far, 0, 0);    // 两次 DFS，maxd 即直径长度

8.7 状压 DP（旅行商 TSP）

// dp[mask][i]：已访问集合 mask，当前在城市 i 的最短路径
dp[1][0] = 0;
for (int mask = 1; mask < (1 << n); mask++)
    for (int i = 0; i < n; i++) if (mask & (1 << i))
        for (int j = 0; j < n; j++) if (!(mask & (1 << j)))
            dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + d[i][j]);

复杂度：O(n² · 2ⁿ)，适合 n ≤ 20。

9. 高精度（大整数）

当结果超过 long long（约 10¹⁸），用数组按位存储。低位在前。

// 加法：a、b 均为 vector，低位在前（a[0] 是个位）
vector<int> add(vector<int>& a, vector<int>& b) {
    vector<int> c; int carry = 0;
    for (int i = 0; i < (int)a.size() || i < (int)b.size() || carry; i++) {
        if (i < (int)a.size()) carry += a[i];
        if (i < (int)b.size()) carry += b[i];
        c.push_back(carry % 10); carry /= 10;
    }
    return c;
}

易错点：输出时要逆序；先去掉前导零。

随堂检测（默写自测）

下面 6 题，遮住代码自己默写，再展开对照。能全默对，说明模板真的背熟了。

默写并查集的 find 函数（要求带路径压缩）。
参考答案
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
解析（考点）：路径压缩把查询路径上的节点直接挂到根，把近乎 O(n) 降到近似 O(α(n))。注意必须赋值回去 fa[x] = …。
Dijkstra 的优先队列里，为什么一定要有 if (d > dist[u]) continue; 这一句？

参考答案
因为同一个节点可能被多次入队（松弛时每次更新都会 push），堆顶取出的 d 可能是过期旧值。若 d > dist[u] 说明已有更优距离，直接跳过，避免重复松弛导致退化。这是「懒删除」写法。
解析（考点）：最短路核心优化；漏写这行在多数数据下仍能过，但卡数据会 TLE/逻辑错。
01 背包和完全背包的内层循环顺序为什么相反？

参考答案
01 背包每件物品只能用一次，必须逆序遍历容量，保证更新 f[j] 时用的 f[j-w[i]] 还是上一轮（没用过第 i 件）的值；完全背包每件可用无限次，要正序，让 f[j-w[i]] 已经包含本轮第 i 件，从而复用多次。
解析（考点）：背包 DP 的状态依赖方向，是高频易错点。
线段树数组 tr 一般要开原数组大小的几倍？为什么？

参考答案
开 4 倍。线段树是近似满二叉树，叶子最多 n 个，结点总数不超过 2 * 2^ceil(log2 n) ≤ 4n。开 2 倍在退化数据下会越界。
解析（考点）：数组越界是 2023 年真题直接扣 40% 分的坑。
KMP 匹配成功后，为什么要写 j = nxt[j]; 而不是 j = 0;？

参考答案
j = nxt[j] 让模式串「滑动」到下一个可能匹配的位置，利用已匹配前缀避免从头再比，保证 O(n+m)；若写 j = 0 会退化为暴力，且可能漏掉重叠出现的模式。
解析（考点）：KMP 的 next 数组本质是「最长公共前后缀」，这是字符串高频考点。
求 LCA 前，为什么要先把较深的节点 x 提到和 y 同一深度？

参考答案
倍增只能在「深度相同」时同步上跳找分叉点。若深度不同直接跳，可能越过 LCA 或越界到 0 号祖先。先 for 循环把 x 提到 depth[y]，再一起往上跳，才能保证相遇点正好是 LCA。
解析（考点）：倍增 LCA 的预处理与查询两步，建图 / 树形题常考。

备考建议

基础算法保底、DP/图论/贪心冲分：把上面模板按「每天 3 个」的速度默写 2 遍，形成肌肉记忆。
真题优先：近 6 年 CSP-S 复赛真题至少刷 2 遍，每题贴「考点标签」（如「超速检测 = 物理建模 + 二分 + 贪心」）。
先写暴力保底分：T3/T4 不会正解也先写 O(n²) 暴力和部分分，再想优化。
模板不是答案，建模才是：近年命题从「背模板」转向「用算法解决实际问题」，重点练「把题意翻译成图 / DP 状态 / 数据结构」这一步。