题解：CF1551D2 Domino (hard version)

TCY1234567 · 2026-06-10 20:56:03 · 题解

题解

恶心分讨题。

是否合法我们已经在上一道题目中知道了，所以说我们直接考虑如何构造。

首先是 n 为偶数，m 也为偶数的情况，我们考虑将其分为若干个 2 \times 2 矩阵，直接放竖的或者横的，直到满足条件即可。

对于 n 为奇数的情况，其实就相当于所出来了额外的一行，所以说直接把多出来的这一行放横的即可。然后就转化成第一种情况了。

对于 m 为奇数的情况，同理，把那一列全放竖的即可，然后也能转化成第一种形式。然后就做完了，剩下的都是细节了。

代码

#include<bits/stdc++.h>
using namespace std;
int T;
int n,m,k;
int ans[210][210];
void init(){
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            ans[i][j] = -1;
        }
    }
}
void solve1(int nn,int mm,int kk){
    bool typ1 = 0,typ2 = 0;
    for(int i = 1;i<=nn;i+=2){
        typ2^=1;
        if(mm%4==2)typ1^=1;
        for(int j = 1;j<=mm;j+=2){
            typ1^=1;
            if(kk!=0){
                ans[i][j] = ans[i][j+1] = typ1;
                ans[i+1][j] = ans[i+1][j+1] = typ1^1;
                kk-=2;
            }else{
                ans[i][j] = ans[i+1][j] = typ2+2;
                ans[i][j+1] = ans[i+1][j+1] = (typ2^1)+2;
            }
        }
    }
}
void output(){
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cout<<char(ans[i][j]+'a');
        }
        cout<<"\n";
    }
}
void solve(){
    cin>>n>>m>>k;
    if(n%2==0&&m%2==0){
        if(k%2==0){
            cout<<"YES\n";
            solve1(n,m,k);
            output();
        }else{
            cout<<"NO\n";
        }
    }else if(n%2==0){
        if(k<=n*(m-1)/2&&k%2==0){
            cout<<"YES\n";
            solve1(n,m-1,k);
            for(int i = 1,typ = 0;i<=n;i+=2,typ^=1){
                ans[i][m] = ans[i+1][m] = typ+4;
            }
            output();
        }else{
            cout<<"NO\n";
        }
    }else if(m%2==0){
        int h = k-(m/2);
        if(h>=0&&h%2==0){
            cout<<"YES\n";
            solve1(n-1,m,h);
            for(int i = 1,typ = 0;i<=m;i+=2,typ^=1){
                ans[n][i] = ans[n][i+1] = typ+4;
            }
            output();
        }else{
            cout<<"NO\n";
        }
    }
}
int main(){
    cin>>T;
    while(T--){
        solve();
    }    
    return 0;
}