题解：IOI 2026 D1T3
Wyh_dailyAC
·
·
题解
讲个笑话
秒了这题，以为是普及组。
Sol
只考虑每个块仅一个白的最坏情况。
正如前面的图，我们要根据唯一一个白格子的朝向决定摆放位置。
由于其他块的情况等价于某个块旋转，所以只对右下为白色的情况进行考量。
根据我截图中的口胡，大致思想是把第一个右下白的堆到左上角，然后接下来的右下白堆到其同行邻接的位置（放到整个图上说，就是先堆出来角落，然后在这个角的同行临近着堆和其在同个方位为白色的块），就像这样：
其实，成一个 2\times2 的黑，是可能会在一个块的上下左右、左上左下、右上右下八个方位形成的。
右下的白块可以破坏掉右、下、右下的形成。
然后分两种情况。
第一种是上一行的左下白情况挤过来了：
这时候，左上、上由于顶着一个白块而形成不了，左、左下侧也顶着一个同行的白块而形成不了，上一行的右上部分的 2\times2 也会因为白块而无法成形，所以八个方位都被破坏了。
第二种就是没挤过来，然后在右上部分临近 / 不临近的情况：（图略）。
其实本质上和挤没挤过来没太大关系：
如果上顶是左下白色，则会受图中 2 类白块影响，导致左上、上、右上全被破坏；否则，如果上顶是右下白色，也是同理的，会受到图中 1 类白块影响，导致上述的三个方面被破坏。
由于构造方式，左侧一定有一个同在右下为白的块，导致左、左下两个方面被破坏。进而，根据这种构造，全部方面都会被破坏。
但这是在一般情况下，如果从上往下行行构造的块和从下往上行行构造的块碰面了（构造时融在一行内）该怎么办？就像这样：
这个时候其实也是同理的。如图：
于是这个构造就处理完了，本题也就做完了。
---
:::success[Code]{open}
```cpp line-numbers
#include <bits/stdc++.h>
#define sfr return cerr << "safe\n", 0;
#define sf_void return cerr << "safe\n", void();
using namespace std;
using ll = long long;
using i128 = __int128;
using pr = pair<int, int>;
using prt = tuple<int, int>;
using tpt = tuple<int, int, int>;
int n, m, t, b, tl, tr, bl, br, tbl, tbr;
auto init(int N, int M) -> void {
n = N, m = M;
t = 1, b = N;
tl = bl = 1, tr = br = M;
tbl = 1, tbr = M;
}
auto receive_block(int TL, int TR, int BL, int BR) -> pair<int, int> {
pr ret;
if (t == b) {
if (!TR || !BR) {
ret.first = t * 2 - 2, ret.second = tbl * 2 - 2;
tbl++;
} else {
ret.first = t * 2 - 2, ret.second = tbr * 2 - 2;
tbr--;
}
return ret;
}
if (!BR) {
ret.first = t * 2 - 2, ret.second = tl * 2 - 2;
tl++;
if (tl > tr) ++t, tl = 1, tr = m;
} else if (!BL) {
ret.first = t * 2 - 2, ret.second = tr * 2 - 2;
tr--;
if (tl > tr) ++t, tl = 1, tr = m;
} else if (!TR) {
ret.first = b * 2 - 2, ret.second = bl * 2 - 2;
bl++;
if (bl > br) --b, bl = 1, br = m;
} else if (!TL) {
ret.first = b * 2 - 2, ret.second = br * 2 - 2;
br--;
if (bl > br) --b, bl = 1, br = m;
}
if (t == b) tbl = max(tl, bl), tbr = min(tr, br);
return ret;
}
```
:::
---
upd：QOJ 上过了。
upd：洛谷上过了。