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

本文主要是介绍Codeforces 1631 C. And Matching ——构造，一点想法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

你现在有0~n-1( $n=2^x(2<=x<=16)$ )这些数，你要将其组成a和b数组，a和b数组的长度都为n/2.并且满足： $\sum\limits_{i=1}^{\frac{n}{2}}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<bits/stdc++.h>
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("-1\n");else{printf("%d %d\n%d %d\n%d %d\n",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 %d\n",i,n^i);}}continue;}printf("%d %d\n",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 %d\n",i,res);vis[res]=1;}}return 0;
}