2026 年 6 月 GESP C++ 八级真题 · 逐题详解

一、单选题（每题 2 分，共 30 分）

参考答案：B B C A C D A A D A C B B C D

第 1 题

从 7 本不同的算法书和 5 本不同的数学书中选出 4 本，要求两类书都至少选 1 本，共有（ ）种不同选法。

• A. 420
• B. 455
• C. 465
• D. 495

答案：B

这类"至少各选一本"的问题，用正难则反（补集思想）最简洁。先不管限制条件，从 12 本书中任选 4 本，总方案数为 C(12, 4) = 495。再减去不满足条件的方案：全部选算法书（一本数学书都没有）的方案数为 C(7, 4) = 35；全部选数学书的方案数为 C(5, 4) = 5。因此满足"两类都至少 1 本"的方案数 = 495 − 35 − 5 = 455，选 B。

如果用正向分类讨论验证：算法书选 1 本数学书选 3 本：C(7,1)×C(5,3) = 7×10 = 70；算法书 2 本数学书 2 本：C(7,2)×C(5,2) = 21×10 = 210；算法书 3 本数学书 1 本：C(7,3)×C(5,1) = 35×5 = 175。三类相加 70 + 210 + 175 = 455，与补集法结果一致。补集法只需三次计算，正向法需要分三类分别乘再相加，在类别更多时补集法优势更明显。

第 2 题

6 个人排成一排照相，其中甲、乙两人不能相邻，共有（ ）种不同排法。

• A. 240
• B. 480
• C. 600
• D. 720

答案：B

同样使用补集思想："不相邻"的方案数 = 总方案数 − "相邻"的方案数。

总方案数：6 个人全排列，为 6! = 720 种。

甲乙相邻的方案数：使用捆绑法，把甲、乙两人捆成一个整体，与其余 4 人一起排列，相当于 5 个"单位"的全排列，共 5! = 120 种；而捆绑内部甲乙可以交换位置（甲在左或乙在左），乘以 2，得到相邻方案数 = 5! × 2 = 240 种。

因此不相邻的方案数 = 720 − 240 = 480，选 B。也可以用插空法直接计算验证：先排其余 4 人（4! = 24 种），4 人之间及两端共形成 5 个空隙，从中选 2 个空隙分别放入甲和乙（有顺序），为 A(5,2) = 5×4 = 20 种，总数 24 × 20 = 480，两种方法结果一致。

第 3 题

展开式 (x² − 1/x)⁶ 中，常数项的系数为（ ）。

• A. 6
• B. 12
• C. 15
• D. 20

答案：C

由二项式定理，(x² − 1/x)⁶ 的通项为：

T(k+1) = C(6, k) · (x²)^(6−k) · (−1/x)^k = C(6, k) · (−1)^k · x^(2(6−k)) · x^(−k) = C(6, k) · (−1)^k · x^(12−3k)

要得到常数项，需要 x 的指数为 0，即 12 − 3k = 0，解得 k = 4。代入通项：常数项 = C(6, 4) · (−1)⁴ = 15 × 1 = 15，选 C。

这类题的关键有两点：一是把两部分的 x 指数合并成关于 k 的一次式（这里是 12 − 3k），令其等于 0 解出 k；二是不要漏掉 (−1)^k 这个符号因子——本题 k = 4 为偶数，符号恰好为正，如果 k 解出来是奇数，常数项就会是负值，粗心漏掉符号是最常见的失分点。

第 4 题

下面代码用于预处理组合数，横线处应填入的是（ ）。

for (int i = 0; i <= n; i++) {    c[i][0] = c[i][i] = 1;for (int j = 1; j < i; j++)        c[i][j] = __________;}

• A. c[i - 1][j - 1] + c[i - 1][j]
• B. c[i][j - 1] + c[i - 1][j - 1]
• C. c[i - 1][j] + c[i][j + 1]
• D. c[i][j - 1] * c[i - 1][j]

答案：A

这段代码用递推方式填出杨辉三角，依据的是组合数的帕斯卡恒等式：C(i, j) = C(i−1, j−1) + C(i−1, j)。这个恒等式有直观的组合解释：从 i 个元素中选 j 个，可以按"是否选中第 i 个元素"分成两类——选中它，则还需从前 i−1 个中再选 j−1 个，方案数 C(i−1, j−1)；不选它，则要从前 i−1 个中选满 j 个，方案数 C(i−1, j)。两类互斥且穷尽所有情况，相加即得 C(i, j)。

对应到代码中就是 c[i][j] = c[i-1][j-1] + c[i-1][j]，选 A。代码里 c[i][0] = c[i][i] = 1 正是杨辉三角每行两端的边界值（任何数选 0 个和选全部都只有 1 种方案），内层循环 j 从 1 到 i−1 填中间部分，且外层 i 递增保证计算第 i 行时第 i−1 行已经全部就绪。其余选项都不符合帕斯卡恒等式的形式：B 引用了同一行尚未定义清楚的关系，C 的 c[i][j+1] 在本行内还没被计算（顺序矛盾），D 用乘法完全不符合组合数的递推性质。

