CF1630A题解
FiraCode
·
·
题解
题解思路：
有一个很显然的性质：
所以我们可一构造出 $k=0$ 时的情况。
当$k \ne n-1$ 的时候：
> 我们就可以让 $k$ 和 $n - 1$ 组成一组。
> 再让 $n - k + 1$ 和 $0$ 构成一组
接下来就是 $k = n-1$ 的情况：
若 $k=n-1$，那我们就不能 $n - 1$ 和 $n - 1$，$0$ 和 $0$ 分成一组。
因为要 $n\ge 4$，即二进制至少有两位。
$(0)_{10} = (0)_{2}$，
$(1)_{10} = (1)_{2}$，
$(2)_{10} = (10)_{2}$，
$(3)_{10} = (11)_{2}$。
$(n - 4)_{10} = ((??????...-1)11)_{2}$、
$(n - 3)_{10} = (?????...00)_{2}$、
$(n - 2)_{10} = (?????...01)_{2}$、
$(n - 1)_{10} = (?????...10)_{2}$、
$(n)_{10} = (??????... 11)_{2}$。
>那么我们可以 $n - 2$ 和 $3$。
>$n - 4$ 和 $1$。
>$n - 1$ 和 $n - 3$。
>$2$ 和 $0$。
特殊情况 $n = 4 , k = 3$ 时构造不出来，输出 $-1$，其他情况都有解，把这种情况特判掉就可以了。
## AC CODE:
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1 << 20;
int a[N];
int main() {
int T;
scanf ("%d" , &T);
while (T --) {
int n , k;
scanf ("%d%d" , &n , &k);
if (n == 4 && k == 2)puts("-1");//无解情况
else if (k == 0) {//k=0时
for (int i = 0; i < n / 2; ++ i)
printf ("%d %d\n" , i , n - 1 - i);
}else if (k != n -1) {//k!=n-1时
printf ("%d %d\n" , n - 1 , k);
printf ("%d %d\n" , n - 1 - k , 0);
for (int i = 1; i < n / 2; ++ i)
if (i != k && i != n - 1 - k)
printf ("%d %d\n" , i , n - 1 - i);
}else {//k=n-1的情况
printf ("%d %d\n" , n - 2 , 3);
printf ("%d %d\n" , n - 4 , 1);
printf ("%d %d\n" , n - 1 , n - 3);
printf ("%d %d\n" , 2 , 0);
for (int i = 4; i < n / 2; ++ i)
printf ("%d %d\n" , i , n - i - 1);
}
}
return 0;
}
```