本文主要是介绍Codeforces Round#768(Div.2) C. And Matching，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给定一个值n，表示数组为[0-n-1]，其中n一定是2的整数幂，将数字两两配对分别为a[i]，b[i]，使得 ∑ a i & b i = k \sum a_{i} \&b_{i}=k ∑ai&bi=k,
题解：
1.直接构造出一个答案为k，使得剩下的组合都为0即可。
我们知道:
- n-1&k=k
- 设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]);}}
}
这篇关于Codeforces Round#768(Div.2) C. And Matching的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
