题解 P1769 【淘汰赛制_NOI导刊2010提高（01）】

两年打铁 · 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;
}