八级编程题必备代码模板
搜索知识点 /

八级编程题必备代码模板

GESP 八级编程题（每场 2 道，每道 25 分，共 50 分）是拉开差距的关键。把近几届真题摊开看——202403 接竹竿、202406 空间跳跃·最远点对、202412 排队·树上移动、202509 最小生成树·最短距离、202603 子图最短路——反复考查的算法其实就这 10 个模板。

背多分清单

把下面 10 段 C++17 模板背熟、能闭眼默写，八级编程题基本全覆盖。考场遇到新题，先做"这题该套哪个模板"的判断，再填细节。

八级编程题必备模板地图

真题 → 模板 速查表

真题（届次）考点本章模板
202509 最小生成树求 MST / 删边后 MST68.1 并查集 + 68.2 Kruskal
202509 最短距离单源/两点最短路68.3 Dijkstra
202603 子图最短路多子图最短路求和68.3 Dijkstra + 68.9 前缀和
202406 最远点对树上不同颜色最远68.5 树的直径
202412 树上移动树+限制条件遍历68.5 树的直径 + DFS
202412 排队捆绑排列计数（取模）68.7 组合数
202406 空间跳跃坐标/高度差计算68.10 方程/几何
202403 接竹竿模拟/栈 + 去重68.9 前缀和思想

68.1 并查集 Union-Find（底层设施）

并查集用来维护"等价集合"：合并两个集合、查询两点是否连通，近乎 O(1)O(1)。它是 Kruskal 最小生成树 和一切连通性判断的底层设施，必须先背。

核心操作：find 带路径压缩，unite 按秩合并。

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

const int N = 100005;
int fa[N], rnk[N];

void init(int n) {                       // 初始化：每个点自成一族
    for (int i = 1; i <= n; i++) fa[i] = i, rnk[i] = 0;
}
int find(int x) {                        // 路径压缩：把路径上节点直接挂到根
    return fa[x] == 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 (rnk[x] < rnk[y]) swap(x, y);
    fa[y] = x;
    if (rnk[x] == rnk[y]) rnk[x]++;
    return true;
}
bool same(int x, int y) { return find(x) == find(y); }

int main() {
    int n = 5; init(n);
    unite(1, 2); unite(3, 4); unite(2, 3);
    cout << (same(1, 4) ? "连通" : "不连通") << "\n"; // 连通
    return 0;
}
易错
  • init 必须跑到 n，别只跑到用到的点；
  • find 里一定写 fa[x] = find(fa[x])（路径压缩），否则会退化成 O(n)O(n)；
  • 多组测试数据时记得每组的 init。

68.2 Kruskal 最小生成树（202509 最小生成树）

思想：把所有边按权值从小到大排序，依次选不会成环的边（用并查集判断），选满 n−1n-1 条即得到 MST。时间复杂度 O(mlog⁡m)O(m\log m)。

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

const int N = 100005;
struct Edge { int u, v, w; } e[N];
int fa[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e + 1, e + m + 1, [](Edge a, Edge b) { return a.w < b.w; }); // 边按权值升序
    long long sum = 0; int cnt = 0;
    for (int i = 1; i <= m; i++) {
        int u = find(e[i].u), v = find(e[i].v);
        if (u != v) { fa[u] = v; sum += e[i].w; cnt++; }   // 不连通才选
        if (cnt == n - 1) break;                          // 已选够 n-1 条
    }
    if (cnt < n - 1) cout << -1 << "\n";                  // 图不连通，MST 不存在
    else cout << sum << "\n";
    return 0;
}
202509 真题思路：删边后 MST 权值和

真题要求"移除第 ii 条边后，剩余图 MST 的权值和"。思路：先跑一遍 Kruskal 得到原 MST，并标记树边集合。

  • 删的是非树边：MST 不变，答案 = 原 MST 权值和；
  • 删的是树边：该边不再是树边，需判断剩余图是否仍连通（不连通输出 −1-1），否则重新求一次 MST。 数据范围 n,m≤105n,m\le 10^5 时，朴素"每删一条重跑一次"会超时，需用倍增/LCA 预处理每条树边对应的"环上最大非树边"来 O(1)O(1) 替换——但Kruskal 主框架就是上面这段，务必先背熟。
