[C++知识库]Codeforces Round#768(Div.2) C. And Matching

题意：

给定一个值n，表示数组为[0-n-1]，其中n一定是2的整数幂，将数字两两配对分别为a[i]，b[i]，使得$\sum a_i\&b_i=k$,

题解：

1.直接构造出一个答案为k，使得剩下的组合都为0即可。
我们知道:

1. n-1&k=k
2. 设c（k）为k的补码, k&c(k)=0

再分情况讨论：
Case 0<=k<n?1:
在这种情况下，可以将除 0、k、c(k) 和 n-1 之外的每个元素与其补码配对，然后将 0 与 c(k) 和 k 与 n-1 配对，0&c(k)=0 和k&(n-1)=k。
Case k=n?1:
n=4 则没有解决方案，如果 n≥8 则可以通过以下方式构造答案：
(n?1)&(n?2)=n?2,
(n?3)&1=1,
0&2=0
剩下的数则按照补码来组合x&c(x)=0
(n?2)+1+0+0+…+0=n?1.

#include<bits/stdc++.h>
using namespace std;
int n, t, k, x[1000005];
int main() {
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &n, &k);
		for (int i = 0; i < n; i++) x[i] = i;
		if (k != n - 1) swap(x[k], x[0]);
		else swap(x[n - 2], x[0]), swap(x[1], x[n - 4]);
		if (n == 4 && k == 3) printf("-1\n");
		else
		{
			for (int i = 0; i < n / 2; i++) printf("%d %d\n", x[i], x[n - i- 1]);
		}
	}
}