arc226_c

IntoTheDusk · 2026-08-09 22:18:39 · 题解

难绷题。赛中最后 5min 绝杀！

注意到我们可以选择 (r,c,1) 使得一个 2 \times 2 的方格被填满。下文称这一种结构为“方格”。

有一个很显然的下界是 \lfloor\frac{n}{2}\rfloor \times \lfloor\frac{m}{2}\rfloor。我们只要尽量用方格去贪心的匹配即可。我们称这一种构造是“平凡的构造”。

通过打表，我们发现，当 n,m \equiv 1 \pmod{2} 的时候平凡的构造是错的，其余情况都是对的。于是我们考虑怎么做 n,m \equiv 1 \pmod{2}。

不妨假设 n\le m。m >n 的情况颠倒一下即可。

首先，我们可以将最右侧那一段 n \times m-n 的矩形用平凡的构造填满。于是，接下来我们只需要在乎左侧 n \times n 的正方形。

我们可以采用递归的构造。假设我们想要对一个 L \times L 的矩形开展构造（其中 L 为奇数），则我们可以按照下列步骤：

• 将矩形的四个角填满，也就是 (1,1,L-1)。
• 将矩形的一周用方格填满。具体地，对于 1 \sim \frac{L-3}{2} 之间的每一个正整数，我们选择 (1,2i,1),(2i,L-1,1),(L-1,L-2i,1),(L-2i,1,1)。
• 最后中央剩下一个 (L-4) \times (L-4) 的正方形，递归即可。

可能有点抽象，下面以 L=7 为例。

上图中，红色的方格就是第一次操作填的，其他非白颜色的方格就是绕着周边填，画斜线的部分就是递归的部分。

这种构造的答案是 \lfloor\frac{n}{2}\rfloor \times \lfloor\frac{m}{2}\rfloor+\lfloor\frac{\min(n,m)-1}{4}\rfloor。可以证明，这就是最优的。

于是就做完了。时间复杂度 \mathcal{O}\left(Tnm\right)。

评测记录。