易错
  • 边权可能很大，用 long long 存 sum；
  • 有重边时 Kruskal 天然兼容（都排进去了）；
  • 不连通要特判输出 −1-1（很多题这么要求）。

68.3 Dijkstra 堆优化最短路（202509 最短距离 / 202603 子图最短路）

思想：从起点出发，每次用优先队列（小根堆）取当前距离最小的点去松弛邻居。适合非负权图，单源最短路。时间复杂度 O((n+m)log⁡n)O((n+m)\log n)。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100005;
const ll INF = 1e18;
vector<pair<int, ll>> g[N];   // 邻接表：{到达点, 边权}
ll d[N];

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

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; ll w; cin >> u >> v >> w;
        g[u].push_back({v, w}); g[v].push_back({u, w}); // 无向图
    }
    dijkstra(1, n);
    for (int i = 1; i <= n; i++) cout << d[i] << " \n"[i == n];
    return 0;
}
202509 真题思路：最短距离

该题图极大（N=1018N=10^{18}），但边权只取决于两点编号是否互质：互质边长 pp，否则 qq。观察性质即可 O(1)O(1) 回答，不必建图——核心是"先判断用哪种最短路/能否直接算"的建模能力，Dijkstra 框架仍是这类题的保底工具。

易错
  • 有负权边绝不能用品 Dijkstra，改用 68.4 Floyd 或 Bellman-Ford；
  • INF 要足够大（1e18），且松弛时防止 d[u]+w 溢出；
  • C++17 结构化绑定 auto [v, w] 可用，注意 g 是 pair<int, ll>。

68.4 Floyd 多源最短路

思想：用邻接矩阵 d[i][j]，枚举中转点 kk 逐步松弛。一次求出所有点对最短路。时间复杂度 O(n3)O(n^3)，适合 n≤200n\le 200 的稠密图或"任意两点"询问。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 205;
const ll INF = 1e18;
ll d[N][N];

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
    for (int i = 1; i <= m; i++) {
        int u, v; ll w; cin >> u >> v >> w;
        d[u][v] = d[v][u] = min(d[u][v], w); // 无向图，重边取最小
    }
    for (int k = 1; k <= n; k++)            // 必经中转点（k 必须在最外层）
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (d[i][k] < INF && d[k][j] < INF)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    // 之后 d[i][j] 即 i 到 j 的最短路
    return 0;
}
记忆口诀

循环顺序必须是 k → i → j（中转点 kk 在最外层），写反就错了。

68.5 树的直径 / 树上最远点对（202406 最远点对）

思想：树上任意两点的最远距离（直径），可通过两次 DFS/BFS 求得：先从任一点找最远点 aa，再从 aa 找最远点，距离即为直径。时间复杂度 O(n)O(n)。

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> g[N];
int far, maxd;

void dfs(int u, int p, int dep) {
    if (dep > maxd) { maxd = dep; far = u; }
    for (int v : g[u]) if (v != p) dfs(v, u, dep + 1);
}

int main() {
    int n; cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v); g[v].push_back(u);
    }
    maxd = -1; dfs(1, 0, 0);   // 第一遍：找最远点 far
    int a = far;
    maxd = -1; dfs(a, 0, 0);   // 第二遍：从 far 再找最远点
    cout << "树的直径(边数) = " << maxd << "\n";
    return 0;
}
202406 真题思路：最远点对（不同颜色）

要求"相距最远的一对不同颜色节点"。技巧：两次 DFS 的端点 a、b 中，必有一个是某种颜色的最远点。分别记录从 a 出发最远的白点距离 wb_a、最远的黑点距离 bb_a，从 b 出发同理；答案 = max⁡(wba+bbb, bba+wbb)\max(wb_a+bb_b,\ bb_a+wb_b)。

