And Matching
C++ 代码
/*
当 k = 0 时,只需要按照 (i, n - i - 1) 进行构造即可,可以发现每对数的 0 和 1 刚好互补
当 k <= n - 1 时,我们试图将一对数的结果变成 k,然后其他所有数对结果都是 0,由于 n - 1
的前 logn 位都是 1,所以 (k, n - 1) 的结果就是 k,然后我们沿用 k = 0 时的构造,可以发现
其他数对都没有影响,只是 (0, n - 1) 和 (k, n - k - 1) 被拆开了,此时可以发现 (0, n - k - 1)
的结果也是 0,因此我们就构造出了新的方案,但是由于我们没法令某个数对的结果是 n - 1,因此
当前的构造方案只适用于 k < n - 1 时
当 k == n - 1 时,我们无法令数对的结果是 n - 1,那么我们就尝试令一个数对的结果是 n - 2,然后
再令一个数对的结果是 1,这样也能凑出 n - 1,而 (n - 2, n - 1) 的结果是 n - 2,(1, n - 3) 的
结果是 1,这两个数对能够凑出 n - 1,剩下的数对我们依旧沿用 k = 0 时的构造,可以发现此时落单的
数有 0 和 2,而 (0, 2) 的结果也是 0,这样就又得到了新的方案。
综上所述,我们将 k 的所有情况都构造出了合理的方案
*/
#include <iostream>
#include <cstring>
using namespace std;
void work()
{
int n, k;
scanf("%d%d", &n, &k);
if(n == 4 && k == 3)
{
puts("-1");
return;
}
if(k == 0)
{
for(int i = 0; i <= (n - 1) / 2; i++) printf("%d %d\n", i, n - i - 1);
return;
}
if(k < n - 1)
{
printf("%d %d\n", k, n - 1);
printf("%d %d\n", 0, n - k - 1);
for(int i = 0; i <= (n - 1) / 2; i++)
if(i != 0 && i != k && i != (n - k - 1))
printf("%d %d\n", i, n - i - 1);
}
if(k == n - 1)
{
printf("%d %d\n", n - 1, n - 2);
printf("%d %d\n", 1, n - 3);
printf("%d %d\n", 0, 2);
for(int i = 0; i <= (n - 1) / 2; i++)
if(i != 0 && i != 1 && i != 2 && i != n - 2 && i != n - 3)
printf("%d %d\n", i, n - i - 1);
}
}
int main()
{
int T;
scanf("%d", &T);
while(T--) work();
return 0;
}