[Contest20180316]Game

这题有一个结论：如果他是最强的（⑨），那么线段树最优，如果他是最弱的，那么链状树最优

严格证明可能挺困难，感性理解就是公平赛制让强的人容易赢，极度不公平的赛制能让弱的人有机会反杀

所以我们只改他的能力值，二分找到当他的能力值是怎样的时候，链状树和线段树的答案差不多，再不停随机树的形态，这时获胜概率就很可能比链状树和线段树都大了

如果给定了树的形态和每个人的能力值，我们可以DP求出他获胜的概率

设$f_{x,s,k}$表示（在以$x$为根的子树中，选手集合为$s$）选手$k$的获胜概率

记以$x$为根的子树中，叶节点的个数为$siz_x$，那么我们枚举每一个$ls$使得$ls\subset s$且$|ls|=siz_{lson_x}$，$rs=s-ls$，再枚举$u\in ls,v\in rs$，用$f_{lson_x,ls,u}\cdot f_{rson_x,rs,v}\cdot\dfrac{a_u}{a_u+a_v}\cdot\dfrac 1{\binom{siz_x}{siz_{lson_x}}}$更新$f_{x,s,u}$，更新$f_{x,s,v}$是类似的

这样做相当于钦点$u,v$分别在左右子树中赢，再让他们打，并且因为每个人在叶子的位置是随机的，最后还要除去一个组合数表示选出$ls$这样的子集的概率

p.s.学习了一个状压DP枚举子集的技巧：$s'=(s'-1)\&s$

于是就做完了，这题除去玄学的部分还是挺棒的...

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n,l[30],r[30],siz[30],a[30],c[4096],log[4096],low[4096],M,mx;
double f[30][4096][13],fac[13];
int lowbit(int x){return x&-x;}
int count(int x){
	int s=0;
	while(x){
		s++;
		x-=lowbit(x);
	}
	return s;
}
double du(int x){return x;}
double max(double a,double b){return a>b?a:b;}
void dfs(int x){
	int i,j,s,sl,sr,u,v;
	double t;
	if((l[x]|r[x])==0){
		for(i=1;i<=n;i++)f[x][1<<(i-1)][i]=1;
		return;
	}
	dfs(l[x]);
	dfs(r[x]);
	for(s=mx;s;s=(s-1)&mx){
		if(c[s]==siz[x]){
			for(sl=s;sl;sl=(sl-1)&s){
				if(c[sl]==siz[l[x]]){
					sr=s^sl;
					for(i=sl;i;i-=lowbit(i)){
						for(j=sr;j;j-=lowbit(j)){
							u=low[i];
							v=low[j];
							f[x][s][u]+=f[l[x]][sl][u]*f[r[x]][sr][v]*a[u]/du(a[u]+a[v]);
							f[x][s][v]+=f[l[x]][sl][u]*f[r[x]][sr][v]*a[v]/du(a[u]+a[v]);
						}
					}
				}
			}
			t=fac[siz[l[x]]]*fac[siz[r[x]]]/fac[siz[x]];
			for(i=s;i;i-=lowbit(i))f[x][s][low[i]]*=t;
		}
	}
}
int buildseg(int n){
	int x=++M;
	if(n==1){
		siz[x]=1;
		l[x]=r[x]=0;
		return x;
	}
	l[x]=buildseg(n/2);
	r[x]=buildseg(n-n/2);
	siz[x]=siz[l[x]]+siz[r[x]];
	return x;
}
double calcseg(){
	M=0;
	buildseg(n);
	memset(f,0,sizeof(f));
	dfs(1);
	return f[1][mx][1];
}
int buildline(int n){
	int x=++M;
	if(n==1){
		siz[x]=1;
		l[x]=r[x]=0;
		return x;
	}
	l[x]=buildline(n-1);
	r[x]=buildline(1);
	siz[x]=siz[l[x]]+siz[r[x]];
	return x;
}
double calcline(){
	M=0;
	buildline(n);
	memset(f,0,sizeof(f));
	dfs(1);
	return f[1][mx][1];
}
int buildrand(int n){
	int x=++M,t;
	if(n==1){
		siz[x]=1;
		l[x]=r[x]=0;
		return x;
	}
	t=rand()%(n-1)+1;
	l[x]=buildrand(t);
	r[x]=buildrand(n-t);
	siz[x]=siz[l[x]]+siz[r[x]];
	return x;
}
double calcrand(){
	M=0;
	buildrand(n);
	memset(f,0,sizeof(f));
	dfs(1);
	return f[1][mx][1];
}
int main(){
	srand(19260817);
	int i,l,r,mid;
	double res;
	scanf("%d",&n);
	mx=(1<<n)-1;
	for(i=0;i<=mx;i++)c[i]=count(i);
	for(i=1;i<=mx;i++)log[i]=log[i>>1]+1;
	for(i=1;i<=mx;i++)low[i]=log[lowbit(i)];
	fac[0]=1;
	for(i=1;i<=n;i++)fac[i]=i*fac[i-1];
	for(i=1;i<=n;i++)scanf("%d",a+i);
	l=101;
	r=0;
	for(i=2;i<=n;i++){
		if(a[i]<l)l=a[i];
		if(a[i]>r)r=a[i];
	}
	while(l<r){
		mid=(l+r+1)>>1;
		a[1]=mid;
		if(calcline()<calcseg())
			r=mid-1;
		else
			l=mid;
	}
	a[1]=l;
	res=max(calcline(),calcseg());
	while(calcrand()-res<1e-8);
	printf("1\n1 %d\n",a[1]);
	for(i=1;i<n<<1;i++)printf("%d %d\n",::l[i],::r[i]);
}

巴特西

[Contest20180316]Game

最新文章

热门文章