CF768C题解
8atemak1r
·
·
题解
Description
## Solution
首先给出这道题中用到的十分重要的几个性质：
1. `i & (n - i - 1) = 0`
这个性质十分好证，将 $i$ 以及 $n - i - 1$ 的二进制写出来你就会发现他们的 $0$ 和 $1$ 是“插空站”的，或者反过来想，当你有这样的两个 $n$ 位二进制数，你将他们相加时每一位都会进位，最后得到的结果自然是 $2^n$，而且我们发现，$i$ 和 $n - i - 1$ 是关于 $\frac{n}{2}$ 对称的。
2. `(n - 1) & k = k`
这个性质也十分好证，易得 $n - 1$ 的二进制表示为连续的 $\log_{2}{n}$ 个 $1$， 它和任何数做位运算与自然是这个数本身了。
3. `0 & p = p`
证明略。
那如何将这个性质运用在这道题当中呢？
首先，当 $k < n - 1$，我们将 $k$ 与 $n - 1$ 配成一对，由性质 $2$ 得这一对数字对答案的贡献恰好为 $k$，再将 $n - k - 1$ 和 $0$ 配成一对，由性质 $3$ 得这一对数字对答案的贡献为 $0$。接下来，我们只需要使剩下的数对对答案的贡献均为 $0$ 就可以了，这不是有性质 $1$ 吗？枚举剩下的数字并输出相应的数对就可以了。
接下来是当 $k = n - 1$ 的情况。~~由样例得~~我们自己手推了一下发现，当 $n = 2$ 和 $n = 4$ 找不出合法的分法，接下来思考 $n > 4$ 的情况。我们可以把 $0$ 至 $n - 1$ 的二进制表示列出来，如下表：
[](https://imgtu.com/i/HZYqs0)
由性质 $2$ 结合表格可得，`(n - 1) & (n - 2) = n - 2` ，这时候还剩下一个最低位的 $0$ 要补上，正好，$n - 3$ 的最低位是 $1$，$1$ 只有最低位是 $1$， 于是易得 `(n - 3) & 1 = 1` ，这下把 $k$ 凑齐了，而根据性质 $1$ 中的“对称性”可得，我们需要把 $0$ 和 $2$ 凑成一对，剩下的数只需要由性质 $1$ 输出对应数对就好了。
## Code
```cpp
#include<iostream>
using namespace std;
int t, n, k;
int main() {
cin >> t;
while(t --) {
cin >> n >> k;
if(k == n - 1) {
if(k <= 4) {
cout << "-1\n";
continue;
}
cout << 1 << ' ' << n - 3 << '\n';
cout << n - 1 << ' ' << n - 2 << '\n';
cout << "0 2\n";
for(int i = 3; i < (n >> 1); ++ i) cout << i << ' ' << n - i - 1 << '\n';
continue;
}
cout << k << ' ' << n - 1 << '\n';
if(k != 0) cout << "0 " << n - k - 1 << '\n';
for(int i = 1; i < (n >> 1); ++ i) {
if(i == k || i == n - k - 1) continue;
cout << i << ' ' << n - i - 1 << '\n';
}
}
return 0;
}
```