BZOJ 4675（点分治）

题面

分析

由于期望的线性性，我们可以分别计算每个点对对答案的贡献

有三个人取数字，分开对每个人考虑

设每个人分别取了k个数，则一共有\(C_n^k\)种组合,选到每种组合的概率为\(\frac{1}{C_n^k}\)

对于一个幸运点对，包含它的组合有\(C_{n-2}^{k-2}\)种(k个点中有2个点是该点对，再从剩下的n-2个点中选k-2个点，每种的贡献均为1)

所以每一个点对的贡献是

\[\frac{C_{n-2}^{k-2}}{C_n^k}=\frac{\frac{(n-2)!}{(n-k)!\times (k-2)!}}{\frac{n!}{(n-k)! \times k !}}=\frac{(n-2)! \times k !}{n! \times (k-2)!}=\frac{k(k-1)}{n(n-1)}
\]

因此总答案为\(a \times \frac{k(k-1)}{n(n-1)}\),其中a为幸运点对的数量

所以只要求出幸运点对数量即可

对于每一个幸运数num[i],我们进行一次点分治，求出长度为num[i]的路径数（直接套点分治板子，先求长度>=num[i]的路径数，再减去长度>num[i]的路径数量），并累计进答案

注意最后n*(n-1)要用double，否则会爆int

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 50005

using namespace std;

int n,k;

struct edge{

	int from;

	int to;

	int next;

}E[maxn<<1];

int ecnt=1;

int head[maxn];

inline void add_edge(int u,int v){

	ecnt++;

	E[ecnt].from=u;

	E[ecnt].to=v;

	E[ecnt].next=head[u];

	head[u]=ecnt;

}

int root=0,sum;

int f[maxn];

int sz[maxn];

int vis[maxn];

void get_root(int x,int fa){

	sz[x]=1;

	f[x]=0;

	for(int i=head[x];i;i=E[i].next){

		int y=E[i].to;

		if(y!=fa&&!vis[y]){

			get_root(y,x);

			sz[x]+=sz[y];

			f[x]=max(f[x],sz[y]);

		}

	}

	f[x]=max(f[x],sum-f[x]);

	if(f[x]<f[root]) root=x;

}

int cnt=0;

int deep[maxn];

int res[maxn];

void get_deep(int x,int fa){

	res[++cnt]=deep[x];

	for(int i=head[x];i;i=E[i].next){

		int y=E[i].to;

		if(y!=fa&&!vis[y]){

			deep[y]=deep[x]+1;

			get_deep(y,x);

		}

	}

}

int calc(int x,int d0){

	deep[x]=d0;

	cnt=0;

	get_deep(x,0);

	sort(res+1,res+1+cnt);

	int l=1,r=cnt;

	int ans1=0;

	while(l<r){

		if(res[l]+res[r]<=k){

			ans1+=(r-l);

			l++;

		}else r--;

	}

	l=1,r=cnt;

	int ans2=0;

	while(l<r){

		if(res[l]+res[r]<k){

			ans2+=(r-l);

			l++;

		}else r--;

	}

	return ans1-ans2;

}

int ans=0;

void solve(int x){

	vis[x]=1;

	ans+=calc(x,0);

	for(int i=head[x];i;i=E[i].next){

		int y=E[i].to;

		if(!vis[y]){

			ans-=calc(y,1);

			root=0;

			sum=sz[y];

			get_root(y,0);

			solve(root);

		}

	}

}

void divide_ini(){

	memset(deep,0,sizeof(deep));

	memset(f,0,sizeof(f));

	memset(sz,0,sizeof(sz));

	memset(vis,0,sizeof(vis));

	root=0;

	sum=n;

	f[0]=n;

	get_root(1,0);

}

int m;

int num[maxn];

int main(){

	int u,v;

	scanf("%d %d",&n,&m);

	for(int i=1;i<=m;i++){

		scanf("%d",&num[i]);

	}

	for(int i=1;i<n;i++){

		scanf("%d %d",&u,&v);

		add_edge(u,v);

		add_edge(v,u);

	}

	for(int i=1;i<=m;i++){

		k=num[i];

		divide_ini();

		solve(root);

	}

	double k1,k2,k3;

	if(n%3==0) k1=k2=k3=n/3;

	else if(n%3==1){

		k1=n/3+1;

		k2=n/3;

		k3=n/3;

	}else{

		k1=n/3+1;

		k2=n/3+1;

		k3=n/3;

	}

	printf("%.2lf\n",ans*k1*(k1-1)/((double)n*(n-1)));//强制转成double,防止溢出

	printf("%.2lf\n",ans*k2*(k2-1)/((double)n*(n-1)));

	printf("%.2lf\n",ans*k3*(k3-1)/((double)n*(n-1)));

}

巴特西

BZOJ 4675（点分治）

题面

分析

代码

最新文章

热门文章