2020暑假牛客多校第九场 K The Flee Plan of Groundhog (树形结构/思维)
程序员文章站
2022-06-15 11:53:35
The Flee Plan of Groundhog 题目大意:有一个土拨鼠在节点1,一个橘子在节点n,在t时刻之前土拨鼠向着n走,橘子不动,从t时刻开始,橘子开始抓土拨鼠,土拨鼠开始跑,土拨鼠 1m/s 橘子 2m/s,问还有多长时间橘子才能抓到土拨鼠。解题思路:t 时刻之后,土拨鼠必然朝着n的反方向移动,土拨鼠走一步,橘子走两步,那么我们可以记录一下t时刻土拨鼠的位置,还有土拨鼠向反方向最多能跑多远。如果土拨鼠向后跑了一步就到头了,那么显然时间是橘子到改点的距离/2向上取整,但是如果土拨鼠可以向...
The Flee Plan of Groundhog
题目大意:
有一个土拨鼠在节点1,一个橘子在节点n,在t时刻之前土拨鼠向着n走,橘子不动,从t时刻开始,橘子开始抓土拨鼠,土拨鼠开始跑,土拨鼠 1m/s 橘子 2m/s,问还有多长时间橘子才能抓到土拨鼠。
解题思路:
t 时刻之后,土拨鼠必然朝着n的反方向移动,土拨鼠走一步,橘子走两步,那么我们可以记录一下t时刻土拨鼠的位置,还有土拨鼠向反方向最多能跑多远。如果土拨鼠向后跑了一步就到头了,那么显然答案是橘子到该点的距离/2向上取整,但是如果土拨鼠可以向后跑很多步,在跑的过程中被逮住了,那么答案就是土拨鼠往后跑的距离的时间。
- 土拨鼠向后跑到了最远处没法再跑蹲躲在角落等着橘子来抓
- 土拨鼠向后跑的过程中被橘子逮住了
分类讨论一下即可。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=500000;
vector<int> ve[maxn];
int dis[maxn],f[maxn],m,ed=1,maxx=0;
void dfs(int x,int pre,int val){ //记录下每个点到n的距离
f[x]=pre;
dis[x]=val;
for(int i=0;i<ve[x].size();i++){
if(ve[x][i]==pre) continue;
dfs(ve[x][i],x,val+1);
}
}
void dfs2(int x,int pre){
maxx=max(maxx,dis[x]); //从t时间所在地点往n点相反的方向跑最远是多少
for(int i=0;i<ve[x].size();i++){
if(ve[x][i]==pre) continue;
dfs2(ve[x][i],x);
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t,n,tmp=1;
cin>>n>>m;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
ve[u].push_back(v);
ve[v].push_back(u);
}
dfs(n,n,0);
while(m--) tmp=f[tmp]; //找出土拨鼠的t时间所在的节点
dfs2(tmp,f[tmp]);
int x=maxx-dis[tmp];
int y=dis[tmp]; // 拨鼠的t时间所在的节点到n的距离
if(tmp==n) cout<<"0\n"; //土拨鼠在t时间之前到了n点
else if(x-y>=0) cout<<max(1,y)<<endl; //土拨鼠跑到最远点之前被橘子逮住了
else cout<<max(1,(maxx+1)/2)<<endl; // 土拨鼠跑到最远点了然后没法再跑了,躲在角落等着橘子来抓
return 0;
}
本文地址:https://blog.csdn.net/weixin_43872264/article/details/107884908
下一篇: IOU与NMS实现代码
推荐阅读
-
2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)
-
【2020牛客多校】第九场 K The Flee Plan of Groundhog——BFS
-
2020暑假牛客多校第九场 K The Flee Plan of Groundhog (树形结构/思维)
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)
-
【2020牛客多校】第九场 K The Flee Plan of Groundhog——BFS
-
2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog
-
2020暑假牛客多校第九场 K The Flee Plan of Groundhog (树形结构/思维)