ARTICLE · 1021315
题解|GESP2026年9月C++八级真题解析
点击 GESP 真题解析合集 可以查看历届 GESP 真题解析。
1. 单选题（每题 2 分，共 30 分）
【答案】: B。
【解析】: 数字模 可以分为三组 。三位数能被 整除，需要三位数字之和能被 整除。由于每组只有两个数字，只能从上述三组中各选一个数字。
选到数字 ：共有 组，每组有 种合法排列，共 个。 选到数字 ：共有 组，每组有 种合法排列，共 个。
因此共有 个。
【答案】: C。
【解析】: 把甲乙看成一个整体，共 个人围成一个圈的圆排列为 ，甲乙内部有 种方案，共有 种方案。
【答案】: B。
【解析】: 典型的区间 DP 问题，何必顺序为 合并， 合并， 合并。
【答案】: A。
【解析】: 先序序列的第一个元素就是根，然后中序中找到根，根的左边是左子树，右边是右子树，递归操作。
【答案】: B。
【解析】:
A 选项错误，普通快速幂无法处理任意负指数。 B 选项正确。 C 选项错误，模数可以是合数。 D 选项错误，迭代实现通常需要 的空间。
【答案】: B。
【解析】: 杨辉三角数就是组合数，答案为 。
【答案】: C。
【解析】: 简单数学题。容易得到长和宽分别为 和 ，面积为 。
【答案】: D。
【解析】: 简单数学题。容易得到 ，答案为 。
【答案】: A。
【解析】:
A 选项正确，Prim 算法时间复杂度与顶点相关，Kruskal 需要对边排序。 B 选项错误，最小生成树不一定相同。 C 选项错误，Kruskal 可以用邻接表存图。 D 选项错误，Prim 也可以处理无向图。
【答案】: B。
【解析】: 按照边权从小到大加入不成环的边。
【答案】: A。
【解析】: 距离小的需要先出队，堆中保存顶点编号与距离。
【答案】: A。
【解析】: 关于 Floyd 算法的理解。
【答案】: C。
【解析】: 简单比大小。
【答案】: D。
【解析】: 次差分，每次操作 ，求前缀和是 ，总时间复杂度为 。
【答案】: D。
【解析】: 关于C++继承中构造函数和析构函数的理解。子类实体化会先调用父类的构造函数再调用子类的构造函数，释放内存时会先调用子类的析构函数再调用父类的析构函数。
2. 判断题（每题 2 分，共 20 分）
2.1 判断题题面
2.2 判断题解析
第 1 题：。排列问题。
第 2 题：。根据二项式定理，取 和 容易证明。
第 3 题：。最小生成树可能唯一，例如本来就是一棵树，边权都相同。
第 4 题：。朴素的 Dijkstra 是 的。
第 5 题：。排堆其实就是一种选择排序，不稳定。
第 6 题：。唯一分解定理。
第 7 题：。循环队列的基础知识。
第 8 题：。私有继承，基类的 public 成员在派生类变为 private 的。
第 9 题：。滚动数组的特点。
第 10 题：。可以用海伦公式计算。
3. 编程题（每题 25 分，共 50 分）
3.1 编程题 1（生成树计数）
分析
这类图通常称为仙人掌图：每条边至多属于一个简单环。
答案为 ，其中 (|C|) 表示环的边数。
对于不属于任何环的边，它是桥。删除桥会使图不连通，所以所有生成树都必须选择这些边。
对于一个长度为 的简单环，如果保留全部 条边，生成树中会出现环；必须从中删除一条边；删除任意一条边后，环变成一条链，仍然连通；因此这个环有 种选择。
由于每条边至多属于一个简单环，不同环之间的选择相互独立，所以把所有环长相乘即可。
可以用 DFS 找环，时间复杂度为 。
代码
#include<bits/stdc++.h>
usingnamespacestd;
using ll = longlong;
constint maxn = 1e5 + 5, mod = 998244353;
int dep[maxn], n, m;
ll ans = 1;
bool vis[maxn];
structnode {
int v, id;
};
vector<node> g[maxn];
voiddfs(int u, int par){
vis[u] = true;
for(auto [v, id]: g[u]) {
if(id == par) continue;
if(!vis[v]) {
dep[v] = dep[u] + 1;
dfs(v, id);
} elseif(dep[v] < dep[u]) { // 反祖边
int len = dep[u] - dep[v] + 1;
ans = ans * len % mod;
}
}
}
intmain(){
cin>>n>>m;
for(int i = 1; i <= m; ++i) {
int u, v;
cin>>u>>v;
g[u].push_back({v, i}), g[v].push_back({u, i});
}
dfs(1, 0);
cout<<ans;
return0;
}
3.2 编程题 2（末班车）
分析
到达车站后没有必要等待。若到达时间为 ，一条线路的末班车时间为 ，只要 ，就可以在第 分钟立即乘车。
另外，如果第 分钟从某站出发能够到达终点，那么更早出发也一定可以，因为可以先等待到第 分钟。
所以，对于任意起点和终点，只需要求出一个值最晚什么时候出发还能到达终点。
部分分
对于 的数据。对于每一组询问 ，设 表示第 分钟从 出发到达 的最早时间。
初始时 ，对于线路 ，如果到达 时还没有错过末班车，即 就可以立即乘车，并进行转移 。
直接使用 Dijkstra 算法。每组询问的时间复杂度为 。
满分
此时不能每组询问单独运行 Dijkstra，但是车站数量只有 ，可以分别固定每个终点进行预处理。
设对于终点 ，定义 表示为了到达 ，最晚可以在什么时刻从 出发。
对于一条路线 ，如果要通过这条线路从 前往终点 ，出发时间 需要满足：
没有错过该线路的末班车， 到达 时，还来得及继续前往 ，
因此，通过这条线路时，从 出发的最晚时间为 。
我们需要枚举 的所有出边，取最大值，。
初始边界 ，表示已经位于终点时，不受出发时间限制。
转移需要用所有的 去更新 ，方向与原图相反。因此，我们对每条原图线路 ，可以在反图中保存一条从 指向 的边。固定终点 后：
固定终点 后：
令 ； 将 放入大根堆； 每次取出当前 最大的车站 ； 枚举原图中所有指向 的线路 （也就是反图中所有 的邻接点）； 用 更新 。
使用大根堆是因为我们要最大化最晚出发时间。
又因为 ，所以一次转移得到的时间满足 。
沿着一条路线从起点走向终点时，允许的最晚时间会严格增大。因此从终点反向计算时，应该优先确定较大的值，大根堆正好满足这个顺序。这种做法可以看成反向求最晚出发时间的 Dijkstra。
综上， 对于每次询问 ，若 则第 分钟从 出发能够到达 ，输出 Yes；否则输出 No。
每个终点运行一次大根堆 Dijkstra，共有 个终点 。每组询问的复杂度为 ，所以总时间复杂度为 。
代码
#include<bits/stdc++.h>
usingnamespacestd;
using ll = longlong;
constint maxn = 505, inf = 1e9;
int dis[maxn], ans[maxn][maxn], n, m, q;
bool vis[maxn];
structedg {
int v, l, t;
};
vector<edg> g[maxn];
structnode {
int id, dis;
booloperator < (const node & rhs) const { // dis 大的先出队
return dis < rhs.dis;
}
};
// 固定终点 target
// dis[u] 表示为了到达 target，最晚可以几点从 u 出发
voiddijkstra(int target){
memset(dis, -1, sizeof(dis));
memset(vis, false, sizeof(vis));
dis[target] = inf;
priority_queue<node> pq;
pq.push({target, dis[target]});
while(!pq.empty()) {
auto [u, d] = pq.top(); pq.pop();
if(vis[u]) continue;
vis[u] = true;
for(auto [v, l, t]: g[u]) {
int ndis = min(l, dis[u] - t); // 原图有 v -> u 的线路
if(!vis[v] && ndis > dis[v]) {
dis[v] = ndis;
pq.push({v, dis[v]});
}
}
}
}
intmain(){
cin>>n>>m>>q;
while(m--) {
int u, v, l, t;
cin>>u>>v>>l>>t;
g[v].push_back({u, l, t}); // 建立反图
}
for(int v = 1; v <= n; ++v) { // 固定每个终点的最晚出发时间
dijkstra(v);
for(int u = 1; u <= n; ++u) ans[v][u] = dis[u];
}
while(q--) {
int x, y, s;
cin>>x>>y>>s;
if(s <= ans[y][x]) cout<<"Yes\n";
elsecout<<"No\n";
}
return0;
}
如果你喜欢这类赛事真题解析文章，欢迎点赞、转发、收藏，让更多人看到这份真诚的分享！