1. 单选题（每题 2 分，共 30 分）
【答案】: D。
【解析】: 至少 1 名男生和 1 名女生有两种情况，1 男 2 女以及 2 男 1 女。其中 1 男 2 女的方案数为 ，表示 8 名男生中选出 1 名，6 名女生中选出 2 名，同理，2 男 1 女的方案数为 。总方案数为 。
【答案】: B。
【解析】: 第 10 行的所有数之和就是 ，根据二项式定理或者从子集个数角度理解，这个求和公式就是 。
【答案】: B。
【解析】: 每次 e 都除以 ，时间复杂度为 。
【答案】: C。
【解析】: 问至少，考虑正难则反。总方案有 ，不包含数学书的方案为 ，那么至少包含 本数学书的方案就有 。
【答案】: B。
【解析】: 这棵树的左子树包含 ，右子树包含 ，形态可能有多种。
A 选项错误，这棵树不一定是完全二叉树，例如， 的左子树中 是 的左儿子。 B 选项正确，如果 是兄弟节点，那么他们的父亲一定是介于 之间的数，这样的数不存在。 C 选项错误， 的最大深度为 ，例如， 的左子树中 是 的左儿子。 D 选项错误， 可以是 的右儿子， 是 的左儿子。
【答案】: C。
【解析】: 基础题。
【答案】: B。
【解析】: 最短路最多经过 条边，路径中不会有环，因为有环那么环上的路径和一定 ，不会使得最短路变小。
【答案】: B。
【解析】: 用 Dijkstra 算法求出任意两点间的最短路后，再用 Floyd 算法求解，任意两点间的最短路不会发生改变，已经满足最短路性质（三角不等式）。
【答案】: B。
【解析】: 考察最短路算法的理解。
A 选项错误，Dijkstra 算法不能处理负权边的情况。 B 选项正确。 C 选项错误，单源最短路算法可以求解无向图。 D 选项错误，Dijkstra 算法每一步会选择一个未访问的距离最小的点。
【答案】: C。
【解析】: 甲、乙两人要相邻，那么就用捆绑法。将甲、乙看成一个整体，内部可以交换顺序，有 种情况，然后看成 个人的排队，共有 种方案。我们需要排除掉甲、乙两人相邻且丙在排头的方案，丙在排头，那么先排丙，有 种方案，剩下可以看成 个人的全排列，且甲、乙内部可以交换顺序（因为甲、乙看成一个整体），那么甲、乙两人相邻且丙在排头的方案共有 种方案。总共合法方案为 种方案。
【答案】: C。
【解析】: 如果 并且 可达，那么就可以用 来松弛 ，也就是 C 选项的代码。这里解释一下 A 选项为什么错误：首先因为是单选题，C 选项的逻辑更完整；其次，A 选项可能会导致 dist[i][k] + dis[k][j] 的值溢出，最终导致转移的含义出现偏差。
【答案】: B。
【解析】: 个位只有 三种选择，分别讨论这 种情况。当个位为 时，剩下 位随便放，有 种方案；当个位为 或 时，首位不能为 ，那么从高位到低位依次有 种可能性，方案数为 。总方案数为 。
【答案】: A。
【解析】: 如果别的点 v 可以通过到达 u 到达最小生成树，并且比之前到达最小生成树的距离更小，那么就更新 v 到达生成树的最小距离，也就是 A 选项。这里说一下为什么不选 B 选项：首先因为是单选题，A 选项逻辑更完整；其次，B 选项没有判断 u,v 之间是否有边相连，万一这个代码中没有边相连用的是负数、 等来表示，那么更新到生成树的距离的时候就会有问题。
【答案】: C。
【解析】: 三点共线可以用斜率相等来判断，也就是 来判断，这个式子转化为代码就是 C 选项。
【答案】: A。
【解析】:sizeof(a) 求解的是 a 数组的字节大小，一个 int 占用 个字节，共 个字节；p 是一个指向数组 int [4] 的指针，在 64 位系统下，指针变量占 个字节； 仍是一个指针，占 个字节；q 是指向数组 a 首地址的指针，也占用 个字节。因此选 A。
2. 判断题（每题 2 分，共 20 分）
2.1 判断题题面
2.2 判断题解析
第 1 题：。static 成员变量不属于结构体对象，属于结构体本身，不属于任何实例，存储在静态区（也称全局数据区）。
第 2 题：。二项式定理基础内容。
第 3 题：。const int & 表示常引用，既可以绑定左值，又可以绑定右值。
第 4 题：。最小生成树唯一，不一定图中所有边权各不相同，只要权值相同的边不影响最小生成树的唯一性即可。
第 5 题：。最坏情况时间复杂度会退化为 。
第 6 题：。所有顶点度数为偶数时存在欧拉回路的必要条件，但还需要非零度顶点在同一个连通分量中。
第 7 题：。ST 表预处理时间复杂度为 ，每次查询时间复杂度为 。
第 8 题：。边的相对大小不会发生变化，因此正确。
第 9 题：。考察最小生成树算法基础。
第 10 题：。当两种方式的“状态空间”数不同时，时间复杂度就不一样。
3. 编程题（每题 25 分，共 50 分）
3.1 编程题 1（消息查找）
分析
这道题本质上是个「最短路径」问题。
总共有 个点，有两种类型的边，普通边：对于任意 都有一条 权重为 的边（表示向前翻了一条消息）；引用边：如果消息 引用了 ，那么就存在一条 权重为 的边（表示跳转到引用的消息）。
这些边都是从编号大的指向编号小的，整个图是一个有向无环图（DAG）。每次询问从 点走到 点的最短路。
如果我们把整个图建出来跑最短路，那么对于每次查询需要 的时间复杂度，总时间复杂度为 ，只能拿到暴力分。
题目保证至多只有 条引用消息。那么最多只有 个「关键点」拥有跳跃能力（引用边的起点）或者跳跃的落点（引用边的终点）。因此，我们可以只关注「关键点」，将图压缩。
将所有涉及引用的消息编号提取出来，作为「关键点」，这样的关键点最多 个。
因为是 DAG 图，就可以用 DP 预处理出任意两个「关键点」之间的最短路，每次查询的时候我们只需要计算出距离起点 最近的关键点 ，距离终点最近的关键点 ，然后就可以 的回答 的最短路了，就是 。
具体地：
将关键点按编号从小到大排序，记为 。因为是 DAG 图，只会向编号小的点移动，那么就可以用 DP 预处理出任意两个关键点之间的最短路。
设 表示 这个关键点到 这个关键点的最短路。
我们倒序递推到更小关键点，天然满足拓扑序：
对于每个起点 i： 对于当前点 j (从 i 递减到 1)： 1. 可以走到前一个关键点 j-1（行走边） 2. 如果 p[j] 有引用，可以跳到 r[p[j]]（跳跃边）状态转移：
dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + (a[j] - a[j - 1])); // 转移 1：普通边if (r[a[j]] > 0) { // 转移 2：跳跃边（如果 a[j] 有引用）int k = pos[r[a[j]]]; // 引用目标在关键点中的下标 dp[i][k] = min(dp[i][k], dp[i][j] + 1);}至于求解离起点 最近的关键点 ，和离终点 最近的关键点 的做法有很多：
方法1：直接二分查找求解，每次查询需要 复杂度。
方法2：预处理
pre[i]和suf[i]数组，分别表示离 最近的 的关键点和离 最近的 的关键点，然后 递推这两个数组的，每次查询是 的。
至此，对于每一次询问，找到距离 最近的 的关键点 ，以及距离 最近的 的关键点 ，答案就由三部分组成，。特殊地：当 时，说明 和 中间没有特殊点，答案就是 。
总时间复杂度为 ，其中 表示关键点的数量，不超过 。
❝可能有人有疑问为什么选择最近的关键点最优？
这个很容易证明，我们以距离 最近的关键点 举例，假设入口选择更小的关键点 ，那么代价 为 ，代价 为 ，我们只需要比较 和 的大小。从 走到 一定会先经过 这个关键点，且中间没有其他关键点。那么 可以拆分成 ，而最短路网络中一定有 ，所以 。
同理，可以证明对于出口也一定是离 最近的 出去的。
换句话说，从 到任何更小的关键点一定都要经过 ，从任何更大的关键点到 都要先经过 ，所以选择它们作为关键网络的入口和出口一定是最优的。
代码
#include<bits/stdc++.h>usingnamespacestd;constint inf = 0x3f3f3f3f;constint maxn = 1e5 + 5;int r[maxn], pos[maxn], pre[maxn], suf[maxn], n, q;int a[2005], dp[2005][2005], tot;bool vis[maxn];intmain(){cin>>n>>q;for(int i = 1; i <= n; ++i) {cin>>r[i];if(r[i]) vis[i] = vis[r[i]] = true; }for(int i = 1; i <= n; ++i) {if(vis[i]) { // 关键点 a[++tot] = i; pos[i] = tot; } }memset(dp, 0x3f, sizeof(dp));for(int i = 1; i <= tot; ++i) { dp[i][i] = 0;for(int j = i; j >= 2; --j) { // 刷表法：已知状态去更新后续状态 dp[i][j - 1] = min(dp[i][j - 1], dp[i][j] + a[j] - a[j - 1]); // 普通边if(r[a[j]]) { // 引用边int k = pos[r[a[j]]]; dp[i][k] = min(dp[i][k], dp[i][j] + 1); } } }for(int i = 1; i <= n; ++i) { pre[i] = pre[i - 1];if(vis[i]) pre[i] = i; } suf[n + 1] = n + 1;for(int i = n; i >= 1; --i) { suf[i] = suf[i + 1];if(vis[i]) suf[i] = i; }while(q--) {int x, y;cin>>x>>y;int tmpx = pre[x], tmpy = suf[y], ans;if(tmpx < tmpy) ans = x - y;else ans = x - tmpx + dp[pos[tmpx]][pos[tmpy]] + tmpy - y;cout<<ans<<'\n'; }return0;}3.2 编程题 2（子图最短路）
分析
总共有 个区间，对于每一个区间用 Floyed 算法跑最短路时间复杂度为 ，总时间复杂度为 。对于满足数据会超时，需要考虑优化。
注意到区间是连续的 。如果我们固定左端点 ，让右端点 从 慢慢增加到 ：
：只有 1 个点。 ：增加 1 个点，增加一些边。 ：再增加 1 个点...
当 增加 时，我们只需要更新涉及新点 的最短路径，而不需要重新计算所有路径！换句话说，当 增加 的时候，将 加入子图，作为 Floyed 算法中的中转点，然后更新所有点对新增一个中转点 的最短路。更新完之后，累加当前子图中所有点对的最短路。
总时间复杂度为 ，考察对 Floyed 算法的理解。
代码
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint maxn = 105, mod = 1e9, inf = 0x3f3f3f3f;int g[maxn][maxn], n, m;ll dp[maxn][maxn], ans;intmain(){cin>>n>>m;memset(g, 0x3f, sizeof(g));for(int i = 1; i <= n; ++i) g[i][i] = 0;while(m--) {int u, v, w;cin>>u>>v>>w; g[u][v] = g[v][u] = min(g[u][v], w); }for(int l = 1; l <= n; ++l) {for(int i = 1; i <= n; ++i) {for(int j = 1; j <= n; ++j) dp[i][j] = g[i][j]; }for(int r = l; r <= n; ++r) {for(int i = 1; i <= n; ++i) {for(int j = 1; j <= n; ++j) dp[i][j] = min(dp[i][j], dp[i][r] + dp[r][j]); }for(int i = l; i <= r; ++i) {for(int j = i; j <= r; ++j) {if(dp[i][j] == inf) continue; ans = (ans + dp[i][j]) % mod; } } } }cout<<ans;return0;}如果你喜欢这类赛事真题解析文章，欢迎点赞、转发、收藏，让更多人看到这份真诚的分享！
欢迎点击下方名片关注
