「BJOI2014」想法

发表于 | 分类于 | | 浏览量： 次

什么鬼？省选也出这种玄学随机算法题？

传送门

洛谷P4581

题解

首先这题一看就很不可解。

所以上随机算法（人家题面都告诉你了QwQ）。

写之前先膜拜一下dalao，保佑AC。

sto 黄霖 orz

对于一个节点，将所用能走到它的叶子节点都存下来是不现实的，所以我们只存$k$个。并且我们要先为每个叶子节点i随机一个权值$W_i$，满足$W_i \in [1,RANDMAX]$。对于每个非叶子节点，我们需要存下所有能走到个节点的叶子节点的权值的前$k$小。设这个节点的答案为$ans$，第$k$小权值为$F_k​$根据期望可得

故有

令$k=50$，多为叶子节点随机几套权值求平均值，吸个氧，放个大悲咒，选个好种子，你就能AC了。

代码

这是真的玄学QwQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long LL;
const int maxn=1000005,k=50;
int n,m,son[maxn][2],w[maxn],num[maxn],f[maxn][55];LL ans[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void Merge(int s1,int s2,int now)         //从两个儿子节点合并过来
{
	register int i=1,j=1;num[now]=k;
	for(register int p=1;p<=k;p++)
	{
		while(f[s1][i]==f[now][p-1]&&i<=num[s1]) i++;  //注意去重
		while(f[s2][j]==f[now][p-1]&&j<=num[s2]) j++;
		if(i>num[s1]&&j>num[s2]){num[now]=p-1;break;}
		if(i<=num[s1]&&(f[s1][i]<f[s2][j]||j>num[s2])){f[now][p]=f[s1][i];i++;}
		else if(j<=num[s2]){f[now][p]=f[s2][j];j++;}
	}
}
int main()
{
	srand(20050429);
	n=read();m=read();
	for(register int i=m+1;i<=n;i++){son[i][0]=read();son[i][1]=read();}
	for(int r=1;r<=4;r++)
	{
		for(register int i=1;i<=n;i++){w[i]=rand();while(!w[i])w[i]=rand();}
		for(register int i=1;i<=m;i++){f[i][1]=w[i];num[i]=1;}
		for(register int i=m+1;i<=n;i++)
		{
			Merge(son[i][0],son[i][1],i);
			if(num[i]<k) ans[i]=num[i]*4;          //如果还没到k个就不用根据期望计算了
			else ans[i]+=(LL)k*RAND_MAX/f[i][k];
		}
	}
	for(int i=m+1;i<=n;i++) printf("%lld\n",ans[i]/4);
	return 0;
}