GESP认证C++编程真题解析 | 202503 八级 - 详解

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

---

编程题

P11966 上学

【题目来源】

洛谷：P11966 [GESP202503 八级] 上学 - 洛谷

【题目描述】

C 城可以视为由 $n$ 个结点与 $m$ 条边组成的无向图。 这些结点依次以 $1,2,\dots ,n$ 标号，边依次以 $1\le i\le m$ 连接边号为 $u_i$ 与 $v_i$ 的结点，长度为 $l_i$ 米。

小 A 的学校坐落在 C 城的编号为 $s$ 的结点。小 A 的同学们共有 $q$ 位，他们想在保证不退到的前提下，每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校，于是找到了聪明的小 A。第 $i$ 位同学 $(1\le i\le q)$ 告诉小 A，他的家位置于编号为 $h_i$ 的结点，并且他每秒钟能行走 $1$ 米。请你帮小 A 计算，每位同学从家出发需要多少秒才能到达学校呢？

【输入】

第一行，四个正整数 $n,m,s,q$，分别表示 C 城的结点数与边数，学校所在的结点编号，以及小 A 同学们的数量。

接下来 $m$ 行，每行三个正整数 $u_i,v_i,l_i$，表示 C 城中的一条无向边。

接下来 $q$ 行，每行一个正整数 $h_i$，表示一位同学的情况。

【输出】

共 $q$ 行，对于每位同学，输出一个整数，表示从家出发到学校的最短时间。

【输入样例】

5 5 3 3
1 2 3
2 3 2
3 4 1
4 5 3
1 4 2
5
1
4

【输出样例】

4
3
1

【算法标签】

《洛谷 P11966 上学》 #最短路# #GESP# #2025#

【代码详解】

#include <bits/stdc++.h>using namespace std;#define int long long  // 使用long long类型别名const int N = 200005, M = 400005;  // 定义最大节点数和边数typedef pair<int, int> PII;  // 定义pair类型，用于优先队列存储(距离,节点)// 图的邻接表存储int n, m, s, q;       // n-节点数, m-边数, s-起点, q-查询次数int h[N], w[M], e[M], ne[M], idx;  // 邻接表数组int dist[N];          // 存储起点到各点的最短距离bool st[N];           // 标记节点是否已确定最短距离// 添加边到邻接表void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;}// Dijkstra算法实现void dijkstra() {memset(dist, 0x3f3f3f3f, sizeof dist);  // 初始化距离为无穷大dist[s] = 0;  // 起点到自身的距离为0// 使用小根堆优化，存储(距离,节点)对priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, s});while (heap.size()) {auto t = heap.top(); heap.pop();int ver = t.second, distance = t.first;if (st[ver]) continue;  // 如果已确定最短距离则跳过st[ver] = true;         // 标记为已确定// 遍历当前节点的所有邻接边for (int i = h[ver]; i != -1; i = ne[i]) {int j = e[i];// 松弛操作：如果发现更短路径则更新if (dist[j] > distance + w[i]) {dist[j] = distance + w[i];heap.push({dist[j], j});}}}}signed main() {cin >> n >> m >> s >> q;memset(h, -1, sizeof h);  // 初始化邻接表头指针// 读入所有边并构建无向图for (int i = 1; i <= m; i++) {int a, b, c; cin >> a >> b >> c;add(a, b, c); add(b, a, c);  // 无向图添加双向边}dijkstra();  // 计算最短路径// 处理查询for (int i = 1; i <= q; i++) {int x; cin >> x;cout << dist[x] << endl;  // 输出查询结果}return 0;}

【运行结果】

5 5 3 3
1 2 3
2 3 2
3 4 1
4 5 3
1 4 2
5
4
1
3
4
1

P11967 割裂

【题目来源】

洛谷：P11967 [GESP202503 八级] 割裂 - 洛谷

【题目描述】

小杨有一棵包含 $n$ 个节点的树，其中节点的编号从 $1$ 到 $n$。

小杨设置了一个好点对 $\{⟨u_1,v_1⟩,⟨u_2,v_2⟩,\dots ,⟨u_a,v_a⟩\}$ 和一个坏点对 $⟨b_u,b_v⟩$。一个节点能被删除，当且仅当：

