CF432E Square Tiling 题解

· · 题解

思路分析：

小清新题。题目要求字典序最小且行优先，直接先按行后按列枚举每个点，贪心地填进去即可。地图染色一定可以只用四种颜色，直接看最小的与相邻块颜色不同的填进去。

这时候发现可以将小的合并成更大的正方形达成更小的字典序，如果 (i,j-1) 颜色字典序更小，我们可以判断一下 (i,j) 能否涂成 (i,j-1) 的颜色（要求图中放得下这个正方形，相邻的没有相同的），如果可以直接扩大上一个正方形。

实现很简单，时间复杂度 O(n^2)，这有蓝吗？

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,mp[N][N],f[N][N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++,cout<<'\n')
        for(int j=1;j<=m;cout<<char(mp[i][j++]+64))
            if(!mp[i][j]){f[i][j]=j;
                for(int k=1;k<=4;k++)
                    if(mp[i-1][j]!=k&&mp[i][j-1]!=k&&mp[i][j+1]!=k){mp[i][j]=k;break;}
                if(j>1&&mp[i][j-1]<=mp[i][j]&&mp[i][j-1]!=mp[i-1][j]&&mp[i][j-1]!=mp[i][j+1]&&i+j<=f[i][j-1]+n){
                    mp[i][j]=mp[i][j-1],f[i][j]=f[i][j-1];
                    for(int k=i+1;k<i+j-f[i][j];k++)mp[k][j]=mp[i][j];
                    for(int k=f[i][j];k<=j;k++)mp[i+j-f[i][j-1]][k]=mp[i][j];
                }
            }
    return 0;
}