2025年3月GESP八级真题解析

第一题——上学

题目描述

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例 1

输出样例 1

4
3
1

数据范围

对于 $20\%$ 的测试点，保证 $q = 1$ 。

对于另外 $20\%$ 的测试点，保证 $1 \leq n \leq 500 ， 1 \leq m \leq 500$ 。

对于所有测试点，保证 $1≤n≤2×10^5，1≤m≤2×10^5，1≤q≤2×10^5$ ， $1≤u_i,v_i,s,h_i≤n，1≤l_i≤10^6$ 。保证给定的图联通。

分析

这道题其实非常简单，是一道裸的最短路问题，我们只需要从终点出发反着跑就可以了，非常的简单。

#include<bits/stdc++.h>
using namespace std;
const int INF=2e5+10;struct Node{long long v,num;bool operator <(const Node &a)const{return num>a.num;}
};vector<Node> mp[INF];
long long dis[INF],used[INF];
priority_queue<Node> q;void dijkstra(int x){dis[x]=0,q.push({x,0});while (!q.empty()){long long u=q.top().v;q.pop();if (used[u]==1)continue;used[u]=1; int len=mp[u].size();for (int i=0;i<len;i++){long long v=mp[u][i].v,w=mp[u][i].num;if (dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push({v,dis[v]});}}}
}int main(){int n,m,s,q;cin>>n>>m>>s>>q;for (int i=1;i<=n;i++){dis[i]=1e18;}for (int i=1;i<=m;i++){long long u,v,l;cin>>u>>v>>l;mp[u].push_back({v,l});mp[v].push_back({u,l});}dijkstra(s);for (int i=1;i<=q;i++){int t;cin>>t;cout<<dis[t]<<endl;}return 0;
}

广告
最短路算法——CSDN
最短路算法——博客园

第二题——割裂

题面描述

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

小杨设置了 $a$ 个好点对< $u_1$ , $v_1$ >,< $u_2$ , $v_2$ >,…,< $u_a$ , $v_a$ >和 1 个坏点对 < $b_u$ , $b_v$ >。一个节点能够被删除，当且仅当：

删除该节点后对于所有的 $i (1 \leq i \leq 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$ >。

输出格式

输出一个正整数，代表能够删除的节点个数。

样例

输入样例

输出样例

数据范围

对于全部数据，保证有 $1≤n≤10^6,0≤a≤10^5,ui≠vi,bu≠bv$ 。

分析

这道题其实还有点思维含量，根据题目，我们要知道那些点是能删的，那些点是不能删的，基于此，我们就要维护出来每个点被那些点所经过了，或者说被经过了几次，如果说一个点没有被任何的好点经过，并且被坏点经过了，那么就说明这个点是可以被删除的，我这里说的被好点经过指的是两个好点之间的路径哈，不要搞错了。

如果说思路是这样的话，我们是不是就可以很显然想到一个做法，树上差分？而且这个是一个非常简答的点差分，所以说没有任何的难度好吧。

#include<bits/stdc++.h>
using namespace std;
const int INF=1e6+10;vector<int> mp[INF];
int dp[INF][30],deep[INF],p[INF],d[INF];void prepare(int x,int fa){for (int i=1;(1<<i)<=deep[x]-1;i++){dp[x][i]=dp[dp[x][i-1]][i-1];}int len=mp[x].size();for (int i=0;i<len;i++){if (mp[x][i]==fa)continue;int t=mp[x][i];dp[t][0]=x,deep[t]=deep[x]+1;prepare(t,x);}
}
int getroot(int x,int y){if (deep[x]<deep[y])swap(x,y);int index=__lg(deep[x]-deep[y]);for (int i=index;i>=0;i--){if (deep[dp[x][i]]>=deep[y])x=dp[x][i];if (deep[x]==deep[y])break;}if (x==y)return x;for (int i=20;i>=0;i--){if (dp[x][i]!=dp[y][i])x=dp[x][i],y=dp[y][i];}return dp[x][0];
}void get_p(int x,int fa){int len=mp[x].size();for (int i=0;i<len;i++){if (mp[x][i]==fa)continue;int t=mp[x][i];get_p(t,x);p[x]+=p[t];}
}void get_d(int x,int fa){int len=mp[x].size();for (int i=0;i<len;i++){if (mp[x][i]==fa)continue;int t=mp[x][i];get_d(t,x);d[x]+=d[t];}
}
int main(){int n,a;cin>>n>>a;for (int i=1;i<n;i++){int u,v;cin>>u>>v;mp[u].push_back(v);mp[v].push_back(u);}deep[1]=1;prepare(1,-1);for (int i=1;i<=a;i++){int u,v;cin>>u>>v;int root=getroot(u,v);p[u]++,p[v]++,p[root]--,p[dp[root][0]]--;}get_p(1,-1);int b1,b2;cin>>b1>>b2;int root=getroot(b1,b2);d[b1]++,d[b2]++,d[root]--,d[dp[root][0]]--;get_d(1,-1);int cnt=0;for (int i=1;i<=n;i++){if (d[i]&&!p[i])cnt++;}cout<<cnt;return 0;
}