题解|GESP2026年6月C++八级真题解析

四季读书网 2026-07-01 17:53:47 3 0

1. 单选题（每题 2 分，共 30 分）

【答案】: B。

【解析】: 总方案减去某一类书一本都不选的方案，。

【答案】: B。

【解析】: 不相邻可以用插空法，先排好没有限制的 4 个人，为，然后甲、乙两人插空，方案数为，总方案数为。

【答案】: C。

【解析】: 可以用二项式定理展开，，其中常数项取。代入，可得常数为

【答案】: A。

【解析】: 考察组合数的递推公式，。

【答案】: C。

【解析】:qpow 实现的是快速幂，答案为，计算方法有很多，可以拆成。

【答案】: D。

【解析】: 归并排序时间复杂度为。

【答案】: A。

【解析】: 可以算出每一条边，然后用海伦公式计算，也可以在平面直角坐标系中画出三角形，然后用大的矩形减去三个直角三角形。

【答案】: A。

【解析】: 圆的方程基础题。

【答案】: D。

【解析】: 可以用 Kruskal 算法，选出四条边，为，边权和为。

【答案】: A。

【解析】: 最短路为，权值和为。

【答案】: C。

【解析】: 外层循环，内层循环，总时间复杂度为。

【答案】: B。

【解析】: 二分答案为，每次 check 是的，总时间复杂度为。

【答案】: B。

【解析】: 欧拉筛的本质。

【答案】: C。

【解析】:

A 选项错误，派生类不能访问基类的 private 成员。
B 选项错误，protected 成员在私有继承后会变成派生类的 private 成员。
C 选项正确。
D 选项错误，销毁派生类对象，会先调用派生类析构函数，再调用基类的析构函数。

【答案】: D。

【解析】: D 选项中 3 出栈后不可能出栈 1。

2. 判断题（每题 2 分，共 20 分）

2.1 判断题题面

2.2 判断题解析

第 1 题：。分类加法原理。

第 2 题：。总共有种方案重复，方案数为。

第 3 题：。可重组合问题，方案数为。

第 4 题：。代入组合数公式，显然不满足。

第 5 题：。快速幂本质。

第 6 题：。Dijkstra 算法无法处理负权边。

第 7 题：。边权两两不同，最小生成树唯一。

第 8 题：。圆方程的知识。

第 9 题：。二分答案需要答案满足单调性或者可以通过划分区间的方式求解答案。

第 10 题：。归并排序的基本知识。

3. 编程题（每题 25 分，共 50 分）

3.1 编程题 1（线网建设）

分析

因为只有，那么将所有距离的边全部连边，问题就变成了最小生成树，跑一个 Kruskal 算法即可。

代码

#include<bits/stdc++.h>usingnamespacestd;constint maxn = 505;int x[maxn], y[maxn], fa[maxn], n, l, tot, cnt;double ans;structnode {int u, v;double w;} e[maxn * maxn];boolcmp(node x, node y){return x.w < y.w;}intfind(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}intmain(){cin>>n>>l;for(int i = 1; i <= n; ++i) {cin>>x[i]>>y[i];        fa[i] = 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;            e[++tot].u = i, e[tot].v = j, e[tot].w = sqrt(dx * dx + dy * dy);        }    }    sort(e + 1, e + tot + 1, cmp);for(int i = 1; i <= tot; ++i) {int fu = find(e[i].u), fv = find(e[i].v);if(fu != fv) {            fa[fu] = fv;            ++cnt;            ans += e[i].w;if(cnt == n - 1) break;        }    }if(cnt == n - 1) cout<<fixed<<setprecision(2)<<ans;elsecout<<"Impossible";return0;}

3.2 编程题 2（堆石子）

分析

要求，且，，这等价于从中选出个互不相同的数，然后从大到小依次赋值给，方案数就是。

因为最大有，我们如果直接递推到阶乘以及阶乘的逆元，有 MLE 和 TLE 的风险。

但是只有，所以我们只需要递推到的逆元，分子可以直接循环求解。

代码

#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint maxn = 1e5 + 5, mod = 1e9 + 7;ll f[maxn], inv[maxn], n, m;ll quick_pow(ll a, int b){    ll ans = 1;while (b) {if(b & 1) ans = ans * a % mod;        a = a * a % mod;        b >>= 1;    }return ans;}voidinit(){ // 预处理    f[0] = 1;for(int i = 1; i <= m; ++i) f[i] = f[i - 1] * i % mod; // 阶乘    inv[m] = quick_pow(f[m], mod - 2);for(int i = m - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod; // 阶乘逆元}ll C(int n, int m){if(m > n) return0;    ll ans = 1;for(int i = n; i >= n - m + 1; --i) ans = ans * i % mod;return ans * inv[m] % mod;}intmain(){cin>>m>>n;    init();cout<<C(n - 1, m - 1)<<'\n';return0;}