我要妹子。

jun头吉吉 · 2023-05-30 16:14:35 · 题解

题意

给定 n，长度为 n 的序列 \{a_i\} 和 \{op_i\}，其中 a_i=2^{c_i}，\{op_i\} 由 x 个与(&)，y 个或(|)，z 个异或(^)组成，现在 x_0=0,x_i=x_{i-1}\ op_i\ a_i，现在你需要重排 a 和 op 使得 x_n 最大，给出最大值并构造一组方案。

多测，0\le x,y,z\le 2^{16},\sum n\le 2^{20}。

题解

我的做法好麻烦不知道有没有高论喵。

设 buc_i 表示序列 \{c_i\} 中 i 出现的次数，c 表示 buc_i>0 的 i 的个数，cc 表示 buc_i>1 的个数，mn 表示最小的 buc_i>0 的 i。

首先如果 x=0，那么不存在与操作，一位如果希望是 1，要么 buc_i 是奇数，否则就需要用掉至少一次或操作。从高位往低位做，优先保证高位是一即可。

然后如果 y+z<c，那么最多只有 y+z 位能够是 1，取高 y+z 位即可。

否则我们有一种除了 mn 位其他所有出现的位都是 1 的策略就是先与 2^{mn}，然后剩下的所有位再与操作之后或/异或一次，剩下的操作全部丢到与 2^{mn} 之前即可。

所以我们现在的目标是判断能否全部出现的位都是 1。

一个最简单的情况是 x\ge 2,cc\ge 2，因为我们可以连续与两个不同的数把所有位清零，之后就所有位都或/异或一次，剩下的操作丢到两次与之前即可。

否则的话我们可以断言，每次与操作后面跟着的数都是相同的，假设是 2^i。因为我们需要保证第 i 位为一，所以首先要有 buc_i>x，然后我们的构造方案还是类似的，仍然是其他位在之后或/异或一次（优先选择异或），那么如果 y\ne 0，那么对于 2^i 肯定可以被或一下，因此肯定可行。否则只有与和异或操作，那么一个条件就是 buc_i-x 是奇数，那么这位肯定是 1，否则就是不行。

然后只要模拟一下就行了叭。

代码

int T,n,x,y,z,c,cc,a[N],buc[N];
#define _(X,a,b) op##X.pb(a),nums##X.pb(b),buc[b]--,(a=='&'?x:a=='|'?y:z)--
#define AA(i) _(A,'&',i)
#define AO(i) _(A,'|',i)
#define AX(i) _(A,'^',i)
#define BA(i) _(B,'&',i)
#define BO(i) _(B,'|',i)
#define BX(i) _(B,'^',i)
#define rev(X) reverse((X).begin(),(X).end())
signed main(){
    read(T);for(int testcase=1;testcase<=T;testcase++){
        read(n,x,y,z);for(int i=0;i<n;i++)buc[i]=0;
        for(int i=1;i<=n;i++)read(a[i]),buc[a[i]]++;
        vector<int>opA,numsA,opB,numsB;
        if(x==0){
            for(int i=n-1;~i;i--)if(buc[i]){
                if(buc[i]%2||y){
                    pc('1');int _=buc[i]%2?0:1;
                    while(buc[i]>_&&z)AX(i);
                    while(buc[i])AO(i);
                }else{pc('0');while(buc[i])AX(i);}
            }else pc('0');
            goto end;
        }else{
            c=cc=0;for(int i=0;i<n;i++)c+=buc[i]>0,cc+=buc[i]>1;
            if(y+z<c){
                for(int i=n-1;~i;i--)if(buc[i]&&(y||z)){
                    pc('1');if(y)BO(i);else BX(i);
                }else pc('0');
                goto end;
            }
            if(x>=2&&cc>=2){
                for(int i=0;i<n;i++)if(buc[i]>1)for(int j=i+1;j<n;j++)if(buc[j]>1){
                    BA(i);BA(j);
                    for(int k=n-1;~k;k--)if(buc[k]){
                        pc('1');if(y)BO(k);else BX(k);
                    }else pc('0');
                    goto end;
                }
            }
            for(int i=0;i<n;i++)if(buc[i]>x&&(y||(buc[i]-x)%2)){
                for(int j=n-1;~j;j--)if(buc[j]){
                    pc('1');if(i!=j){if(z)BX(j);else BO(j);}
                }else pc('0');
                if(y){BA(i);rev(opB);rev(numsB);BO(i);}
                else{while(x)BA(i);rev(opB);rev(numsB);while(buc[i])BX(i);}
                goto end;
            }
            for(int mn=0;mn<n;mn++)if(buc[mn]){
                for(int j=n-1;~j;j--)pc('0'+(buc[j]&&j!=mn));
                BA(mn);
                for(int j=0;j<n;j++)if(buc[j]&&j!=mn){if(y)BO(j);else BX(j);}
                goto end;
            }
        }
        end:pc('\n');
        for(int i=0;i<n;i++)while(buc[i]){if(x)AA(i);else if(y)AO(i);else AX(i);}
        for(uint i=0;i<opA.size();i++)pc(opA[i]);
        for(uint i=0;i<opB.size();i++)pc(opB[i]);
        pc('\n');
        for(uint i=0;i<numsA.size();i++)write(numsA[i]),pc(' ');
        for(uint i=0;i<numsB.size();i++)write(numsB[i]),pc(' ');
        pc('\n');
    }
}