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

题目注意

尝试后跳板不再视为跳板。

思路

首先，要求任意一个出发的期望，其实也就是求从每个点出发，最短时间期望的平均值。

不妨设

dp_i

表示起点为

i

的最短时间期望，

Fail_i

表示

i

为起点，跳失败的概率。

分成三种情况：

如果 $i=1$ ，则 $Fail_i = 1,dp_i = 0$ 。
如果 $father_i$ 是“跳板”，显然不跳是较优的，这里和后面的点失败的概率也会增加，则 $Fail_i = Fail_{father_i} \times P,dp_i = dp_{father_i} + 1$ 。
如果 $father_i$ 不是“跳板”，显然跳较优，那么从 $i$ 跳成功了和从 $father_i$ 跳成功是一样的，不成功则转化为 $dp_{father_i}$ ，则 $Fail_i = Fail_{father_i},dp_i = dp_{father_i} + Fail_i$ 。

~~目前最优解的~~代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m;
double P;
bool Jump[N];

namespace Graph
{
	int head[N],tot_edge;
	struct edge
	{
		int v,next;
	}e[N<<1];
	void G_init()
	{
		memset(head,-1,sizeof(head));
		tot_edge=-1;
	}
	void add(int u,int v)
	{
		e[++tot_edge]=(edge){v,head[u]};
		head[u]=tot_edge;
	}
	void add_edge(int u,int v)
	{
		add(u,v),add(v,u);
	}
} using namespace Graph;

double dp[N];
double Fail[N];
void dfs(int x,int fa)
{
	int i;
	for(i=head[x];~i;i=e[i].next)
	{
		int y=e[i].v;
		if(y==fa)
		continue;
		if(Jump[x]==0) dp[y]=dp[x]+(Fail[y]=Fail[x]);
		else Fail[y]=Fail[x]*P,dp[y]=dp[x]+1;
		dfs(y,x);
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int i,u,v;
	cin>>n>>m>>P;
	G_init();
	for(i=1;i<=n-1;i++)
	{
		cin>>u>>v;
		add_edge(u,v);
	}
	for(i=1;i<=m;i++)
	{
		cin>>u;
		Jump[u]=1;
	}
	Fail[1]=1;
	dfs(1,0);
	
	double ans=0; for(i=1;i<=n;i++) ans+=dp[i];
	cout<<fixed<<setprecision(2)<<(ans/n)<<'\n';
	return 0;
}

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

文章操作

题目注意

思路

相关推荐

评论

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