第 5 题

下列程序输出的值为（ ）。

#include<iostream>usingnamespacestd;longlongqpow(longlong a, longlong b, longlong mod){longlong ans = 1 % mod;while (b) {if (b & 1)            ans = ans * a % mod;        a = a * a % mod;        b >>= 1;    }return ans;}intmain(){cout << qpow(3, 20, 17) << endl;return0;}

• A. 1
• B. 4
• C. 13
• D. 16

答案：C

程序计算的是 3²⁰ mod 17，qpow 是标准的快速幂实现：把指数 b 按二进制逐位拆解，底数 a 不断自乘平方，指数当前位为 1 时把当前的 a 乘入答案。逐轮模拟（20 的二进制是 10100）：

• 初始：ans = 1, a = 3, b = 20
• b = 20，最低位 0，不乘入；a = 3² = 9，b = 10
• b = 10，最低位 0，不乘入；a = 9² = 81 mod 17 = 13，b = 5
• b = 5，最低位 1，ans = 1 × 13 = 13；a = 13² = 169 mod 17 = 16，b = 2
• b = 2，最低位 0，不乘入；a = 16² = 256 mod 17 = 1，b = 1
• b = 1，最低位 1，ans = 13 × 1 = 13；a = 1，b = 0，循环结束

返回 13，选 C。也可以用数论性质快速验证：由费马小定理，17 是质数且 3 与 17 互质，故 3¹⁶ ≡ 1 (mod 17)，于是 3²⁰ = 3¹⁶ × 3⁴ ≡ 1 × 81 ≡ 81 mod 17 = 13。两种方法结果一致，说明快速幂的模拟没有出错。

第 6 题

归并排序每次把长度为 n 的序列分成两个规模约为 n/2 的子序列，递归排序后再用线性时间合并。该算法的时间复杂度通常为（ ）。

• A. O(n)
• B. O(n²)
• C. O(log n)
• D. O(n log n)

答案：D

归并排序的时间复杂度可以从递归树的角度分析：整个递归过程形成一棵深度约为 log₂n 的二叉树——每往下一层，序列长度减半，从 n 减到 1 需要折半 log₂n 次。而在递归树的每一层上，所有子问题的合并操作加起来恰好要处理全部 n 个元素（比如第二层是两个 n/2 的合并，第三层是四个 n/4 的合并，每层总量都是 n），也就是每层的总代价为 O(n)。层数 × 每层代价 = log n × n，得到总复杂度 O(n log n)，选 D。

也可以用递推式表达：T(n) = 2T(n/2) + O(n)，由主定理直接得出 T(n) = O(n log n)。值得一提的是，归并排序的最好、最坏、平均复杂度都是 O(n log n)，性能非常稳定（不像快速排序最坏会退化到 O(n²)），代价是需要 O(n) 的额外辅助空间。

第 7 题

在平面直角坐标系中，三角形三个顶点为 A(1,1)、B(5,2)、C(3,6)，该三角形面积为（ ）。

• A. 9
• B. 10
• C. 12
• D. 18

答案：A

用向量叉积（鞋带公式）计算最直接。以 A 为公共起点构造两个向量：AB = B − A = (5−1, 2−1) = (4, 1)，AC = C − A = (3−1, 6−1) = (2, 5)。两向量叉积的绝对值等于它们张成的平行四边形面积：

|AB × AC| = |4 × 5 − 1 × 2| = |20 − 2| = 18

三角形面积是平行四边形面积的一半：18 ÷ 2 = 9，选 A。

叉积公式 (x₁, y₁) × (x₂, y₂) = x₁y₂ − x₂y₁ 是计算几何中最基础也最重要的工具，除了求面积，它的符号还能判断点在向量的哪一侧（正为逆时针方向、负为顺时针方向），是凸包、线段相交判定等算法的核心构件。相比"求三边长再用海伦公式"的做法，叉积法全程只有整数运算，既快又没有精度问题。

第 8 题

某程序需要判断点 P(x, y) 是否在以原点为圆心、半径为 5 的圆内或圆上。下列判断条件正确的是（ ）。

• A. x * x + y * y <= 25
• B. abs(x) + abs(y) <= 5
• C. x * x - y * y <= 25
• D. x + y <= 5

答案：A

点 P(x, y) 到原点的距离为 √(x² + y²)，"在圆内或圆上"即 √(x² + y²) ≤ 5。直接开平方会引入浮点运算和精度误差，标准技巧是对不等式两边平方（两边均非负，平方保持不等号方向），化为 x² + y² ≤ 25，对应代码 x * x + y * y <= 25，全程整数运算、精确无误差，选 A。

