P9428 [蓝桥杯 2023 国 B] 逃跑题解

坑点：

跳跃是向跳板星球的。
其前往根结点路径上的除当前星球以外的第一个跳板星球。
求的是其花费的最短时间的期望。

思路

考虑递推，设当前节点为

u

，它的子节点为

v

。

易发现当

u

为跳板星球时，

dp_{v}=dp_{u}+1

。因为我们是求的其花费的最短时间的期望。

又因

0<p<1

所以不跳是更优的。

当

u

不为跳板星球时，计

cnt

为当前节点前往根结点路径上的跳板星球的个数。

有

dp_{v}=dp_{u}+p^{cnt}×1

。

又因求其花费的最短时间的期望，所以要跳就一直跳，要么不跳，走到父节点。

Code

CPP

#include<bits/stdc++.h>
#define double long double
using namespace std;
const int N=1e6+6;
vector<int> g[N];
bool is[N];
int n,m,cnt;
double dp[N];
double p;
void dfs(int x,int fa,int cnt){
	if(is[x]) cnt++;
	for(int y:g[x]){
		if(y==fa) continue;
		if(is[x]) dp[y]=dp[x]+1;
		else dp[y]=dp[x]+pow(p,cnt);
		dfs(y,x,cnt);
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin>>n>>m>>p;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		is[x]=1;
	}
	dfs(1,0,0);
	double sum=0;
	for(int i=1;i<=n;i++) sum+=dp[i];
	double ans=sum/n;
	printf("%.2Lf",ans);
}

题解：P9428 [蓝桥杯 2023 国 B] 逃跑

文章操作

P9428 [蓝桥杯 2023 国 B] 逃跑题解

坑点：

思路

Code

相关推荐

评论

题解：P9428 [蓝桥杯 2023 国 B] 逃跑