题解 AT3869 【[AGC021C] Tiling】

· · 题解

一道比较巧妙的构造题。

为了方便，下文用a表示1*2的方块,b表示2*1的方块。

首先可以考虑，若我们先放a再放b，放a时我们肯定尽量将两个a堆在一起，这样才不会浪费。对于b也同理。

如下图这样：

换句话说，我们会把棋盘分割成尽量多的2*2的矩形，每个矩形放两个a或两个b。

当然，当n或m为奇数时，我们会多出一行/列，多出的行只能放a，多出的列只能放b，我们直接放就好了。

如下图就是一种n=5,m=5,A=4,B=8的合法情况：

但是我们发现这种放法还是会WA 6个点，有什么问题呢？

当然是有问题的，例如n=3,m=3,A=2,B=2时，我们的程序会给出NO，但是实际上存在这一种情况：

我们发现这种情况并没有把a,b放在2*2的矩形内，这是否代表我们的思路有很大问题呢？（我打vp的时候就是以为有很大问题然后就跳了）

但我们可以发现，通过这种方法，我们能放的方块总数并没有变（即A+B的最大值并不会改变），我们能进行的最多只有A++,B--，或者A--,B++。

进一步探究可以发现，这种情况发生，当前仅当n,m都是奇数时，我们选择牺牲掉一个2*2的方格，并同时放上一个a,b，如下图：

(绿色表示我们划分出的，还未确定放什么的2*2空间)

这个图可以通过我们上述的操作变为：

在n为偶数或m为偶数时其实也可以进行上述变化，但是这样会使能放的方块总数减少，显然不能使原本不合法的情况合法。

判断这种情况，然后按照之前所述的方法放就可以了。

//W4P3R
#include<bits/stdc++.h>
#define inf 1e9
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register int
#define fr first
#define sd second
#define pa pair<int,int>
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define N 3010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
inline ll read()
{
    char ch=getchar();
    ll s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
inline int lowbit(int x){return x&(-x);}
int n,m,A,B;
int vis[N][N],flag;
inline void END()
{
    if(A||B)cout<<"NO\n";
    else 
    {
        cout<<"YES\n";
        FOR(i,1,n)
        {
            FOR(j,1,m)
            {
                if(vis[i][j]==0)cout<<'.';
                if(vis[i][j]==1)cout<<'<';
                if(vis[i][j]==2)cout<<'>';
                if(vis[i][j]==3)cout<<'^';
                if(vis[i][j]==4)cout<<'v';
            }
            cout<<'\n';
        }   
    }
}
int main()
{
    //ios::sync_with_stdio(false);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read(),m=read(),A=read(),B=read();

    if(n&1)for(re j=1;j<m&&A;j+=2){vis[n][j]=1;vis[n][j+1]=2;A--;}
    if(m&1)for(re j=(n&1)?2:1/*方便进行变换*/;j<n&&B;j+=2){vis[j][m]=3;vis[j+1][m]=4;B--;}
    if(n==1||m==1){END();return 0;}
    if((A&1)&&(B&1)&&(n&1)&&(m&1))//显然只有这种情况才需要变换，如果不需要但我们变换了也不会影响原来的结果
    {
        vis[1][m-2]=3;vis[2][m-2]=4;
        vis[1][m]=2;vis[1][m-1]=1;
        A--,B--;
    }
    FOR(i,1,n-1)FOR(j,1,m-1)if(A&&!vis[i][j]&&!vis[i][j+1]&&!vis[i+1][j]&&!vis[i+1][j+1])
    {
        if(A>=2){vis[i][j]=1;vis[i][j+1]=2;vis[i+1][j]=1;vis[i+1][j+1]=2;A-=2;}
        else {vis[i][j]=1;vis[i][j+1]=2;A=0;break;}
    }
    FOR(i,1,n-1)FOR(j,1,m-1)if(B&&!vis[i][j]&&!vis[i][j+1]&&!vis[i+1][j]&&!vis[i+1][j+1])
    {
        if(B>=2){vis[i][j]=3;vis[i+1][j]=4;vis[i][j+1]=3;vis[i+1][j+1]=4;B-=2;}
        else {vis[i][j]=3;vis[i+1][j]=4;B=0;break;}
    }
    END();

    return 0;
}
//gl

如果你觉得这篇题解对你有帮助，那你可以点个赞支持我一下qwq。如果你对题解有任何问题/认为我的题解有任何问题，可以私信/在评论区发出来，当然如果你对我的题解有任何意见/建议也欢迎指出。我会尽我全力把我题解写到最好的qwq