点击 GESP 真题解析合集 可以查看历届 GESP 真题解析。
1. 单选题（每题 2 分，共 30 分）
【答案】: C。
【解析】: 求 的组合，罗列一下有 种。
【答案】: A。
【解析】: 总共有 种不同的照片方案，现在要从这 种中选出来 张，方案数为 。
【答案】: C。
【解析】: 一个包含纯虚函数的类（抽象类）完全可以包含成员变量。纯虚函数仅要求派生类必须实现该函数，但并不限制抽象类本身定义成员变量。
【答案】: B。
【解析】: 存在生成树的有向图不一定是强连通的，它可能是弱连通的。
【答案】: C。
【解析】: 总共有 种可能，其中全是男生或者全是女生不合法，那么合法的概率就是 。
【答案】: D。
【解析】: 根据二项式定理， 的系数为 。
【答案】: B。
【解析】: 每个点每条边访问一次，时间复杂度为 。
【答案】: A。
【解析】: 只有满足“最优子结构”和“无后效性”的多阶段决策问题才能用 DP。
【答案】: B。
【解析】: 直接枚举 ，发现 有 种方案，累加起来。
【答案】: C。
【解析】: 线性筛，时间复杂度为 。
【答案】: A。
【解析】: 朴素的 Dijkstra 算法，双重循环枚举，时间复杂度为 。
【答案】: D。
【解析】: 两层循环都是 级别的，gcd 是 的，总时间复杂度为 。
【答案】: A。
【解析】: 观察第 4 行，当 right - left <= 1 时，区间内只有一个元素时返回，所以此时归并的是一个左闭右开的区间 。
那么计算出 mid 后，会把区间分成 以及 这两个区间，所以选 A。
【答案】: D。
【解析】: 14 行是要更新其它点到达生成树距离的最小值，也就是说当 存在边，并且边权小于 key[v] 就需要更新。
【答案】: D。
【解析】: 根据题目要求画出图，最短路为 ，边权和为 。
2. 判断题（每题 2 分，共 20 分）
2.1 判断题题面
2.2 判断题解析
第 1 题：。字符 9 和数字 3 进行异或，结果是 int 类型。
第 2 题：。输出 arr[5] 会产生数组越界问题。
第 3 题：。每个算法都会有最差的时间复杂度，如果采用随机化排序，时间复杂度可能大于 。
第 4 题：。不尽相异的全排列问题，排列方案有 。
第 5 题：。x * x 可能会溢出，溢出的时候 sqrt(x * x) 的结果就不对了。
第 6 题：。C语言不支持重载。
第 7 题：。容易构造这样的简单无向图。
第 8 题：。弧长为 theta * r，两条半径为 2r。
第 9 题：。如果用堆优化+邻接表实现，时间复杂度为 ，其中 是顶点数， 是边数。
第 10 题：。题目并没有说明男生和女生的数目，无法计算。
3. 编程题（每题 25 分，共 50 分）
3.1 编程题 1（最短距离）
分析
分类讨论：
时，如果走直线边，那么边权为 ；要么走其它若干边权为 的边，因为要走最短路，显然走两条边权为 的边最优，又因为 ，所以可以走 ，边权和为 。这种情况下，答案取 。 ，同理，如果走直线，边权为 ；也可以走 ，边权为 。最终答案为 。
特别地，当 时，答案为 ，当 或 时，答案为 。
代码
#include<bits/stdc++.h>usingnamespacestd;intmain(){int n, p, q, u, v;cin>>n>>p>>q;while(n--) {cin>>u>>v;if(u == v) cout<<"0\n";elseif(u == 1 || v == 1) cout<<p<<'\n';elseif(__gcd(u, v) == 1) cout<<min(p, 2 * q)<<'\n';elseif(__gcd(u, v) != 1) cout<<min(q, 2 * p)<<'\n'; }return0;}3.2 编程题 2（最小生成树）
分析
我们先用 Kruskal 算法求出原图的最小生成树（MST），设其权值为 base。
对于非树边（非 MST 中的边）：删除它后，原来的 MST 仍然存在，所以新的 MST 的权值和依然是 base。
对于树边（MST 中的边）：删除它后，原来的 MST 会分成两个连通块，想要重新连通，必须找一条连接这两个连通块的非树边，且权值尽可能小。新的 MST 的权值和 base - w(树边) + min(非树边)。
如果找不到这样的非树边，则图不连通，输出 -1。
因此，问题转化为：对于每一条树边，找到所有覆盖它的非树边中的最小权值。
如果我们枚举每一条非树边 ，暴力遍历 路径上的所有树边，更新最小值，时间复杂度为 。这个重要问题在于同一条树边会被多条非树边重复访问。
我们可以用树链剖分来优化，因为这是 GESP 八级，所以考虑用更简单的并查集来优化。
将每一条非树边按照权值从小到大排序，依次处理每条非树边，用它去“覆盖” 路径上的树边。因为，某条树边第一次被覆盖时，得到的权值一定是最小的，后续再遇到更大的非树边，直接跳过即可。
如何实现“跳过已覆盖的边”？
我们可以用并查集来维护， fa2[x]表示：从节点x沿着树边向上走，第一个还未处理完的祖先节点。用并查集跳过已经处理过的边，让两个节点不断往上跳，直到在 LCA 处相遇 时间复杂度为 。
实现的时候，我将边用深度较深的点代替，具体实现可以参考如下代码。
代码
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint maxn = 1e5 + 5;int ew[maxn], n, m;int par[maxn], dep[maxn], re[maxn];int fa1[maxn], fa2[maxn];ll ans[maxn];bool in[maxn];structnode {int u, v, w, id;};vector<node> g, no_mst;vector<pair<int, int>> mst[maxn]; // 树边 {邻居, 边编号}boolcmp(node x, node y){return x.w < y.w;}intfind1(int x){return fa1[x] == x ? x : fa1[x] = find1(fa1[x]);}intfind2(int x){return fa2[x] == x ? x : fa2[x] = find2(fa2[x]);}voiddfs(int u, int fa){ par[u] = fa; dep[u] = dep[fa] + 1;for(auto x: mst[u]) {int v = x.first, id = x.second;if(v == fa) continue; re[v] = id; // v 对应 id 这条边 dfs(v, u); }}intmain(){cin>>n>>m;for(int i = 1; i <= m; ++i) {int u, v, w;cin>>u>>v>>w; ew[i] = w; g.push_back({u, v, w, i}); }for(int i = 1; i <= n; ++i) fa1[i] = i; sort(g.begin(), g.end(), cmp); ll base = 0;for(auto e: g) {if(e.u == e.v) continue; // 自环int fu = find1(e.u), fv = find1(e.v);if(fu != fv) { fa1[fu] = fv; in[e.id] = true; base += e.w; mst[e.u].push_back({e.v, e.id}); mst[e.v].push_back({e.u, e.id}); } } dfs(1, 0);for(auto e: g) { // 非树边if(!in[e.id] && e.u != e.v) no_mst.push_back(e); } sort(no_mst.begin(), no_mst.end(), cmp);for(int i = 1; i <= m; ++i) ans[i] = -1;for(int i = 0; i <= n; ++i) fa2[i] = i;for(auto e: no_mst) { // 枚举非树边int u = find2(e.u), v = find2(e.v), w = e.w;while(u != v) {if(dep[u] < dep[v]) swap(u, v);int eid = re[u];if(ans[eid] == -1) ans[eid] = w; // 贪心首次赋值 fa2[u] = find2(par[u]); // 并查集合并 u = fa2[u]; // 往上跳 } }for(int i = 1; i <= m; ++i) {if(in[i]) {if(ans[i] == -1) cout<<-1<<'\n';elsecout<<base - ew[i] + ans[i]<<'\n'; } else {cout<<base<<'\n'; } }return0;}-完结-
信奥课程咨询或合作，请加微信dimension-s或扫描下方二维码
如果你喜欢这类赛事真题解析文章，欢迎点赞、转发、收藏，让更多人看到这份真诚的分享！
欢迎点击下方名片关注
