点击 GESP 真题解析合集 可以查看历届 GESP 真题解析。
1. 单选题（每题 2 分，共 30 分）
【答案】: D。
【解析】:
当 时，达到基准 的情况，将其带入，得到 ，所以选 D。
【答案】: D。
【解析】:
A 选项正确，预处理出每个数的最小质因数后，每次除以最小质因数就可以在 时间复杂度下完成质因数分解。 B 选项正确，线性筛基础知识。 C 选项正确，唯一分解定理的基础知识。。 D 选项错误，埃氏筛的时间复杂度源于调和级数。
【答案】: B。
【解析】: LCS 长度为 意味着两个字符串至少有 个公共字符（不一定连续）。
【答案】: B。
【解析】: 树有 个点 条边，每条边提供 度，度数之和为 。
【答案】: D。
【解析】: 查找哈希表在理想情况下平均是 ，但最坏可能达到 ，例如所有元素哈希到一个位置产生冲突。
【答案】: B。
【解析】: 贪心选择较小的边加入。
【答案】: B。
【解析】: 代码功能为：给定数组 ，排序后为 ，选出 个数，使得相邻数的距离（差）的最小值最大。
选出 时相邻距离的最小值为 ，这是最大可能的最小距离。
模拟代码执行过程也可以。
【答案】: A。
【解析】: 排序是 ，二分值域为 ，check 需要 ，二分答案的复杂度为 。总时间复杂度为 。
【答案】: A。
【解析】: 二叉树遍历基础题，根据先序和中序可以直接画出二叉树求出后序。
【答案】: B。
【解析】:
A 选项错误，访问 4 之后应该继续遍历 7。 B 选项正确。 C 选项错误，访问 8 后需要把 8 的三个后继 4、7、9 都访问完 D 选项错误，访问 5 后应该访问 4。
【答案】: B。
【解析】: 有 个强连通分量，, , , 。
【答案】: C。
【解析】: 泛洪本质就是对图进行了一次遍历。泛洪可用于统计连通块的个数、面积、周长等，不限于二维网格，也不一定需要递归实现。
【答案】: D。
【解析】: 画出二叉哈夫曼树即可求解。
【答案】: D。
【解析】:
A 选项错误，删除需要知道该节点的前驱结点，这个需要 的遍历。 B 选项错误，循环链表如果不带头结点，那么当链表为空时，就有空指针。 C 选项错误，尾结点的 next指针应该指向头结点。D 选项正确，循环单链表判空方式就是判断头结点的 next指针是否指向自身。
【答案】: C。
【解析】:
A 选项错误，树的 DFS 序列有很多种可能性。 B 选项错误，已知先序和后序不能唯一确定二叉树，例如先序为 ，后序为 的二叉树，就有两种情况。 C 选项正确，根据先序和中序可以唯一确定二叉树。 D 选项错误，中序遍历序列递增无法保证该二叉树平衡，例如这棵二叉树是一条链时就不是平衡二叉树了。
2. 判断题（每题 2 分，共 20 分）
2.1 判断题题面
2.2 判断题解析
第 1 题：。异或运算基础知识。
第 2 题：。C++中的引用一旦绑定，不能重新绑定到其他对象。
第 3 题：。引用的基础知识。
第 4 题：。动态规划可以解决，不代表贪心一定正确，需要满足贪心的性质才可求解。
第 5 题：。每次将数组一分为二分治，时间复杂度是稳定的 。
第 6 题：。最短路径树上的边不一定属于最小生成树，两者目标不同。
第 7 题：。边权都不相同，那么最小生成树唯一。
第 8 题：。哈夫曼树不一定是完全二叉树，例如 个频率都为 的字符，画出二叉哈夫曼树时就不是完全二叉树。
第 9 题：。sin(90) 中的 是弧度制，结果不为 。
第 10 题：。因为图连通，所以从任意定点开始的 DFS 都会遍历到所有点。
3. 编程题（每题 25 分，共 50 分）
3.1 编程题 1（拆分）
分析
经典面试题。下面先给出结论，再证明。发现结论的过程可以用打表等方法。
要使得拆分后乘积最大，策略如下：
尽可能多地拆分出 3 剩余部分处理： 如果 能被 整除（），则全部拆分为 ，即答案为 如果 除以 余数为 ，则拆分出一个 （即两个 ），其余为 ，即答案为 如果 除以 余数为 ，则拆分出一个 ，其余为 ，即答案为 特殊情况： 时，答案就是
证明分以下几个步骤完成：
拆分因子中不包含
假设拆分方案包含 ，那么把 合并到任意一个拆分项，得到的新的乘积都会变大，因此最优拆分中所有因子 拆分因子中不包含大于 的数
假设最优拆分方案中存在一个数 ，我们可以将 拆分为 和 。比较拆分前后的乘积贡献， 和 ，因为 ，那么就有 （即 ）。 这说明任意大于等于 的数都可以继续拆分以获得更大的乘积，对于 拆分为 ，与原数一样。为了统一策略，认为 等价于 两个 。 综上，最优拆分中的因子只可能包含 或 。 最优选择 而不是
我们已知最优拆分因子只包含 或 ，现在仅需确定 和 的比例。 对于 来说，有两种拆分方式 和 ，显然 的拆分方案更优，那么在总和固定的情况下，用两个 代替 个 会使得乘积更大。因此，最优拆分中，因子 的个数只可能是 个、 个 或 个，其余全部是 。 根据模 余数分类讨论
综上，我们就可以根据模 的余数来决定 的个数。 若 ：全部拆分为 。 若 ：拆分为若干个 和 两个 （因为 ）。 若 ：拆分为若干个 和 一个 。
代码
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint maxn = 1e6 + 5, mod = 1e9;ll pow3[maxn];intmain(){ pow3[0] = 1;for(int i = 1; i <= 1e6; ++i) pow3[i] = pow3[i - 1] * 3 % mod;int t, n;cin>>t;while(t--) {cin>>n;if(n == 1) {cout<<1<<'\n';continue; }int tmp = n % 3; ll ans;if(tmp == 0) ans = pow3[n / 3];elseif(tmp == 1) ans = 4 * pow3[(n - 4) / 3] % mod;else ans = 2 * pow3[(n - 2) / 3] % mod;cout<<ans<<'\n'; }return0;}3.2 编程题 2（物流网络）
分析
本题暂无发现 的做法，官方提供的两种解法时间复杂度都有问题，精心构造的数据会被卡成 TLE。
我们可以直接暴力枚举哪一条边免费了，则景观评分超过这条边的边都不能走，然后跑一个堆优化的 dijkstra 算法求解最短路，时间复杂度为 。
题外话：这个题放在七级里很抽象，数据范围里没有体现有部分分，并且也没有说数据是随机生成的，会导致很多同学不敢写暴力。并且正解是需要用 dijkstra 算法的，这个并不在七级考纲中，涉及超纲问题。
给参加考级学生的建议：因为 GESP 是 IOI 赛制，所以鼓励大胆尝试，想不到正解的时候，先写一个暴力看看情况，很多时候 GESP 的数据很水，说不定就拿到很高的分数甚至满分。
代码
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;const ll inf = 0x3f3f3f3f3f3f3f3f;constint maxn = 5005;int w[maxn], b[maxn], n, m;ll dis[maxn];bool vis[maxn];structedg {int v, id;};vector<edg> g[maxn];structnode {int x; ll dis;friendbooloperator < (node x, node y) {return x.dis > y.dis; }};intmain(){cin>>n>>m;for(int i = 1; i <= m; ++i) {int u, v;cin>>u>>v>>w[i]>>b[i]; g[u].push_back({v, i}); g[v].push_back({u, i}); } ll ans = inf;for(int i = 1; i <= m; ++i) {memset(vis, false, sizeof(vis));memset(dis, 0x3f, sizeof(dis)); priority_queue<node> pq; pq.push({1, 0}); dis[1] = 0; ll tmpw = w[i]; w[i] = 0; // i 号边免费while(!pq.empty()) { node tmp = pq.top(); pq.pop();int u = tmp.x;if(vis[u]) continue; vis[u] = true;for(auto x: g[u]) {int v = x.v, id = x.id;if(b[i] >= b[id]) { // i 号边的景观评分最高if(dis[u] + w[id] < dis[v]) { dis[v] = dis[u] + w[id]; pq.push({v, dis[v]}); } } } } ans = min(ans, dis[n]); w[i] = tmpw; }cout<<(ans == inf ? -1 : ans);return0;}如果你喜欢这类赛事真题解析文章，欢迎点赞、转发、收藏，让更多人看到这份真诚的分享！
欢迎点击下方名片关注
