题解：P17227 [Math×Girl²] まよいづき

· · 题解

挖吧会证明，只能说说我咋做的了呜呜呜。

首先你发现 n=1 的时候只能取到重的那个，n=2 只能取到次重那个，后面不会算了。

我们尝试一个答案下界，我们猜测每轮扔掉最轻的那个和最重的那些，轻的可以足够轻，于是我们得到答案不小于 2^n-n，交一发就过了 5 分，很好。

接下来，我们把我们上面的构造坐下来，每次保留形如一个区间，做完之后算出来最轻的那个最重是啥，我们此处允许负数，最后再加即可，我们观察到为了让这个人轻被影响小，于是重的那边尽量轻，于是我们要求对于 i<2^n-n，m_i=m_{i+1}+1。可以过掉 40 分，容易看出我们答案是 O(2^{2n}) 量级的，而且根据评分标准，我们两级应该是对的。

然后我们思考一下还能怎么卡，我们发现我们每次如果轻的那个和最轻的几个 2^n-n 以前编号的保留的点扔掉，而不是最重的，似乎统计答案可以少算很多，但是此时后面不是单调降的，需要取 \min，尝试后可以获得 74 分。

我们思考一下这个值具体是什么？

实际上我们只关心下一轮物品总和，我们设 m_{2^n-n}=0，对于 i<2^n-n，m_i=m_{i+1}+1。

于是每一轮物品总和类似一个负数，是后一轮物品总和的两倍减一。最后物品总和是 0。前提是取 \min 的时候没影响到我。

我这个最轻物品重量就是物品总和减去重的那些物品，我们希望最后一轮这个值大一点。

我们考虑为啥会发生不单调降。

容易看出物品总和是 -O(2^n) 的，实际上可以暂时忽略。

而减去的重量是 O(2^{2n})，这是关键。

考虑每一轮找重物品个数是前一轮一半。

我们考虑 74 的那个构造，我们设第一轮拿 2B 个重物品，物品和是 \frac{(1+2B)\times2B}{2}=O(2B^2)。

第二轮拿的物品少一半，就是 \frac{(2B+3B)\times B}{2}=O(2.5B^2)，第三轮则是 O(1.625B)，之后都降下去了。

于是前两轮很难受。

我们发现可以把这两轮平均一下，我们无法做到更优秀，即使只考虑这两轮，平均下来是 O(2.25B^2)，仍然比第三轮优秀，所以不用管后面。

于是平均一下，发现过了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int m[2000009];
int t[2000009];
int n;
int f[2000009];
int g[2000009];
int w[29];
void did(int x){
    int r;
    r=(1ll<<(n-x+1))-(n-x+1)-1;
    if(r+n-x+2==4){
        t[f[r]]=t[(1ll<<n)-x+1]=x;
        t[(1ll<<n)-n+1]=x+1;
        t[(1ll<<n)-n]=0;
        m[(1ll<<n)-n+1]=-1;
        m[(1ll<<n)-x+1]=-m[f[r]]-2;
        return;
    }
    int rr;
    rr=(1<<(n-x))-(n-x+1);
    t[(1ll<<n)-x+1]=x;
    if(n>=4&&x==1){
        int rrr;
        rrr=(1ll<<(n-x-1))-(n-x);
        int S,T;
        S=T=0;
        for(int i=rrr+1;i<=rr;i++){
            T+=m[f[i]];
        }
        for(int i=rr+1;i<=r;i++){
            S+=m[f[i]];
        }
        int zz1,zz2;
        zz1=rrr+1,zz2=r;
        S-=T;
        while(w[3]>S){
            if(S+2*(zz2-zz1)<w[3]){
                S+=2*(zz2-zz1);
                swap(f[zz1],f[zz2]);
                ++zz1,--zz2;
                continue;
            }
            while(zz1+1<=rr&&S+2*(zz2-zz1-1)>=w[3]){
                ++zz1;
            }
            while(zz2-1>rr&&S+2*(zz2-zz1-1)>=w[3]){
                --zz2;
            }
            swap(f[zz1],f[zz2]);
            break;
        }

    }
    for(int i=rr+1;i<=r;i++){
        t[f[i]]=x;
    }
    did(x+1);
    int sum;
    sum=-1;
    for(int i=1;i<=rr;i++){
        sum+=m[f[i]];
    }
    for(int i=(1ll<<n)-n;i<=(1ll<<n)-x;i++){
        sum+=m[i];
    }
    for(int i=rr+1;i<=r;i++){
        sum-=m[f[i]];
    }
    m[(1ll<<n)-x+1]=min(sum,m[(1ll<<n)-x]-1);
}
void _main(){
    cin>>n;
    cout<<(1ll<<n)-n<<endl;
    m[(1ll<<n)-n]=0;
    for(int i=(1ll<<n)-n-1;i>=1;i--){
        m[i]=m[i+1]+1;
    }
    for(int i=1;i<=(1ll<<n)-n-1;i++){
        f[i]=i;
    }
    w[n]=-1;
    for(int i=n-1;i>=1;i--){
        w[i]=w[i+1]*2-1; 
    }
    //w[3]<=S-T
    if(n>1)
    did(1);
    else
    t[1]=0,t[2]=1,m[1]=0,m[2]=-1;
    for(int i=1;i<=(1ll<<n);i++){
        cout<<m[i]-m[(1ll<<n)]+1<<" ";
    }
    cout<<endl;
    for(int i=1;i<=(1ll<<n);i++){
        cout<<t[i]<<" ";
    }
    cout<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        _main();
    }
    return 0;
}