其余选项对应的几何区域都不是圆：B 的 |x| + |y| ≤ 5 是曼哈顿距离约束，描述的是一个顶点在坐标轴上的正方形（菱形）区域；C 的 x² − y² ≤ 25 是双曲线划分出的区域，与圆毫无关系；D 的 x + y ≤ 5 是一条直线下方的半平面。这道题同时考察了距离公式和"用平方比较代替开方"这一避免浮点误差的重要工程习惯。

第 9 题

某无向带权图有边 (1,2,4)、(1,3,2)、(2,3,1)、(2,4,5)、(3,4,8)、(3,5,10)、(4,5,2)。该图最小生成树的总权值为（ ）。

• A. 7
• B. 8
• C. 9
• D. 10

答案：D

图有 5 个顶点，最小生成树需要恰好 4 条边。用 Kruskal 算法模拟：先把所有边按权值从小到大排序：(2,3,1)、(1,3,2)、(4,5,2)、(1,2,4)、(2,4,5)、(3,4,8)、(3,5,10)。然后依次尝试加入，跳过会成环的边：

1. (2,3) 权 1：2 和 3 不连通，加入。当前连通块 {2,3}，累计权值 1。
2. (1,3) 权 2：1 和 3 不连通，加入。连通块 {1,2,3}，累计 3。
3. (4,5) 权 2：4 和 5 不连通，加入。连通块 {1,2,3} 和 {4,5}，累计 5。
4. (1,2) 权 4：1 和 2 已在同一连通块，加入会成环，跳过。
5. (2,4) 权 5：2 所在的 {1,2,3} 与 4 所在的 {4,5} 不连通，加入。全图连通，累计 5 + 5 = 10。

已选 4 条边，算法结束，最小生成树总权值为 1 + 2 + 2 + 5 = 10，选 D。这道题的"陷阱"在于第 4 条边：权值为 4 的 (1,2) 看起来不大，但它两端已经连通必须跳过，真正把两个连通块接起来的是权值为 5 的 (2,4)——Kruskal 的贪心是"权值最小且不成环"，成环检测（实际实现中用并查集完成）一步都不能省。

第 10 题

有向非负权图边为 1→2(3)、2→4(4)、1→3(10)、3→4(1)、2→3(2)。使用 Dijkstra 算法从 1 号顶点出发到 4 号顶点的最短距离为（ ）。

• A. 6
• B. 7
• C. 8
• D. 11

答案：A

按 Dijkstra 算法的流程模拟。初始 dist[1] = 0，其余为无穷大。

1. 取出当前距离最小的未确定顶点 1（dist = 0），松弛它的出边：1→2(3) 使 dist[2] = 3；1→3(10) 使 dist[3] = 10。
2. 取出距离最小的顶点 2（dist = 3），松弛出边：2→4(4) 使 dist[4] = 3 + 4 = 7；2→3(2) 使 dist[3] 从 10 更新为 3 + 2 = 5。
3. 取出顶点 3（dist = 5），松弛出边：3→4(1) 使 dist[4] 从 7 更新为 5 + 1 = 6。
4. 取出顶点 4（dist = 6），它就是目标，最短距离确定为 6。

对应的最短路径是 1 → 2 → 3 → 4，长度 3 + 2 + 1 = 6，选 A。这道题设计了两处"诱导"：直达路径 1→3(10) 权值很大，需要被 1→2→3 = 5 替换掉；先被算出的 1→2→4 = 7 也不是最优，要被绕行 3 的路径 6 再次松弛更新。它检验的正是对 Dijkstra"逐步确定 + 反复松弛"机制的理解，而不是简单找一条看起来短的路。

第 11 题

下列代码片段的时间复杂度为（ ）。

longlong s = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j * j <= n; j++) {        s += i + j;    }}

• A. O(n)
• B. O(n log n)
• C. O(n√n)
• D. O(n²)

答案：C

外层循环 i 从 1 到 n，执行 n 次。关键在内层：循环条件是 j * j <= n，即 j ≤ √n，所以内层每次执行约 √n 次——注意内层的终止条件只和 n 有关、与 i 无关，因此每一轮外层循环中内层次数都是固定的 √n。由乘法法则，总执行次数 = n × √n，复杂度为 O(n√n)，选 C。

这道题的辨析点在于准确读出 j * j <= n 蕴含的循环次数：它既不是 O(n)（那要求条件是 j <= n），也不是 O(log n)（那要求 j 以倍增方式增长，如 j *= 2），而是平方根级别 O(√n)。j * j <= n 这种写法在枚举因数、判断质数等场景中非常常见，看到它应条件反射地想到 √n。

第 12 题

