Codeforces 1631 C. And Matching ——构造，一点想法

This way

你现在有0~n-1( n = 2 x ( 2 < = x < = 16 ) n=2^x(2<=x<=16) n=2x(2<=x<=16))这些数，你要将其组成a和b数组，a和b数组的长度都为n/2.并且满足： ∑ i = 1 n 2 a [ i ] & b [ i ] = k sumlimits_{i=1}^{frac{n}{2}}a[i]&b[i]=k i=1∑2n​​a[i]&b[i]=k
问你这俩数组的任意一种构造方法。

以前就不擅长构造题，一回归给我整一个这个，真难受，代码也写的乱七八糟，是写到一半换想法或者抠细节。

假设mx=n-1=111…1B
那么a[i]&(a[i]^mx)可知为0.
也就是说我们可以构造b[i]=a[i]^mx，那么题中运算方法得到的结果为0.如果要得到k呢？
只需要将k和mx放到一对，0和mx^k放到一对即可。
如果k是mx呢，对于3的时候确实是无解的，但是对于更大的情况，可知：
mx&(mx-1)=mx-1
那么我们只需要想办法凑个1加上去就好了啊。
由于mx和mx-1一对了，那么0和1就被排挤在外，而且他们俩并不能凑成一对。
but，我们知道mx一定是一个奇数，所以mx-2也一定是一个奇数，所以1&(mx-2)=1.那么剩下的就是0和2，我们惊奇（不是）地发现，0&2=0。
所以这三对数打乱一下，其它的数还是保持原样即可。

#include
using namespace std;
const int N=1e5+5;
int vis[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n,k;
        scanf("%d%d",&n,&k);
        n--;
        memset(vis,0,sizeof(vis));
        if(k==n){
            if(n==3)printf("-1n");
            else{
                printf("%d %dn%d %dn%d %dn",n,n-1,n-2,1,0,2);
                for(int i=n-3;i>=3;i--){
                    if(vis[i])continue;
                    vis[n^i]=1;
                    printf("%d %dn",i,n^i);
                }

            }
            continue;
        }
        printf("%d %dn",k,n);
        vis[k]=vis[n]=1;
        int v=n+1;
        for(int i=n;i;i--){
            if(i==(v/2)-1)v>>=1;
            if(vis[i])continue;
            int res=(v-1)^i;
            if(vis[res])res=0;
            printf("%d %dn",i,res);
            vis[res]=1;
        }
    }
    return 0;
}