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

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

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

适合人群：

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

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

---

编程题

P11966 上学

【题目来源】

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

【题目描述】

C 城可以视为由n nn个结点与m mm条边组成的无向图。 这些结点依次以1 , 2 , … , n 1,2,…,n1,2,…,n标号，边依次以1 ≤ i ≤ m 1≤i≤m1≤i≤m连接边号为u i u_iui​与v i v_ivi​的结点，长度为l i l_ili​米。

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

【输入】

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

接下来m mm行，每行三个正整数u i , v i , l i u_i,v_i,l_iui​,vi​,li​，表示 C 城中的一条无向边。

接下来q qq行，每行一个正整数h i h_ihi​，表示一位同学的情况。

【输出】

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

【输入样例】

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>usingnamespacestd;#defineintlonglong// 使用long long类型别名constintN=200005,M=400005;// 定义最大节点数和边数typedefpair<int,int>PII;// 定义pair类型，用于优先队列存储(距离,节点)// 图的邻接表存储intn,m,s,q;// n-节点数, m-边数, s-起点, q-查询次数inth[N],w[M],e[M],ne[M],idx;// 邻接表数组intdist[N];// 存储起点到各点的最短距离boolst[N];// 标记节点是否已确定最短距离// 添加边到邻接表voidadd(inta,intb,intc){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;}// Dijkstra算法实现voiddijkstra(){memset(dist,0x3f3f3f3f,sizeofdist);// 初始化距离为无穷大dist[s]=0;// 起点到自身的距离为0// 使用小根堆优化，存储(距离,节点)对priority_queue<PII,vector<PII>,greater<PII>>heap;heap.push({0,s});while(heap.size()){autot=heap.top();heap.pop();intver=t.second,distance=t.first;if(st[ver])continue;// 如果已确定最短距离则跳过st[ver]=true;// 标记为已确定// 遍历当前节点的所有邻接边for(inti=h[ver];i!=-1;i=ne[i]){intj=e[i];// 松弛操作：如果发现更短路径则更新if(dist[j]>distance+w[i]){dist[j]=distance+w[i];heap.push({dist[j],j});}}}}signedmain(){cin>>n>>m>>s>>q;memset(h,-1,sizeofh);// 初始化邻接表头指针// 读入所有边并构建无向图for(inti=1;i<=m;i++){inta,b,c;cin>>a>>b>>c;add(a,b,c);add(b,a,c);// 无向图添加双向边}dijkstra();// 计算最短路径// 处理查询for(inti=1;i<=q;i++){intx;cin>>x;cout<<dist[x]<<endl;// 输出查询结果}return0;}

【运行结果】

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 nn个节点的树，其中节点的编号从1 11到n nn。

小杨设置了一个好点对{ ⟨ u 1 , v 1 ⟩ , ⟨ u 2 , v 2 ⟩ , … , ⟨ u a , v a ⟩ } \{⟨u_1,v_1⟩,⟨u_2,v_2⟩,…,⟨u_a,v_a⟩\}{⟨u1​,v1​⟩,⟨u2​,v2​⟩,…,⟨ua​,va​⟩}和一个坏点对⟨ b u , b v ⟩ ⟨b_u,b_v⟩⟨bu​,bv​⟩。一个节点能被删除，当且仅当：

• 删除该节点后对于所有的1 ≤ i ≤ a 1≤i≤a1≤i≤a，好点对u i u_iui​和v i v_ivi​仍然连通；
• 删除该节点后坏点对b u b_ubu​和b v b_vbv​不连通。

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

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

【输入】

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

接下来n − 1 n−1n−1行，每行包含两个正整数x i , y i x_i,y_ixi​,yi​，代表存在一条连接节点x i x_ixi​和y i y_iyi​的边；

之后a aa行，每行包含两个正整数u i , v i u_i,v_iui​,vi​，代表一个好点对⟨ u i , v i ⟩ ⟨u_i,v_i⟩⟨ui​,vi​⟩；

最后一行包含两个正整数b u , b v b_u,b_vbu​,bv​，代表坏点对⟨ b u , b v ⟩ ⟨b_u,b_v⟩⟨bu​,bv​⟩。

【输出】

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

【输入样例】

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>usingnamespacestd;constintN=1000005;// 最大节点数constintD=20;// 倍增的最大深度// 全局变量intn,a,cnt;// n-节点数, a-操作次数, cnt-结果计数器vector<int>h[N];// 邻接表存储树结构intdep[N];// 节点深度intpower[N];// 节点权值（差分数组）intfa[N][D];// 倍增数组，fa[i][j]表示i的2^j级祖先queue<int>q;// BFS队列// BFS初始化深度和倍增数组voidbfs(introot){memset(dep,0x3f,sizeof(dep));// 初始化深度为无穷大dep[0]=0;// 哨兵节点深度为0dep[root]=1;// 根节点深度为1q.push(root);while(!q.empty()){intt=q.front();q.pop();for(inti=0;i<h[t].size();i++){intj=h[t][i];if(dep[j]>dep[t]+1){// 如果发现更短路径dep[j]=dep[t]+1;// 更新深度q.push(j);fa[j][0]=t;// 记录父节点// 预处理倍增数组for(intk=1;k<=19;k++)fa[j][k]=fa[fa[j][k-1]][k-1];}}}}// 求最近公共祖先(LCA)intlca(intx,inty){if(dep[x]<dep[y])swap(x,y);// 保证x更深// 将x提升到与y同一深度for(intk=19;k>=0;k--)if(dep[fa[x][k]]>=dep[y])x=fa[x][k];if(x==y)returnx;// 如果已经是同一个节点// 同时向上寻找for(intk=19;k>=0;k--)if(fa[x][k]!=fa[y][k]){x=fa[x][k];y=fa[y][k];}returnfa[x][0];// 返回LCA}// 后序遍历计算子树权值和voiddfs2(intu,intf){for(inti=0;i<h[u].size();i++){intj=h[u][i];if(j==f)continue;// 跳过父节点dfs2(j,u);// 递归处理子节点power[u]+=power[j];// 累加子节点的权值}}intmain(){cin>>n>>a;// 构建树结构for(inti=1;i<n;i++){intu,v;cin>>u>>v;h[u].push_back(v);h[v].push_back(u);}// 预处理深度和倍增数组bfs(1);// 处理a次操作（路径加1）for(inti=1;i<=a;i++){intx,y;cin>>x>>y;intl=lca(x,y);// 求LCA// 差分操作++power[x];++power[y];--power[l];--power[fa[l][0]];}// 计算每个节点的最终权值dfs2(1,0);// 查询路径上权值为0的边数intu,v;cin>>u>>v;intl=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;return0;}

【运行结果】

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