某优化问题的答案是 [1, M] 内的整数，存在单调判定函数 check(x)，且每次判定的时间复杂度为 O(n)。使用二分答案求最小可行值，整体时间复杂度通常为（ ）。

• A. O(nM)
• B. O(n log M)
• C. O(M log n)
• D. O(n + M)

答案：B

二分答案的框架是：在答案区间 [1, M] 上做二分，每次取中点 mid 并调用一次 check(mid)，根据判定结果舍弃一半区间。区间长度为 M，每次折半，最多折 log₂M 次就能收缩到唯一答案，因此 check 一共被调用 O(log M) 次；每次调用花费 O(n)。总复杂度 = 判定次数 × 单次代价 = O(n log M)，选 B。

对比错误项能加深理解：A 的 O(nM) 是不用二分、把 [1, M] 每个候选值逐一判定的暴力做法——二分正是把这里的 M 因子压缩成 log M，这也是二分答案的价值所在；C 把 n 和 M 在对数里的位置弄反了（二分的对象是答案区间 M，不是数据规模 n）；D 的加法关系不符合"循环嵌套调用"的乘法结构。

第 13 题

下列线性筛的代码片段中，当枚举到质数 p 且 i % p == 0 时，使用 break; 语句停止继续枚举。这样做的主要目的是（ ）。

