考构造 = 考怎么构造 + 满足构造的条件
思路提示：想到 2 分形就是 $\text {lowbit}$
ZOJ 4063 Tournament
题目描述
给你一个矩阵，你需要构造满足以下条件：
- 对于任意 4 个人 $a, b, c, d$ ，你需要让他们交叉进行比赛（第 $x$ 轮是 $a \Leftrightarrow b, c \Leftrightarrow d$ ，存在第 $y \neq x$ 轮是 $a \Leftrightarrow c, b \Leftrightarrow d$）
题解
通过手绘发现，矩阵是具有高度分形性质的
通过下图可以看到
左上角可以复制 2 * 2 得到整个图。
仔细构造规律可以发现， $x$ 行至多能输出 $\text{lowbit} - 1$ 列
下次还是要注意一下的。。
AC Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| #include <bits/stdc++.h> using namespace std; int A[1009], n; void swwp(int x) { ++ x; x = 1 << x; for(register int i = 0; i < n; ++ i) if(i % x < (x >> 1)) { swap(A[i], A[x - i % x - 1 + i / x * x]); } } void swp(int x) { int cnt = 0; while(x) { if(x & 1) { swwp(cnt); break; } ++ cnt; x >>= 1; } } int lowbit(int x){return x & -x;} int main() { int T, m, lim; scanf("%d", &T); while(T --) { scanf("%d %d", &n, &m); lim = lowbit(n); if(lim <= m) { puts("Impossible"); continue; } for(register int i = 0; i < n; ++ i) A[i] = i + 1; for(register int i = 1; i <= m; ++ i) { swp(i); for(register int k = 0; k < n; ++ k) printf("%d%c", A[k], k == n - 1 ? '\n' : ' '); } } return 0; }
|
