目前在看贪心/构造/DP 杂题选做,发现一道非常不错的结论题,具有启发意义。
先说明如下结论
结论一:如何怎么样都不会使用二和三操作
证明:
二三操作显然可以通过两次一操作达到,而其操作费用大于两次一操作费用
所以显然我们只会操作一四操作。
那么我们发现翻转一整个矩形不好操作,翻转到一特定状态也不好处理,不如考虑倒序操作:即给定特定状态变为全白状态的费用,知其与原问题等价。
然后我们处理翻转问题,我们考虑一个转换
\(a_{i,j} = a_{i,j}\ xor\ a_{i+1,j}\ xor\ a_{i,j + 1}\ xor\ a_{i + 1,j + 1}\)。
我们发现全白时显然全等为\(0\)。
而一四操作我们可以将其本质变为:
一操作:单点翻转\((x,y)\)
四操作:四点翻转\((x,y),(x,m),(n,y),(n,m)\)
那么问题变得显然起来。
我们依旧给出了两个结论
结论二:不用同时使用两个横坐标或竖坐标相等的四操作
证明:其等价于修改四个任意散点,其可以等价于四次一操作的费用
结论三:除非\((x,y),(n,y),(x,m)\)都为1,才会使用\((x,y)\)这一四操作
证明:如果有一个不为\(1\),那么其有一个错误反转,我们需要其一个一操作反转回来,那么其等价于\(1 + 2 = 3\),可以使用一操作代替。
那么经典问题转化为满足某种条件的改变行列取点数量。
二分图上最大匹配即可。