P11313 [RMI 2021] 园艺 / Gardening 题解

Satellite_system · 2025-11-17 18:32:40 · 题解

思路分析：

观察样例发现，样例中只有两种填充方式，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:

#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;
}

完结撒花！！！