P9890 [ICPC2018 Qingdao R] Tournament
题目传送门
更好的阅读体验
一道找规律的思维题。
前置知识 \(lowbit\)
\(lowbit\) 是指获取一个二进制数中最右边的 \(1\) 所对应的数值。
具体地， \(lowbit\) 可以通过对一个数取反然后加 \(1\) ，再与原数进行按位与的方式来实现。
int lowbit(int x) {return x&-x;
}
例子：对于 \((11010)_2\) （十进制下为 \(26\) ）来说，它的 \(lowbit\) 为 \((10)_2\) （十进制下为 \(2\) ），即 \(lowbit(26)=2\) 。
Solve
其实题意说得已经非常清楚了，我们可以将骑士分成二幂次组，构造打出循环赛日程表，通过找规律不难发现最多进行 \(lowbit(n)-1\) 场比赛，最后依次输出即可。
And 至于为什么最多进行 \(lowbit(n)-1\) 场比赛，我想到了一段不严格的文字证明：在比赛中，每场比赛都会消除掉一个骑士，所以在给定人数为 \(n\) 时，总的比赛次数就是将骑士数缩减为 \(1\) 的过程。最多的比赛发生在每轮都尽可能减少最少人数的情况下，即每次比赛中淘汰 \(lowbit(n)\) 个骑士。因此，总的比赛次数为 \(lowbit(n) - 1\)。
Code
#include <bits/stdc++.h>
#define N 2005int A[N][N];
int T,n,k;int lowbit(int x) {return x & -x;
}int main() {A[1][1]=1;for(int k = 1; k < 1024; k *= 2) {for(int i = 1; i <= k; i++) {for(int j = 1; j <= k; j++) {A[i + k][j + k] = A[i][j];A[i][j + k]=A[i + k][j] = A[i][j] + k;}}}std::cin>>T;while(T--) {std::cin>>n>>k;if(k > lowbit(n) - 1) {std::cout<<"Impossible";puts("");continue;}for(int i = 2; i <= k + 1; i++) {for(int j = 1; j <= n; j++) {std::cout<<A[i][j]<<" ";}puts("");}}return 0;
}
over~
