题解：CF432E Square Tiling

· · 题解

题意：

用 i \times i 的正方形砖块铺设矩形，保证相邻砖块之间颜色不同，问字典序最小方案。

Subtask 1

打表手玩，对于25种不同case分类讨论得到答案。

Subtask 3

给一些写挂了的标算或者时间复杂度不好的搜索。

100 pts / 正解

根据手玩之后，考虑贪心。

按照从上到下，从左到右，行优先地顺序贪心即可。

假设当前枚举到 (i,j)：若当前 (i,j) 已被摆放，则跳过。

否则查看周围四个方块，从小到大找到第一个可以摆放的字符 c。 查看当前应当摆放砖块的最大的边长 k，条件有：

  1. 满足 (i,j)→(i,j+k−1) 的最小可能摆放的字符也为 c。

  2. 满足以 (i,j) 为左上角的边长为 k 的正方形均未被摆放。

AC code:

#include <bits/stdc++.h>
#define int long long
#define File(x, y) freopen(x".in", "r", stdin), freopen(y".out", "w", stdout)
#define REP(i, a, b) for (int i = a; i <= b; i ++)
#define PER(i, a, b) for (int i = a; i >= b; i --)
using namespace std;
const int N = 5e3 + 10;
char ans[N][N];
int n, m;
inline char getc(int x, int y) {
    char res = ans[x][y];
    if (!res) {
        res = 'A';
        while (res == ans[x - 1][y] || res == ans[x + 1][y] || res == ans[x][y - 1] || res == ans[x][y + 1]) res ++;
    }
    return res;
}
inline void cover(int x, int y) {
    char c = getc(x, y);
    putchar(c);
    if (ans[x][y]) return;
    int len = 1;
    while (x + len - 1 <= n && y + len - 1 <= m && getc(x, y + len - 1) == c) len ++;
    len --;
    REP(i, x, x + len - 1) REP(j, y, y + len - 1) ans[i][j] = c;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    REP(i, 1, n) {
        REP(j, 1, m) cover(i, j);
        puts("");
    }
    return 0;
}