易错
  • 无向树 DFS 必须传父节点 p 并 if (v != p) 防回头，否则死循环；
  • 权在"边上"时把 dep+1 换成 dep+w；
  • 节点编号从 1 开始，数组开到 n+5n+5。

68.6 倍增 · 快速幂（含模运算）

思想：把指数 bb 按二进制拆开，平方累乘，把 aba^b 从 O(b)O(b) 降到 O(log⁡b)O(\log b)。是组合数取模、哈希等子模块的基石。

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

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

int main() {
    cout << qpow(2, 10, 1000000007) << "\n"; // 1024
    return 0;
}
易错
  • 全程 % mod，包括初始 res = 1 % mod 和 a %= mod，防止 a*a 溢出 long long；
  • 模数 mod 为质数时，逆元 = qpow(x, mod-2, mod)（费马小定理），用于 68.7。

68.7 组合数与杨辉三角（取模，202412 排队）

思想：组合数 C(n,k)C(n,k) 在取模下有两种求法——nn 小用杨辉三角递推；nn 大用"阶乘 + 逆元"。

方法一：杨辉三角递推（适合 n≤2000n\le 2000）

#include <bits/stdc++.h>
using namespace std;
const int N = 2005, MOD = 1000000007;
long long C[N][N];

void initC(int n) {                  // 预处理 C[i][j] % MOD
    for (int i = 0; i <= n; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
    }
}

方法二：阶乘 + 逆元（适合 n≤105n\le 10^5）

const int N = 100005, MOD = 1000000007;
long long fac[N], inv[N];
ll qpow(ll a, ll b) { ll r = 1 % MOD; a %= MOD; while (b) { if (b&1) r = r*a%MOD; a = a*a%MOD; b >>= 1; } return r; }
void initFac(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % MOD;
    inv[n] = qpow(fac[n], MOD - 2);                 // 费马小定理求逆元
    for (int i = n - 1; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
}
ll comb(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fac[n] * inv[m] % MOD * inv[n-m] % MOD;
}
202412 真题思路：排队（捆绑排列）

"mm 对同学必须相邻" → 把每对捆绑成一个块，总元素数变为 n−mn-m。排列数 = (n−m)!(n-m)!，再乘每块内部 2 种顺序 2m2^m。用上面的 fac 与 comb 取模即可。注意若出现 a 在 b 前且 b 在 a 前 这类矛盾（如样例3），应输出 0。

易错
  • 取模下"除法"要用逆元，不能直接 /；
  • MOD 必须是质数才能用费马小定理求逆元；
  • 多次询问先 init 一次，别每次重算。

68.8 全排列 next_permutation（排列枚举）

思想：next_permutation 按字典序生成下一个排列，配合 do...while 可枚举全排列。适合 n≤8n\le 8 的暴力枚举题。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a[] = {1, 2, 3};
    sort(a, a + 3);                  // 必须先从最小字典序开始
    int cnt = 0;
    do {
        for (int x : a) cout << x << " ";
        cout << "\n"; cnt++;
    } while (next_permutation(a, a + 3));
    cout << "共 " << cnt << " 种排列\n"; // 6
    return 0;
}
易错
  • 枚举前务必 sort 到最小字典序，否则会漏掉前半部分排列；
  • do...while 而非 while，保证初始排列也被处理；
  • 要"所有排列"用 next_permutation，要"第 k 个"可用 prev_permutation 或康托展开。

68.9 前缀和 & 差分（优化必杀）

思想：前缀和把"区间求和"从 O(n)O(n) 降到 O(1)O(1)；差分把"区间加值"从 O(n)O(n) 降到 O(1)O(1)，是八级"算法优化"题的高频手段。

一维前缀和

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

二维前缀和

// 子矩阵 (x1,y1)~(x2,y2) 和 = s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]
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];

