自动搬运

查看原文

来自洛谷，原作者为

	C_S_L 。，

搬运于2025-08-24 22:33:58，当前版本为作者最后更新于2021-10-05 11:38:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑如何染色。

我们先把每种颜色依次一行一行染下去，如下图（以样例 $1$ 的第 $3$ 个数据为例）：

此时，$2,5,8$ 三个数字是不联通的。

我们要在保证其他数字仍然联通的情况下使得这三个数字联通。

我们可以使用另一种染色方式：奇数行从前往后染，偶数行从后往前染。这样，若某个数字在同一行里，那么一定联通，若不在一行里，也一定联通，因为相邻两行中的这个数字联通。

如图：

注意特判不可行的情况，即 $k\nmid nm$ 。

于是，我们以 $\Theta(\sum nm)$ 的时间复杂度解决了此题。

代码：

#include<bits/stdc++.h>
using namespace std;
int T,n,m,k,a[10000][10000];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&k);
		if(n*m%k!=0){
			printf("NO\n");
			continue;
		}
		printf("YES\n");
		int cnt=k-1;
		for(int i=1;i<=n;++i){
			if(i%2==1){
				for(int j=1;j<=m;++j){
					a[i][j]=(++cnt)/k;
				}
			}
			else{
				for(int j=m;j>=1;--j){
					a[i][j]=(++cnt)/k;
				}
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				printf("%d ",a[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}