题解：AT_cf17_final_i Full Tournament

· · 题解

思路分析

考虑比赛的形态，我们可以将其画成一棵分治树，如图：

最上面那排的就是最后的 a 序列，即排名序列，而对于这个节点，它一定是从它的父节点 p 中每两个选一个最小/大的数组成的序列，就比如点 1536，它的左节点就是 13，右节点就是 56，而我们知道的是最后一层的答案，要反推上面是否有解，那么容易想到一种贪心策略就是左右节点最小的匹配，第二小的匹配，以此类推。

这个贪心转化到树上就是 u 的一个匹配对 (x_{2i},x_{2i+1}) 一定有 x_{2i}<x_{2i+1}，即左节点的 l_i 小于右节点的 r_i，把它映射到最初知道的 a 序列，我们就能推出其需要满足的条件：即 a_i< a_{i+2^j}(j\not\isin i)，感性理解就是你左右节点构造方式是相等的，所以你 l_i 和 r_i 对应到 a 中一定差了 2^j。

那么我们建出图然后套用这个题的解法即可。

时间复杂度为 \mathcal{O}(2^nn)，实现上不用显式建图。

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lli long long
#define db long double
#define ull unsigned long long
#define F(i,k,n) for (int i=(k);i<=(n);i++)
#define R(i,k,n) for (int i=k;i>=n;i--)
#define pu push_back
#define mpr make_pair
#define ins insert
#define lowb(x) (x&(-x))
#define mes(a,b) memset(a,b,sizeof a)
const int N=2e6+10;
const int inf=1e18;
const int mod=1e9+7;
struct node{
    int id,l,r;
}b[N];
int n;
int l[N],r[N];
int a[N],c[N]; 
set<int>s;
bool cmp(node a,node b){
    if (a.r!=b.r) return a.r<b.r;
    return a.l<b.l;
}
int rev(int x){
    int y=0;
    F(i,0,n-1){
        if ((x>>i)&1) y+=(1<<n-1-i);
    }
    return y;
}
signed main(){  
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    F(i,0,(1<<n)-1){
        cin>>a[i];
        if (a[i]) l[i]=r[i]=a[i];
        else l[i]=1,r[i]=(1<<n);
    }
    F(i,0,(1<<n)-1){
        F(j,0,n-1){
            if ((i>>j)&1){
                l[i]=max(l[i],l[i^(1<<j)]+1); 
            }
        }
    }
    R(i,(1<<n)-1,0){
        F(j,0,n-1){
            if (!((i>>j)&1)){
                r[i]=min(r[i],r[i^(1<<j)]-1);
            }
        }
    }
    bool p=1;
    F(i,0,(1<<n)) s.insert(i);
    F(i,0,(1<<n)-1) b[i+1]={i,l[i],r[i]};
//  F(i,0,(1<<n)-1) cout<<l[i]<<' '<<r[i]<<'\n';
    sort(b+1,b+1+(1<<n),cmp);
    F(i,1,(1<<n)){
        int x=*s.lower_bound(b[i].l);
        if (x>b[i].r){
            cout<<"NO";
            return 0;
        }
        c[b[i].id]=x;
        s.erase(x);
    }
    cout<<"YES\n";
    F(i,0,(1<<n)-1){
        cout<<c[rev(i)]<<' '; 
    }
    return 0;
}