自动搬运

查看原文

来自洛谷，原作者为

	两年打铁 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:28:53，当前版本为作者最后更新于2019-10-24 20:49:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

做完题后看了题解都是神仙打架，蒟蒻只好弱弱地说说自己的DP

先着眼题目中的限制，如果把赛程模拟下，就是个完全二叉树。

而且还有个非常优美的性质就是编号直接代表了节点，而且任何一个点所在的比赛都是可以分治的连续的区间。

那么我们一下就得到了状态$f[l][r][i]$表示编号在$[l,r]$的选手最终获胜者是$i$。

分治向上合并的时候只需要左右区间各枚举一个点即可。

然后我们发现内存炸了。

回到一开始的话，这是一颗完全二叉树，那么我们就多记了好多无用的$l,r$

唯一有用的$l,r$只用来表示当前分治的这一层的二叉树的区间，也就是说这一层枚举的获胜的$i$的区间是确定的。

那么我们的状态就可以改为$f[d][i]$表示在完全二叉树的深度为$d$，$i$获胜的概率，大力转移即可。

复杂度$O(n4^n)$

#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define kong putchar(' ')
#define huan putchar('\n')
#define bug puts("QWQ")
#define pr putchar
const int big=0x7fffffff;
using namespace std;
inline void read(int &x)
{
    x=0;char ch=getchar();int pd=1;
    while(ch<'0'||ch>'9'){if(ch=='-')pd=-pd;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    x*=pd;
}
inline void write(const int &x)
{
    char ggg[100];int s=0;int tmp=x;
    if(tmp==0){putchar('0');return;}
    if(tmp<0){tmp=-tmp;putchar('-');}
    while(tmp>0){ggg[s++]=tmp%10+'0';tmp/=10;}
    while(s>0){putchar(ggg[--s]);}
}
inline void wrs(const int &x)
{
	write(x);
	putchar(' ');
}

inline void wrl(const int &x)
{
	write(x);
	putchar('\n');
}

const int N=(1<<10)+1;
double f[11][N];
int n;
double p[N][N];

void merge(int l,int r,int d)
{
	if(l==r)
	{
		f[d][l]=1;
		return;
	}
	int mid=(l+r)>>1;
	merge(l,mid,d+1);
	merge(mid+1,r,d+1);
	for(register int i=l;i<=mid;++i)
	{
		for(register int j=mid+1;j<=r;++j)
		{
			f[d][i]+=(f[d+1][i]*f[d+1][j])*p[i][j];
			f[d][j]+=(f[d+1][i]*f[d+1][j])*p[j][i];
		}
	}
}

int main()
{
	read(n);
	n=1<<n;
	int x;
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=n;++j)
		{
			read(x);
			p[i][j]=x/100.0;
		}
	}
	merge(1,n,1);
	int k=0;
	for(register int i=1;i<=n;++i)
	{
		if(f[1][i]>f[1][k])k=i;
	}
	cout<<k<<endl;
}