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

· · 题解

怎么是唐题？

手玩一下 n=1 的情况可以发现，唯一的策略是将左边两个是黑色的往左放，其余往右放。扩展这个想法，我们肯定将所有块全部当成 S=3 来做，那么对左上角为白色的块尽可能往右下角放，即选择距离右下角曼哈顿距离最近的任意一个格子放置，其余三种同理。写一下发现直接通过了，下文考虑证明这是正确的。

考虑反证，取第一次出现 2 \times 2 的黑色正方形的位置，其内部显然不可能全部是同一方块。若只由两个方块拼接构成，则取较早放下的那个方块，可以发现它更优的放置位置是向较晚放下方块移动一步，因此该方案不符合我们的放置方案；同理讨论由四个方块拼接起来的情况，仍取最早放置的位置并讨论该方块的类型，可以发现我们仍然可以在剩余四个位置中找出在我们的方案下更优的放置位置，因此我们的做法是正确的。

实现上直接通过四个堆维护即可。