题解：CF432E Square Tiling

题意：

用

i \times i

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

Subtask 1

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

Subtask 3

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

100 pts / 正解

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

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

假设当前枚举到

(i,j)

：若当前

(i,j)

已被摆放，则跳过。

否则查看周围四个方块，从小到大找到第一个可以摆放的字符

c

。查看当前应当摆放砖块的最大的边长

k

，条件有：

满足 $(i,j)→(i,j+k−1)$ 的最小可能摆放的字符也为 $c$ 。
满足以 $(i,j)$ 为左上角的边长为 $k$ 的正方形均未被摆放。

AC code:

CPP

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

题解：CF432E Square Tiling

文章操作

题意：

Subtask 1

Subtask 3

100 pts / 正解

AC code:

相关推荐

评论

题解：CF432E Square Tiling