自动搬运

查看原文

来自洛谷，原作者为

	MarSer020 玩二游玩的

搬运于2025-08-24 23:06:21，当前版本为作者最后更新于2024-11-26 17:27:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

抽象 Ad-hoc。

$\Large\text{Solution}$

首先可以把题面转化为在 $n\times m$ 的网格图内画 $k$ 个 $2\times2$ 或 $i\times j(i,j\ge2)$ 的互不相交的环，容易用调整法证明若有解必然存在这样的解：

考虑左边的构造方法总能转化为右边的构造方法。

先手摸一下小数据，发现不存在这样的情况：

其中红色部分的长度是奇数。

这是好证明的，长为 $3$ 的显然不存在，其他情况归纳即可。可以得到对于任意一个环，其任意一边都是偶数。故环长必为 $4$ 的倍数。

由此我们发现：当 $n$ 或 $m$ 为奇数时，一定不存在解。

考虑进一步手玩：对 $n=6,m=6$ 和 $n=6,m=8$ 的情况进行手玩：

再手玩几组，发现：

• 当 $k<\frac{\max(n,m)}{2}$ 时无解。
• 当 $k>\frac{nm}{4}$ 时无解。
• 当 $k=\frac{nm}{4}-1$ 时无解。
• $n=m$ 时，当 $k=\frac{n}{2}+1$ 时无解。

具体的，可以看下面几张图：

可以写个暴力，发现这就是所有无解情况了，手摸也是容易证明的。由于我太菜了不会严谨证明，可以查看官解的证明。

考虑如何构造，发现有以下两种构造流派：

• 当 $k=\frac{nm}{4}$ 时，直接使用上面第二张图的构造，即用 $2\times2$ 的矩形铺满。
• 其他情况，从左上角开始选择一个长宽均为偶数的矩形，将外面的全部填 $2\times2$，这个矩形的边框填一种颜色，内部递归构造。

考虑直接枚举红色矩形的大小即可。时间复杂度 $O(\sum nm)$。

注意官方题解这里的分段疑似是错的，我自己手推出来是 $\frac{nm}{4}-\frac{n+m}{2}$ 之类的东西，不确定。

$\Large\text{Code}$

#include<bits/stdc++.h>
using namespace std;
int n,m,T,K;
vector<int>a[200005];
bool check(int n,int m,int K){
	return !(n&1||m&1||K>n*m/4||K<max(n,m)/2||K==n*m/4-1||(n==m&&K==n/2+1));
}
void solve(int n,int m,int K,int lx,int rx,int ly,int ry){
	if(K==n*m/4){
		for(int i=lx;i<rx;i+=2)
			for(int j=ly;j<ry;j+=2)
				a[i][j]=a[i+1][j]=a[i][j+1]=a[i+1][j+1]=K,K--;
		return;
	}
	else if(check(n-2,m-2,K-1)){
		for(int i=lx;i<=rx;i++)
			a[i][ly]=a[i][ry]=K;
		for(int i=ly;i<=ry;i++)
			a[lx][i]=a[rx][i]=K;
		solve(n-2,m-2,K-1,lx+1,rx-1,ly+1,ry-1);
	}
	else{
		for(int i=lx+2;i<rx;i+=2)
			for(int j=ly+2;j<ry;j+=2)
				if(check(i-lx,j-ly,K-(n*m-(i-lx+2)*(j-ly+2))/4-1)){
					for(int ii=lx;ii<=i;ii+=2)
						for(int jj=j+2;jj<ry;jj+=2)
							a[ii][jj]=a[ii+1][jj]=a[ii][jj+1]=a[ii+1][jj+1]=K,K--;
					for(int ii=i+2;ii<rx;ii+=2)
						for(int jj=ly;jj<ry;jj+=2)
							a[ii][jj]=a[ii+1][jj]=a[ii][jj+1]=a[ii+1][jj+1]=K,K--;
					for(int ii=lx;ii<=i+1;ii++)
						a[ii][ly]=a[ii][j+1]=K;
					for(int ii=ly;ii<=j+1;ii++)
						a[lx][ii]=a[i+1][ii]=K;
					solve(i-lx,j-ly,K-1,lx+1,i,ly+1,j);
					return;
				}
		assert(0);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cin>>T;
	while(T--){
		cin>>n>>m>>K;
		if(!check(n,m,K))
			cout<<"NO\n";
		else{
			for(int i=1;i<=n;i++)
				a[i].clear(),a[i].resize(m+1);
			cout<<"YES\n",solve(n,m,K,1,n,1,m);
			for(int i=1;i<=n;i++,cout<<'\n')
				for(int j=1;j<=m;j++)
					cout<<a[i][j]<<' ';
		}
	}
	return 0;
}