题解：AT_arc226_c [ARC226C] Square Corner Packing
沉石鱼惊旋
·
·
题解
分析一些东西：一次操作会导致某些行某些列多 2 个黑色格子，那么也就是任意时刻一行一列黑点个数都是偶数。
$n,m$ 存在一个偶数，不妨设 $n$ 是奇数，那么显然因为每一列都只能有偶数个黑点，所以每一列都会至少有一个白点，那么上界就是 $\frac{nm-m}{4}$。而这个也是可以构造达到的，就是直接当 $(n-1,m)$ 的情况做 $n,m$ 都是偶数的构造。
若 $n,m$ 都是奇数，参考类似的分析，每一列都会至少有一个白点，每一行都会至少有一个白点，所以上界是 $\lfloor\frac{nm-\max\{n,m\}}{4}\rfloor$，这个也是可以达到的。
首先我们考虑 $n=m$ 且都是奇数的 case，给这个做一个构造。通过手玩不难得到如下的 $5\times 5$ 和 $9\times 9$ 的解：
```none
122.1
.2233
44.33
4455.
1.551
1223344.1
.22334455
aa.....55
aa.....dd
cc.....dd
cc.....bb
99.....bb
99887766.
1.8877661
```
那么也就是 $(4k+1)\times (4k+1)$ 类型可以做到 $\lfloor\frac{nm-\max\{n,m\}}{4}\rfloor$。
对于 $7\times 7$，即为 $(4k+3)\times (4k+3)$ 的类型很遗憾我们只能得到这样一个解：
```none
12233.1
.223344
880.044
88...99
770.099
776655.
1.66551
```
我们浪费了 $\max\{n,m\}+2$ 个格子。也就是我们只能构造 $\lfloor\frac{(4k+3)^2-(4k+3)}{4}\rfloor-2$ 个。不过由于下取整，我们发现上式的分子部分等于 $16k^2+20k+4$，如果不浪费这两个只能构造到 $16k^2+20k+6$，很显然 $\lfloor\frac{16k^2+20k+4}{4}\rfloor=\lfloor\frac{16k^2+20k+6}{4}\rfloor$，也就是我们这样构造操作数依然是上界。
那么所有的 $(2k+1)\times (2k+1)$ 类型就解决了。
不妨设 $n\gt m$，声称如此构造 $m\times m$ 的一个解然后构造一个 $(n-m)\times m$ 的解（注意到 $n-m$ 一定是偶数所以上界是 $\lfloor\frac{(n-m)m-(n-m)}{4}\rfloor$），依然是操作数上界 $(nm-\max\{n,m\})/4$，即 $\lfloor\frac{nm-n}{4}\rfloor=\lfloor\frac{m^2-m}{4}\rfloor+\lfloor\frac{(n-m)m-(n-m)}{4}\rfloor$ 恒成立。这是因为 $(n-m)m-(n-m)=(n-m)(m-1)$ 一定是 $4$ 的倍数，$n-m$ 和 $m-1$ 都是偶数。
所以对于奇数的情况，我们只要构造一个 $m\times m$ 的解，然后构造一个 $(n-m)\times m$ 的解，依然顶到了操作数上界，构造是最优的。
至于 $m\times m$ 的解的构造，仿照上文给的三个例子即可，就是每次铺边界 $2$ 格，然后缩成 $(m-2)\times (m-2)$ 继续做。