题解：AT_arc226_c [ARC226C] Square Corner Packing

· · 题解

设 U 表示未被染黑的格子个数。我们的目标变成了最小化 U。

因为总共操作 K 次，而每次恰好染黑四个格子，于是 U=HW-4K，于是 U\equiv HW\pmod 4。

设 u_i 表示第 i 行未被染黑的格子个数，v_j 表示第 j 列未被染黑的格子个数。

那么容易发现，每次操作对任意一行、一列染黑的格子数为 0 或 2。即 u_i,v_j 每次操作后奇偶性不变：

u_i\equiv W\pmod 2,\\ v_j\equiv H\pmod 2.

未染色总数满足 U=\sum_{i=1}^H u_i=\sum_{j=1}^W v_j。

接下来我们想要达到最优解，思路是导出 U 的理论下界，并构造方案使得其恰好为理论下界。

H,W 均为偶数

此时直接构造 (H/2)\times(W/2) 个 2\times 2 的正方形即可，U=0。

H 为偶数，W 为奇数（H 为奇数，W 为偶数同理）

我们令 W\gets W-1，用 H,W 均为偶数的方法构造，然后最后会剩下一列，这一列我们直接留白，于是 U=H。

而由于 u_i\equiv W\pmod 2，W 又是奇数，那么 u_i\equiv 1\pmod 2，即 u_i\ge 1。

那么 U=\sum_{i=1}^H u_i\ge \sum_{i=1}^H 1=H。

H,W 均为奇数，H=W

当 H 和 W 为 1 或 3 时，构造是显然的，否则当 H\ge 5 时，我们可以用下面这个方法去递归构造：

maabbcc.m
.aabbccdd
ll?????dd
ll?????ee
kk?????ee
kk?????ff
jj?????ff
jjiihhgg.
m.iihhggm

此时问题的规模减小 4，递归下去即可。

接下来导出理论下界。类似地有 U=\sum_{i=1}^H u_i\ge \sum_{i=1}^H 1=H。

而由于 U\equiv HW\pmod 4，当 H 为奇数时，H^2（即 HW）模 4 余 1。

H,W 均为奇数，H<W（H>W 同理）

左侧按照 H=W 构造之后，剩下的部分直接用 2\times 2 的正方形填充。那么：

接下来导出理论下界。类似地有 U=\sum_{j=1}^W v_j\ge \sum_{j=1}^W 1=W。