一维差分

// 区间 [l, r] 都加 v：打标记后前缀和还原
b[l] += v; b[r+1] -= v;
for (int i = 1; i <= n; i++) b[i] += b[i-1];
易错
  • 前缀和下标从 1 开始，避免 l-1 越界；
  • 二维前缀和"容斥"四个系数别记错符号（+ - - +）；
  • 差分还原后在原数组上叠加，别覆盖原值。

68.10 一元一次方程 / 几何面积（代数几何保底）

八级大纲含初中代数与平面几何，编程题常需解简单方程或算图形面积（如 202406 空间跳跃涉及坐标与高度差）。

一元一次方程 ax+b=0ax+b=0

double solve1(double a, double b) { return -b / a; }   // 要求 a != 0

二元一次方程组（克莱姆法则）

// a1 x + b1 y = c1 ;  a2 x + b2 y = c2
double det = a1*b2 - a2*b1;            // 行列式，det != 0 有唯一解
double x = (c1*b2 - c2*b1) / det;
double y = (a1*c2 - a2*c1) / det;

几何常用计算

#include <cmath>
double dist(pair<double,double> A, pair<double,double> B) {
    double dx = A.first - B.first, dy = A.second - B.second;
    return sqrt(dx*dx + dy*dy);
}
double triArea(double a, double b, double c) {   // 海伦公式
    double p = (a + b + c) / 2;
    return sqrt(p * (p-a) * (p-b) * (p-c));
}
double rectArea(double w, double h) { return w * h; }
double circleArea(double r) { return acos(-1) * r * r; }
易错
  • 浮点数不要直接 == 比较，用 fabs(a-b) < 1e-9 判断相等；
  • π\pi 用 acos(-1) 比 3.14159 更精确；
  • 坐标可能是整数也可能是实数，读入用 double 更稳。

68.11 本章练习

练习说明

下面 5 道选择题考查"该用哪个模板 / 复杂度 / 易错点"。点击每题下方的"参考答案"展开。

1. 给定 nn 个点 mm 条边的带权连通无向图，求整张图的最小生成树边权和，最优应使用的算法是？

参考答案

B. Kruskal（或 Prim）。最小生成树标准解法为 Kruskal（并查集 + 排序，复杂度 O(mlog⁡m)O(m\log m)）或 Prim（堆优化 O(mlog⁡n)O(m\log n)）。Dijkstra 是最短路、Floyd 是多源最短路、并查集只是 Kruskal 的子工具，均不直接求 MST。

2. 单源最短路问题中，若图中存在负权边但没有负权环，下列哪项正确？

参考答案

Dijkstra 不再适用，应使用 Bellman-Ford 或 SPFA；若还需多源且 n≤200n\le 200，可用 Floyd。注意 Dijkstra 要求非负权，遇到负权会给出错误答案。

3. 树上求"相距最远的两个节点距离"（树的直径），时间复杂度与做法是？

参考答案

两次 DFS/BFS，O(n)O(n)。从任一点找最远点 aa，再从 aa 找最远点，距离即直径。Floyd O(n3)O(n^3) 太慢，Dijkstra 是带权图最短路非树结构。

4. 计算 C(100000,50000) mod (109+7)C(100000, 50000) \bmod (10^9+7)，最合适的方法是？

参考答案

阶乘 + 逆元（费马小定理 inv=qpow(fac,MOD−2)inv = qpow(fac, MOD-2)）。杨辉三角递推需要 O(n2)O(n^2) 空间，对 n=105n=10^5 不可行；直接递乘会溢出且无法取模除法。

5. 多次询问"数组区间 [l,r][l,r] 的和"，每次询问前数组不变，应优先用？

参考答案

一维前缀和，预处理 O(n)O(n)，每次询问 O(1)O(1)。差分适合"多次区间加值"，不适合纯区间求和；暴力每次 O(n)O(n) 在高频询问下会超时。

SShowball OI知识手册