P9890 [ICPC2018 Qingdao R] Tournament 题解

XueRuhao's Blog / 2024-11-07 / 原文

P9890 [ICPC2018 Qingdao R] Tournament

题目传送门

更好的阅读体验

一道找规律的思维题。

前置知识 lowbit

lowbit 是指获取一个二进制数中最右边的 $1$ 所对应的数值。

具体地，lowbit 可以通过对一个数取反然后加 $1$，再与原数进行按位与的方式来实现。

int lowbit(int x) {
	return x&-x;
}

例子：对于 $(11010)_2$（十进制下为 $26$）来说，它的 lowbit 为 $(10)_2$（十进制下为 $2$），即 $\operatorname{lowbit}(26)=2$。

Solve

其实题意说得已经非常清楚了，我们可以将骑士分成二幂次组，构造打出循环赛日程表，通过找规律不难发现最多进行 $\operatorname{lowbit}(n)-1$ 场比赛，最后依次输出即可。

And 至于为什么最多进行 $\operatorname{lowbit}(n)-1$ 场比赛，我想到了一段不严格的文字证明：在比赛中，每场比赛都会消除掉一个骑士，所以在给定人数为 $n$ 时，总的比赛次数就是将骑士数缩减为 $1$ 的过程。最多的比赛发生在每轮都尽可能减少最少人数的情况下，即每次比赛中淘汰 lowbit(n) 个骑士。因此，总的比赛次数为 $\operatorname{lowbit}(n) - 1$。

Code

#include <bits/stdc++.h>
#define N 2005

int 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~