for (int i = 2; i <= n; ++i) {if (!is_composite[i])        primes.push_back(i);for (int p : primes) {if (i * p > n)break;        is_composite[i * p] = true;if (i % p == 0)break;          // 这条语句的目的是？    }}

• A. 保证递归深度不超过 O(log n)。
• B. 保证每个合数只被它的最小质因子筛去一次。
• C. 保证每个素数都被标记为合数。
• D. 把筛法时间复杂度提高到 O(n log n)。

答案：B

线性筛（欧拉筛）能达到 O(n) 复杂度的根本原因，就是它保证每个合数恰好被标记一次，而实现这一保证的机关正是这条 break。分析其原理：内层按从小到大的顺序枚举已知质数 p，用 i × p 标记合数。当第一次遇到 p 整除 i（即 i % p == 0）时，p 就是 i 的最小质因子。此时如果不停下、继续用更大的质数 p' 去标记 i × p'，那么由于 p 整除 i，合数 i × p' 也能写成 p × (i/p × p')，它的最小质因子是 p 而不是 p'——这个数将来会在 i' = i/p × p' 这一轮被 p 再标记一次，造成重复标记。break 掉之后，每个合数都只会在"i = 该合数除以最小质因子、p = 最小质因子"这唯一一轮被标记，总标记次数恰好等于合数个数，整体 O(n)。选 B。

其余选项：A 与代码无关，这里根本没有递归；C 说反了，素数永远不该被标记为合数；D 方向反了，去掉 break 复杂度才会退化变差（趋向埃氏筛的 O(n log log n) 甚至更差），break 的作用是把复杂度"降"到 O(n)，而不是"提高到 O(n log n)"。

第 14 题

在 C++ 中，关于类的继承和构造、析构顺序，下列说法正确的是（ ）。

• A. 派生类可以直接访问基类的 private 成员。
• B. 基类的 protected 成员在私有继承后会变成派生类的 public 成员。
• C. 创建派生类对象时，会先调用基类构造函数，再调用派生类构造函数。
• D. 销毁派生类对象时，会先调用基类析构函数，再调用派生类析构函数。

答案：C

逐项分析：A 错误——private 成员是类封装的最内层，只有本类的成员函数（和友元）能访问，即使是亲儿子派生类也不能直接访问（派生类能直接访问的是基类的 public 和 protected 成员）。B 错误——私有继承（private 继承）会把基类的 public 和 protected 成员在派生类中统一降级为 private，访问权限在继承中只会收紧不会放宽，"变成 public"完全说反了。C 正确——构造派生类对象时，遵循"先基后派"的顺序：先执行基类构造函数把"基础部分"建好，再执行派生类构造函数完成派生部分的初始化，这保证派生类构造函数运行时可以安全使用已就绪的基类成员。D 错误——析构顺序与构造顺序严格相反："先派后基"，先执行派生类析构函数清理派生部分，再执行基类析构函数清理基础部分；如果先析构基类，派生类析构时可能引用到已被销毁的基类成员，逻辑上不成立。

"构造从基类到派生类、析构从派生类到基类"这个对称规则可以类比盖楼与拆楼：盖楼先打地基再建上层，拆楼先拆上层再拆地基。

第 15 题

将 4 个元素按 1, 2, 3, 4 的顺序入栈，在该过程中可随时插入出栈操作。下列序列中不可能作为出栈序列的是（ ）。

• A. 1, 2, 3, 4
• B. 2, 1, 4, 3
• C. 3, 2, 1, 4
• D. 3, 1, 2, 4

答案：D

逐个验证每个序列能否通过合法的入栈/出栈操作产生：

A（1,2,3,4）：入 1 出 1，入 2 出 2，入 3 出 3，入 4 出 4——每个元素入栈后立刻弹出，可行。

B（2,1,4,3）：入 1、入 2，出 2、出 1，入 3、入 4，出 4、出 3——可行。

C（3,2,1,4）：入 1、入 2、入 3，出 3、出 2、出 1，入 4，出 4——可行。

D（3,1,2,4）：要让 3 第一个出栈，必须先把 1、2、3 依次压入，弹出 3。此时栈中从底到顶是 1、2，栈顶是 2。序列要求下一个出栈的是 1，但 1 被压在 2 的下面，栈的后进先出性质决定了必须先弹 2 才能弹 1，顺序无法满足——不可行。

因此不可能的出栈序列是 D。判断这类题有一个通用法则：在出栈序列中，任取某个元素 x，所有比 x 先入栈（编号更小）且比 x 后出栈的元素，它们在出栈序列中必须呈现递减顺序（因为它们此刻都还压在栈里，后进的先出）。D 中 3 出栈之后，1 和 2 以"1, 2"的递增顺序出现，违反了这条法则，直接可判定非法。

二、判断题（每题 2 分，共 20 分）

参考答案：✓ ✓ ✗ ✗ ✓ ✗ ✓ ✓ ✗ ✓

第 1 题

若一项任务可从两种互斥的方案中选择一种完成，其中，方案 A 有 m 种做法，方案 B 有 n 种做法，则总做法数为 m + n。

✓ 这是计数原理中的加法原理（分类计数原理）的标准表述：完成一件事有若干类互斥的途径（选了这类就不走那类），各类内部分别有若干种做法，则总做法数是各类做法数之和。与之相对的是乘法原理（分步计数原理）：完成一件事需要依次经过若干个步骤，每步各有若干种做法，总数是各步做法数之积。区分两者的关键就在"分类（选其一）用加法、分步（都要做）用乘法"。表述正确。

第 2 题

将 n 个不同元素围成一圈，若只把旋转视为同一种排法、翻转仍视为不同排法，则方案数为 (n−1)!。

✓ 圆排列的经典结论。推导方式一（除法）：n 个元素的直线排列共 n! 种；围成圈后，每种圆排列沿圆旋转可以对应 n 种不同的直线排列（从 n 个不同位置"剪开"），它们在圆上视为同一种，所以圆排列数 = n!/n = (n−1)!。推导方式二（固定法）：既然旋转等价，不妨把某个指定元素固定在"12 点钟"位置作为基准消除旋转自由度，剩下 n−1 个元素在其余位置自由排列，共 (n−1)! 种。题干特别说明"翻转仍视为不同排法"，这正是标准圆排列的设定；如果翻转也算同一种（如项链问题），答案还要再除以 2 变成 (n−1)!/2。表述正确。

第 3 题

从 n 个不同元素中可重复地选取 k 个且不考虑顺序，方案数为 C(n+k, k)。

✗ 可重组合（多重集组合）的正确公式是 **C(n+k−1, k)**，题目写的 C(n+k, k) 多了 1，是错误的。正确公式的经典推导是"隔板法"：把选取方案记作 x₁ + x₂ + … + xₙ = k（xᵢ 表示第 i 种元素被选的次数，允许为 0），等价于把 k 个相同的球放进 n 个不同的盒子。将 k 个球和 n−1 块隔板排成一行，总共 n+k−1 个位置，从中选出 k 个位置放球（其余放隔板），方案数即 C(n+k−1, k)。可以用最小例子验证：n = 2、k = 1（两种元素中可重复选 1 个），显然只有 2 种；正确公式给出 C(2, 1) = 2 ✓，而题目公式给出 C(3, 1) = 3 ✗。表述错误。

第 4 题

杨辉三角中的组合数满足 C(n, k) = C(n−1, k) + C(n−2, k)。

✗ 正确的帕斯卡恒等式是 **C(n, k) = C(n−1, k−1) + C(n−1, k)**：两项都来自"上一行"（n−1），列下标一个是 k−1 一个是 k，对应杨辉三角中"每个数等于它左上方与正上方两数之和"。题目给出的式子两项分别取自 n−1 行和 n−2 行、列下标都是 k，形式上更像斐波那契式的递推，与组合数的性质不符。代入具体数字即可证伪：取 n = 4, k = 2，左边 C(4,2) = 6，右边 C(3,2) + C(2,2) = 3 + 1 = 4，6 ≠ 4。表述错误。

第 5 题

快速幂通过二进制拆分指数，可以在 O(log b) 时间内计算 a^b mod m。

✓ 快速幂的原理是把指数 b 写成二进制形式，例如 b = 13 = 1101₂ 意味着 a¹³ = a⁸ · a⁴ · a¹。算法维护一个不断平方的底数（a → a² → a⁴ → a⁸ → …，每步顺带取模防溢出），同时逐位扫描 b 的二进制：当前位为 1 就把当前底数乘进答案。b 的二进制位数约为 log₂b，每位只做常数次乘法和取模，所以总时间为 O(log b)——把朴素的 b−1 次连乘从线性压缩到对数级，是数论算法（模幂、逆元、矩阵幂等）的基础构件。表述正确。

第 6 题

只要图中不存在负权环，Dijkstra 算法就一定能正确处理带负权边的图。

✗ Dijkstra 的正确性依赖一个关键前提：所有边权非负。它的贪心逻辑是"每次取出当前距离最小的顶点并将其距离定案，此后不再修改"——这个"定案"之所以合法，是因为非负边权保证了绕更远的路不可能让距离变得更短。一旦存在负权边，即使没有负权环，也可能出现"先定案的顶点，后来经过一条负边反而能被更新得更短"的情况，而 Dijkstra 已经不再回头修改它，从而得出错误结果。构造一个最小反例：边 1→2 权 10，1→3 权 5，3→2 权 −8。Dijkstra 会在 dist[2] = 10 之前先定案 dist[3] = 5，随后松弛 3→2 得到 5 + (−8) = −3？不——问题出在顶点 2 若先于顶点 3 被某些实现定案，或更典型的例子中负边指向已定案顶点时更新被跳过，最短路 2 的真实距离 −3 与算法输出不符。处理含负权边（无负环）的图应改用 Bellman-Ford 或 SPFA。表述错误。

第 7 题

若一张连通无向图所有边权两两不同，则它的最小生成树一定唯一。

✓ 这是最小生成树的重要定理。可以用反证法结合交换论证理解：假设存在两棵不同的最小生成树 T₁ 和 T₂，取只属于其中一棵的边中权值最小的那条，设为 e ∈ T₁。把 e 加入 T₂ 会形成一个环，环上必然存在某条边 f 不属于 T₁（否则 T₁ 含环）。由于所有边权两两不同且 e 是"差异边"中最小的，可推出 w(e) < w(f)，于是用 e 替换 T₂ 中的 f 得到一棵总权更小的生成树，与 T₂ 是最小生成树矛盾。因此边权互不相同时 MST 唯一。反过来，当存在相等边权时 MST 可能不唯一（比如三角形三条边权全相等，任取两条都是 MST）。表述正确。

第 8 题

判断点 (x, y) 是否在以原点为圆心、半径为 r 的圆内或圆上时，可以比较 x² + y² 与 r²，不必先开平方。

✓ 原始条件是 √(x² + y²) ≤ r。由于不等式两边都非负，对两边平方不会改变不等号方向，条件等价于 x² + y² ≤ r²。用平方形式比较的好处非常实际：sqrt 返回浮点数，会引入舍入误差，在边界情形（点恰好落在圆上）可能因为误差判错；而当坐标和半径都是整数时，平方比较全程是精确的整数运算，既快又绝对可靠。这是计算几何编程中"能不开方就不开方"这一基本准则的典型应用。表述正确。

第 9 题

若能写出判定函数 check(x)，表示"答案为 x 时是否可行"，即使 check(x) 不满足单调性，也一定可以使用二分答案求最优解。

✗ 二分答案能够成立的前提条件恰恰是 check 的单调性：可行性关于 x 必须呈现"一刀切"的结构——存在某个分界点，使得分界点一侧全部可行、另一侧全部不可行（例如 x 越大越容易满足）。只有这样，"check(mid) 为真就舍弃一半、为假就舍弃另一半"的折半操作才是安全的：被舍弃的那一半确实不含更优答案。如果 check 不单调，可行与不可行在数轴上交错分布，检测一个 mid 点的结果无法推断任何一侧的整体情况，二分就会漏掉正确答案。所以"即使不满足单调性也一定可以二分"的说法从根本上违背了二分答案的适用条件。表述错误。

第 10 题

归并排序是一种稳定排序算法，常见实现的时间复杂度为 O(n log n)。

✓ 两个论断都成立。稳定性：归并排序的合并阶段用双指针比较左右两个有序子数组的当前元素，只要实现时约定"相等时优先取左半部分的元素"（即比较条件写 L[i] <= R[j]），原本位于左侧的相等元素就始终先进入结果，相对顺序得以保持，因此常见实现是稳定的。复杂度：递归树深度 log n，每层合并的总工作量 O(n)，最好、最坏、平均都是 O(n log n)（详见单选第 6 题的分析）。"稳定 + 复杂度有保证"正是归并排序区别于快速排序（平均 O(n log n) 但不稳定、最坏 O(n²)）的两大特征。表述正确。

三、编程题（每题 25 分，共 50 分）

3.1 编程题 1

试题名称：线网建设时间限制：1.0 s内存限制：512.0 MB

思路：

题目要求用总长度最小的线路把 n 座基站连成一个连通整体，且只有距离不超过 l 的基站对之间才允许修线路——这正是带约束的最小生成树问题：把每座基站看作图上的顶点，把每一对距离 ≤ l 的基站连一条边（边权为欧几里得距离），在这张图上求最小生成树；如果这张图本身不连通（可用的边不足以把所有点连起来），则输出 Impossible。

建图：双重循环枚举所有基站对 (i, j)，共 C(n, 2) 对。判断距离是否超限时使用平方比较技巧：dx*dx + dy*dy > l*l 则跳过，避免开方带来的浮点误差（坐标绝对值 ≤ 100，dx²+dy² 最大约 80000，int 完全够用且精确）。通过筛选的边记录端点和真实距离 sqrt(dx²+dy²)。n ≤ 500 时边数最多约 12.5 万条，数组开 N×N 规模足够。

求最小生成树：采用 Kruskal 算法。为了不搬动整条边的数据，代码用一个下标数组 p 做间接排序——p 中存边的编号，按 d[边号] 从小到大排序 p。然后按序枚举每条边，用并查集判断两端是否已连通：getf 函数实现了路径压缩的找根操作（这份代码用 f[u] = 0 表示 u 自己是根，写法略特殊但等价于常规并查集）；两端同根则加入会成环，跳过；不同根则采纳这条边，累加长度、合并两个集合，并用计数器 t 记录已采纳的边数。

连通性判定：一棵覆盖 n 个顶点的生成树恰好有 n−1 条边。Kruskal 结束后若 t == n−1，说明全图连通，输出累计长度（printf 的 %.2lf 保留两位小数）；否则说明剩余的可用边无论如何都接不通所有基站，输出 Impossible。

整体复杂度：建边 O(n²)，排序 O(n² log n)，并查集近似 O(n² α)，n = 500 时总量约百万级，远在时限之内。

以样例 2 验证 Impossible 分支：l = 1 时，四个点中 (1,0) 与 (1,1) 距离 1 可连、(0,0) 与 (1,0)、(0,0) 与 (1,1)？(0,0)-(1,0) 距离 1 可连，(0,0)-(1,1) 距离 √2 > 1 不可连，而 (−1,−1) 与其余任意点的距离都超过 1（到 (0,0) 为 √2），它成了孤立点，无法并入网络，故输出 Impossible，与样例一致。

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>usingnamespacestd;constint N = 510;constint E = N * N;int n, l;int x[N], y[N];int p[E], u[E], v[E], cnt;      // p 为边的下标数组，用于间接排序int f[N], t = 0;                // 并查集与已采纳边数double d[E], ans = 0;intgetf(int u){return f[u] ? f[u] = getf(f[u]) : u;   // f[u]==0 表示 u 是根；带路径压缩}boolcmp(int a, int b){return d[a] < d[b];         // 按边的真实长度升序}intmain(){cin >> n >> l;for (int i = 1; i <= n; i++)cin >> x[i] >> y[i];for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++) {int dx = x[i] - x[j], dy = y[i] - y[j];if (dx * dx + dy * dy > l * l)     // 平方比较，整数运算无精度问题continue;            cnt++;            p[cnt] = cnt;            u[cnt] = i;            v[cnt] = j;            d[cnt] = sqrt(dx * dx + dy * dy);  // 通过筛选后才计算真实距离        }    sort(p + 1, p + cnt + 1, cmp);for (int i = 1; i <= cnt; i++) {           // Kruskal 主循环int pu = u[p[i]], pv = v[p[i]];if (getf(pu) == getf(pv))              // 两端已连通，成环，跳过continue;        t++;        ans += d[p[i]];        f[getf(pu)] = pv;                      // 合并两个集合    }if (t == n - 1)                            // 恰好 n-1 条边 = 全图连通printf("%.2lf\n", ans);elseprintf("Impossible\n");return0;}

3.2 编程题 2

试题名称：堆石子时间限制：1.0 s内存限制：512.0 MB

思路：

先把问题翻译成纯粹的计数语言。约束条件是：a₁ = n（第一堆固定为 n 个）；a₁ > a₂ > a₃ > … > aₘ（严格递减）；每个 aᵢ ≥ 1。第一堆已经定死，真正需要确定的是 a₂ 到 aₘ 这 m−1 堆，它们必须满足：全部取自区间 [1, n−1]（因为 a₂ < a₁ = n 且每堆至少 1 个），且严格递减。

关键的组合观察：**"从一个集合中选出若干个互不相同的数并按严格递减排列"与"从该集合中选出一个子集"是一一对应的**——任取 m−1 个互不相同的数，把它们从大到小排好，就得到唯一一组合法的 (a₂, …, aₘ)；反之每组合法方案也唯一对应一个 m−1 元子集。因此方案数就是从 {1, 2, …, n−1} 这 n−1 个数中选 m−1 个的组合数：

答案 = C(n−1, m−1) mod (10⁹ + 7)

当 m−1 > n−1（即 m > n）时，可选的数不够，不存在合法方案，答案为 0（代码中 comb 函数的 if (m > n) return 0; 正是处理这一情形）。用样例验证：m = 3, n = 5，答案 C(4, 2) = 6，与样例输出的 6 种方案（(5,4,3)、(5,4,2)、(5,4,1)、(5,3,2)、(5,3,1)、(5,2,1)）完全吻合。

实现上的难点在于数据范围：n 可达 10⁸，m 可达 10⁵，既不能打出整张杨辉三角（O(n²) 空间时间都爆炸），也不能预处理 1~n 的阶乘（n 太大）。但注意到 C(n−1, m−1) 只需要 m−1 个乘积项，可以用定义式逐项计算：

C(N, K) = N × (N−1) × … × (N−K+1) / (1 × 2 × … × K)

在模 10⁹+7 意义下，除法要转化为乘以模逆元。由于 10⁹+7 是质数，根据费马小定理，i 的逆元等于 i^(MOD−2) mod MOD，用快速幂 qpow 计算。comb 函数的循环每轮先乘上分子的一项 (n−i)，再乘上分母项 (i+1) 的逆元，循环 K = m−1 次即完成。单次逆元 O(log MOD)，总复杂度 O(m log MOD)，m ≤ 10⁵ 时约几百万次运算，轻松通过。所有中间乘法先转 long long 再取模，防止 int 溢出。

qpow 采用递归写法：指数为奇数时拆出一个底数乘入，然后指数折半、底数平方，原理与单选第 5 题的迭代版快速幂完全相同。

#include<iostream>usingnamespacestd;constint MOD = (int)1e9 + 7;intqpow(int base, intexp){                  // 递归快速幂，O(log exp)if (!exp) return1;if (exp & 1) return (longlong)base * qpow((longlong)base * base % MOD, exp >> 1) % MOD;return qpow((longlong)base * base % MOD, exp >> 1);}intcomb(int n, int m){                       // 计算 C(n, m) mod MODif (m > n) return0;                       // 可选数不足，无合法方案int ans = 1;for (int i = 0; i < m; ++i) {        ans = (longlong)ans * (n - i) % MOD;              // 乘上分子项        ans = (longlong)ans * qpow(i + 1, MOD - 2) % MOD; // 乘上分母项的逆元（费马小定理）    }return ans;}intmain(){int m, n;cin >> m >> n;cout << comb(n - 1, m - 1) << endl;        // 答案即 C(n-1, m-1)return0;}

四、知识点分类汇总：这套八级卷子各考点考了几道？

一句话看懂这张表：

• 八级最鲜明的特征是数学化：组合计数一个板块就占了 8 道题，覆盖加法原理、捆绑/插空、二项式定理求特定项、圆排列、可重组合、帕斯卡恒等式等几乎全部初等计数工具，纯数学推导题的比重远超之前任何等级，这是八级区别于七级最典型的"能力台阶"；
• 图论从七级的"搜索遍历"升级为经典图算法本体：最小生成树的手工模拟与唯一性定理、Dijkstra 的执行过程与负权失效条件，都要求既会算又懂原理边界；
• 数论与计算几何作为提高组的标配板块正式登场：快速幂、模逆元、线性筛的 break 原理、叉积求面积、平方比较避免开方，都是后续更难题目的基础构件；
• 两道编程题分别对应两大板块的落地：第一题是"建图 + Kruskal + 并查集 + 连通性判定"的完整图论工程，第二题则要求先完成"严格递减序列 ⇔ 组合选取"的数学建模，再解决"n 高达 10⁸ 时如何计算组合数取模"的实现难题（逐项乘 + 费马逆元），建模与实现缺一不可；
• 判断题大量考察"公式细节的对错"（可重组合是 n+k−1 还是 n+k、帕斯卡恒等式的下标、二分答案是否需要单调性、Dijkstra 能否处理负权），死记结论而不理解推导的考生极易在这些"一字之差"上失分。

也就是说，八级想稳过，重心要放在初等组合计数的系统掌握（原理、模型与公式推导，而非背结论）、经典图算法的原理与边界条件（MST、Dijkstra 什么时候对、什么时候失效）、模运算工具链（快速幂、费马逆元、大参数组合数的计算）这三块，同时保持对复杂度分析和数据结构性质题的熟练度——八级已经与 CSP 提高组的知识体系深度接轨，数学功底开始成为决定性因素。