• 删除该节点后对于所有的 $1\le i\le a$，好点对 $u_i$ 和 $v_i$ 仍然连通；
• 删除该节点后坏点对 $b_u$ 和 $b_v$ 不连通。

如果点对中的任意一个节点被删除，其视为不连通。

小杨想知道，还有多少个节点能被删除。

【输入】

第一行包含两个非负整数 $n,a$，含义如下题面所示。

接下来 $n-1$ 行，每行包含两个正整数 $x_i,y_i$，代表存在一条连接节点 $x_i$ 和 $y_i$ 的边；

之后 $a$ 行，每行包含两个正整数 $u_i,v_i$，代表一个好点对 $⟨u_i,v_i⟩$；

最后一行包含两个正整数 $b_u,b_v$，代表坏点对 $⟨b_u,b_v⟩$。

【输出】

输出一个非负整数，代表删除的节点个数。

【输入样例】

6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6

【输出样例】

2

【算法标签】

《洛谷 P11967 割裂》 #倍增# #最近公共祖先LCA# #差分# #GESP# #2025#

【代码详解】

#include <bits/stdc++.h>using namespace std;const int N = 1000005;  // 最大节点数const int D = 20;       // 倍增的最大深度// 全局变量int n, a, cnt;          // n-节点数, a-操作次数, cnt-结果计数器vector<int> h[N];       // 邻接表存储树结构int dep[N];             // 节点深度int power[N];           // 节点权值（差分数组）int fa[N][D];           // 倍增数组，fa[i][j]表示i的2^j级祖先queue<int> q;           // BFS队列// BFS初始化深度和倍增数组void bfs(int root) {memset(dep, 0x3f, sizeof(dep));  // 初始化深度为无穷大dep[0] = 0;                      // 哨兵节点深度为0dep[root] = 1;                   // 根节点深度为1q.push(root);while (!q.empty()) {int t = q.front(); q.pop();for (int i = 0; i < h[t].size(); i++) {int j = h[t][i];if (dep[j] > dep[t] + 1) {  // 如果发现更短路径dep[j] = dep[t] + 1;    // 更新深度q.push(j);fa[j][0] = t;           // 记录父节点// 预处理倍增数组for (int k = 1; k <= 19; k++)fa[j][k] = fa[fa[j][k-1]][k-1];}}}}// 求最近公共祖先(LCA)int lca(int x, int y) {if (dep[x] < dep[y]) swap(x, y);  // 保证x更深// 将x提升到与y同一深度for (int k = 19; k >= 0; k--)if (dep[fa[x][k]] >= dep[y])x = fa[x][k];if (x == y) return x;  // 如果已经是同一个节点// 同时向上寻找for (int k = 19; k >= 0; k--)if (fa[x][k] != fa[y][k]) {x = fa[x][k];y = fa[y][k];}return fa[x][0];  // 返回LCA}// 后序遍历计算子树权值和void dfs2(int u, int f) {for (int i = 0; i < h[u].size(); i++) {int j = h[u][i];if (j == f) continue;  // 跳过父节点dfs2(j, u);            // 递归处理子节点power[u] += power[j];  // 累加子节点的权值}}int main() {cin >> n >> a;// 构建树结构for (int i = 1; i < n; i++) {int u, v;cin >> u >> v;h[u].push_back(v);h[v].push_back(u);}// 预处理深度和倍增数组bfs(1);// 处理a次操作（路径加1）for (int i = 1; i <= a; i++) {int x, y;cin >> x >> y;int l = lca(x, y);  // 求LCA// 差分操作++power[x]; ++power[y];--power[l]; --power[fa[l][0]];}// 计算每个节点的最终权值dfs2(1, 0);// 查询路径上权值为0的边数int u, v;cin >> u >> v;int l = lca(u, v);// 统计u到LCA路径上的0权值边while (u != l) {if (power[u] == 0) cnt++;u = fa[u][0];}// 统计v到LCA路径上的0权值边while (v != l) {if (power[v] == 0) cnt++;v = fa[v][0];}// 检查LCA节点if (power[u] == 0) cnt++;cout << cnt << endl;return 0;}

【运行结果】

6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6
2