原题 https://codeforces.com/contest/1956/problem/C
官方证明 https://codeforces.com/blog/entry/128426

官方的证明前面挺好的，但后面有点跳跃，我说说我的理解，建议结合官方证明看

原问题可以转化为：对于一个n*n的矩阵，每次涂色能涂一整行或者一整列，这一行或者一列中必须包含x个白色的，（n-x)个黑色的。只能涂最多2n次，证明最终最多有(nn-xx)个黑块。

既然是涂色问题，存在后涂的覆盖先涂的情况，那么我们从最后一次往前考虑，则涂过的不可覆盖。

（下面说的“前..次”，都是真正的前，尽管我们反着考虑，但表述时按照真正的涂色前后表述）

证明思路：分别证明

i）倒数前2x次涂的最好结果是留下xx个白块。

ii）按照i中的涂法，前(2n-2x)次不会再新增白块

这样实现了白块最小化，且由于我们这种涂色方案对所有的块都进行了涂色，所以黑块最大化。

先证 i ：

​ 最优的策略是x次横着涂，x次竖着涂，且保证每个块都被涂两次（一次横着，一次竖着），比如白色 涂在左上角x*x部分。一共2x次，每次涂x个白块，每个白块被涂两次，这样最多留下的就是xx个白 块。不存在白块数比xx还少的方案，因为一个块最多被用2次（它所在的行列）。

再证明 ii :

​ 显然我们可以指派前(2n-2x)涂色的时候，每次涂的x个白块是那2x次涂过不可覆盖的，所以能够做到不新增白块。