题解：P17242 [IOI 2026] 方块游戏 / tiling

· · 题解

思路

问题转化

每个方块大小为 2\times2，并且要求左上角坐标必须为偶数。

因此这个棋盘可以被划分为 N\times M 个互不重叠的 2\times2 的小区域。

所以问题变成：给定一个至少有一个白格子的 2\times2 方块，如何在线决定它可以放入哪个小区域，使得任何时候任何位置都不会出现全黑的 2\times2 区域。

贪心

我们维护如下不变量：

对于已经放置的每一个 2\times2 方块，它朝向未填充区域的那个角一定是白色。

例如：

考虑让每个方块的白格都朝向棋盘此时的未填满区域（注意，不一定是棋盘的几何中心），使每次操作后不变量仍成立。

假设当前所有已放置的方块满足不变量。

收到一个新方块后，由于它至少有一个白格，我们按照白格的位置选择对应区域。

如果一个 2\times2 方块有多个白格，任选一个即可，因为多给一个白格子并不会使情况更坏，它会让 2\times2 黑格更难以形成。

具体：

白格位置 放置区域
左上 右下
右上 左下
左下 右上
右下 左上

例如我们收到：

此时白格在左上。

假如给出的棋盘大小为 (2\times4)\times(2\times3)，我们把这个 2\times2 方格放在右下：

此时这个 2\times2 方块的白格朝向未填满区域。

这样放置后，新方块朝向未填充区域的角就是白色，因此不变量仍然成立。

正确性证明

下面证明该不变量可以保证不存在全黑的 2\times2 区域。

初始时棋盘为空，显然成立。

首先，一个全黑的 2\times2 区域不可能完全位于某一个方块内部，因为每个方块至少有一个白格。

因此，如果存在全黑的 2\times2，它一定跨越了至少两个方块。

考虑它所在的位置。

第一种

任意两个 2\times2 方格之间，两个方格在交界处各贡献两个黑格：

备注：图片内容不是按照正解思路画的，只是为了展示“假设存在 2\times2 的黑色方块”。下图同。

如图，中间出现全黑的 2\times2，那么它一定包含上方方块靠近下边界的两个格子，以及下方方块靠近上边界的两个格子（其他方向和位置同理）。

根据不变量：

上方方块靠近中心的一侧存在白格；下方方块靠近中心的一侧存在白格。

因此这个 2\times2 中至少有一个白格，与“全黑”矛盾。

第二种

四个 2\times2 方格交汇处各贡献一个黑格：

然而根据不变量：

左上方块的右下角是白色；右上方块的左下角是白色；左下方块的右上角是白色；右下方块的左上角是白色。

因此这个 2\times2 区域至少包含一个白格，不可能全部为黑色。

时间复杂度

共有 N\times M 个 2\times2 方块，每次寻找最多扫描 N\times M 个小区域，因此时间复杂度为 O(N^2M^2)。

由于 N,M\le100，所以最坏情况下 N^2M^2\le100^4=10^8。

代码

并不长。

#include <bits/stdc++.h>
#define rep(i,j,k) for (int i = (j); i <= (k); i ++)
#define per(i,j,k) for (int i = (j); i >= (k); i --)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define mkp make_pair
#define eb emplace_back
#define INF = 0x3f3f3f3f;
#define LINF = 0x3f3f3f3f3f3f3f3f;
//#define MOD 998244353
//#define MOD 1000000007
//#define int ll
using namespace std;
const int MAXN = 105;
//int T;
int n, m;
bool u[MAXN][MAXN]; // 用于标记该小区域是否被使用，我是按照 2 * 2 的小区域标记的，输出需要乘 2
// 这道题是一个交互题
// 不过无需使用主函数
// 每个样例会使用你写的 init 函数 和 receive_block 函数获取数据
pair<int, int> solve (int a) {
    // 直接遍历整个棋盘寻找第一个符合要求（从该方向上寻找第一个未被使用的小区域）
    // 例如第一种
    // 其实不一定是 i 优先，你也可以先遍历 j
    // 只要保证有一个白格子指向未被覆盖的区域即可
    if (a == 1) rep (i, 0, n - 1) rep (j, 0, m - 1) if (! u[i][j]) return {i, j};
    if (a == 2) rep (i, 0, n - 1) per (j, m - 1, 0) if (! u[i][j]) return {i, j};
    if (a == 3) per (i, n - 1, 0) rep (j, 0, m - 1) if (! u[i][j]) return {i, j};
    per (i, n - 1, 0) per (j, m - 1, 0) if (! u[i][j]) return {i, j};
}
void init (int N, int M) {
    n = N;
    m = M;
}
pair<int, int> receive_block (int TL, int TR, int BL, int BR) {
    // 由上文知，你需要根据白格的位置选择摆放位置
    // 选择任意白格即可，原因已经解释过
    auto z = solve (! TL ? 4 : (! TR ? 3 : (! BL ? 2 : 1)));
    int x = z.first, y = z.second;
    u[x][y] = true; // 标记使用
    return {x * 2, y * 2}; // 这是输出！返回你找到的答案
}

如果你看到这里，我想说明一下为什么可以想到这样的做法

这道题容易想到统计黑白格数量，但由于方块出现顺序未知，任何依赖未来信息或者整体数量的策略都无法在线实现。

注意到题目唯一保证的是：每个方块至少存在一个白格。

因此我们应该利用这个必然存在的白格，主动安排它的位置，使它成为阻止全黑 2\times2 的屏障。