题目链接:https://codeforces.com/gym/104270/problem/F
题意:
有n个武士，编号1~n, 要进行k轮比赛，每轮比赛中所有武士都要出现，然后两名武士之间会发生决斗，并且一名武士在一轮比赛中只会与另外一名武士决斗，发生决斗的这两名武士，在其他轮比赛中，将不会再次决斗。
问能否构造出来符合题意的k轮比赛。
输入:
n, k分别表示武士的数目和比赛的轮数。
$ 1\leqslant n,k \leqslant 1000$
输出:
如果不可能构造出来符合题意的k轮比赛，输出"impossible"。
如果可以构造出来，输出k行，每行n个整数，对于第i行第j个数\(C_{ij}\)
其含义为，武士j将在第i轮与武士\(C_{ij}\)决斗。
如果有多种构造方法，输出字典序最小的。
Simple input:
2
3 1
4 3
Simple output:
Impossible
2 1 4 3
3 4 1 2
4 3 2 1
Solution:
要按字典序输出，很容易想到1， 2， 3， 4， 5 \(\dots\)n的情况。
但是每个武士不可能和自己决斗，可以两两交换变成2, 1, 4, 3\(\dots\)的情况。
然后列出来符合题意的字典序递增的几行：
1 2 3 4 5 6 7 8（这行是思维的起点，不合题意）
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
...
设1 2 3 4 5 6 7 8为第一行，行内每个元素分别是a[1][1]...a[1][n]可以发现
第二行是swap(a[1][1], a[1][2]), swap(a[1][3], a[1][4])...得到的
第三行是swap(a[2][1], a[2][4]), swap(a[2][2], a[2][3])...得到的
...
第五行是swap(a[4][1], a[4][8]), swap(a[4][2], a[4][7])...得到的
意思就是
直接看代码，更直观。
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int LL
int lowbit(int x) {
return x & (-x);
}
void solve(void) {
int n, k; cin >> n >> k;
if(k > lowbit(n) - 1) {
cout << "Impossible\n";
return;
}
int a[n + 1];
for(int i = 1; i <= n; i ++) a[i] = i;
for(int i = 1; i <= k; i ++) {
int len = lowbit(i);
for(int j = 1; j <= n; j += (len << 1)) {
for(int kk = 0; kk < len; kk ++) {
swap(a[j + kk], a[j + (len << 1) - kk - 1]);
}
}
for(int j = 1; j <= n; j ++) cout << a[j] << ' ';
cout << endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
while(t --) solve();
}