题解：P11313 [RMI 2021] 园艺 / Gardening

MarSer020 · 2024-11-26 17:27:49 · 题解

抽象 Ad-hoc。

首先可以把题面转化为在 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 时无解。

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

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

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

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

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

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

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