CF432E Square Tiling 题解

思路分析：

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

这时候发现可以将小的合并成更大的正方形达成更小的字典序，如果

(i,j-1)

颜色字典序更小，我们可以判断一下

(i,j)

能否涂成

(i,j-1)

的颜色（要求图中放得下这个正方形，相邻的没有相同的），如果可以直接扩大上一个正方形。

实现很简单，时间复杂度

O(n^2)

，~~这有蓝吗~~？

AC Code:

CPP

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

CF432E Square Tiling 题解

文章操作

思路分析：

AC Code:

相关推荐

评论

CF432E Square Tiling 题解