题解：CF1310B Double Elimination

· · 题解

CF1310B Double Elimination

思路

不难想到可以把双败淘汰制理解为一个完全二叉树，所以对于每场比赛，都可以用完全二叉树编号的形式给他编号。

贪心极其困难，所以我们考虑 dp，观察发现我们并不注意具体哪个人赢了，而是只关心赢或输的这个人是否是他喜欢的队伍，所以我们不妨设 dp_{u,i,j} 表示进行到了第 u 场比赛，且第 u 场比赛的胜者是否是他喜欢的球队，即 i=1 时是他喜欢的球队，i=0 时不是他喜欢的球队，以及第 u 场的败者是否是他喜欢的球队，即 j=1 时是他喜欢的球队，j=0 时不是他喜欢的球队。

所以转移我们只考虑第 u \times 2 与 第 u \times 2 +1 场的状态即可。具体参考代码理解。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&(-x))
#define ls (u<<1)
#define rs (u<<1|1)
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
int read(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') k=k*10+c-'0',c=getchar();
    return k*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
const int N=20;
bool pos[1<<N];
int dp[1<<N][2][2];
void solve(){
    int n=read(),k=read();
    for (int i=1;i<=k;i++) pos[read()-1]=1;
    memset(dp,-0x3f,sizeof(dp));
    int tot=1<<(n-1);
    for (int i=0;i<(1<<n);i+=2){
        dp[tot+i/2][pos[i]][pos[i+1]]=pos[i]|pos[i+1];
        dp[tot+i/2][pos[i+1]][pos[i]]=pos[i]|pos[i+1];
    }
    for (int u=tot-1;u>=1;u--){
        int l=u<<1,r=u<<1|1;
        for (int a=0;a<2;a++){
            for (int b=0;b<2;b++){
                for (int c=0;c<2;c++){
                    for (int d=0;d<2;d++){
                        // a左胜,b左败,c右胜,d右败
                        if (dp[l][a][b]<0 || dp[r][c][d]<0) continue;
                        int sum=dp[l][a][b]+dp[r][c][d];
                        dp[u][a][b|c]=max(dp[u][a][b|c],sum+(a|c)+(b|c)+(b|d));
                        dp[u][a][d|c]=max(dp[u][a][d|c],sum+(a|c)+(d|c)+(b|d));
                        dp[u][c][b|a]=max(dp[u][c][b|a],sum+(b|a)+(a|c)+(b|d));
                        dp[u][c][d|a]=max(dp[u][c][d|a],sum+(d|a)+(a|c)+(b|d));
                    }
                }
            }
        }
    }
    int ans=0;
    for (int i=0;i<2;i++){
        for (int j=0;j<2;j++) ans=max(ans,dp[1][i][j]+(i|j));
    }
    write(ans);
}
signed main(){
    int T=1;
    while (T--) solve();
    return 0;
}