P11313 [RMI 2021] 园艺 / Gardening 题解

思路分析：

观察样例发现，样例中只有两种填充方式，

2\times2

的矩形，或者矩形的外框。那我们何不大胆猜想：仅靠这两种填充方式就可以得出所有合法状态。

事实上是对的。非中空的情况，显然只有

2\times2

的矩形是合法的；而中空的情况，可以通过割补和微调变为矩形。本质就是，合法的构造方式中存在一种只用到这两种填充方式的方案。

那么我们考虑递归求解。对于当前一个矩形，我们可以：

剥去外层一圈。
竖向分割。
横向分割。

对于分割的情况，我们没有必要枚举分割点，我们每次割掉

2

行/列就可以得到所有情况。同时，考虑到割掉的越少直觉上可能性更多，于是我们可以直接选择更短的边割掉。

接下来是如何判断一个矩形能否由

k

种颜色涂满。

首先 $n$ 和 $m$ 都必须是偶数，奇数一定无解。
其次最大的 $k$ 为全都由 $2\times2$ 的矩形组成，即 $k$ 不能多于 $r=\dfrac{n\times m}{4}$ 。
其次最小的 $k$ 为一层一层的回字形，即 $k$ 不能少于 $l=\dfrac{\max(n,m)}{2}$ ，最小值当 $n=m$ 时容易取得。
如果 $k=r-1$ ，发现无论如何无法合并两个色块，故无解。
若 $k=l+1$ ，发现当 $n=m$ 时不可能将一个环拆成两个色块，故无解。

AC Code:

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,c,ans[N];
#define id(i,j) (i)*(m+1)+j
bool chk(int x,int y,int k){
	int l=max(x,y)/2,r=x*y/4;
	return k>=l&&r>=k&&(k!=l+1||x!=y)&&k!=r-1;
}
void dfs(int lx,int ly,int rx,int ry,int k){
	if(!k)return;
	if(chk(rx-lx-1,ry-ly-1,k-1)){
		c++;
		for(int i=ly;i<=ry;i++)ans[id(lx,i)]=ans[id(rx,i)]=c;
		for(int i=lx;i<=rx;i++)ans[id(i,ly)]=ans[id(i,ry)]=c;
		dfs(lx+1,ly+1,rx-1,ry-1,k-1);
	}else if(rx-lx>ry-ly){
		for(int i=ly;i<=ry;i+=2)
			ans[id(lx,i)]=ans[id(lx,i+1)]=ans[id(lx+1,i)]=ans[id(lx+1,i+1)]=++c;
		dfs(lx+2,ly,rx,ry,k-(ry-ly+1)/2);
	}else{
		for(int i=lx;i<=rx;i+=2)
			ans[id(i,ly)]=ans[id(i+1,ly)]=ans[id(i,ly+1)]=ans[id(i+1,ly+1)]=++c;
		dfs(lx,ly+2,rx,ry,k-(rx-lx+1)/2);
	}
}
void solve(){
	int k;cin>>n>>m>>k,c=0;
	if(n%2==1||m%2==1||!chk(n,m,k))
		return cout<<"NO\n",void();
	cout<<"YES\n";
	dfs(1,1,n,m,k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cout<<ans[id(i,j)]<<" \n"[j==m];
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;while(T--)solve();
	return 0;
}

完结撒花！！！

P11313 [RMI 2021] 园艺 / Gardening 题解

文章操作

思路分析：

AC Code:

相关推荐

评论

P11313 [RMI 2021] 园艺 / Gardening 题解