题意
给定一个 \(n\) 行 \(m\) 列的目标矩阵,矩阵元素只有 W 或 B ,并且你有一个初始矩阵,元素全为 W 。
现在你可以矩阵实施以下操作:
使用一块钱,选定一个包含 \((1,1)\) 的子矩阵,把矩阵中的元素全部反转( W 变 B , B 变 W )。
使用三块钱,选定一个包含 \((n,1)\) 的子矩阵,把矩阵中的元素全部反转。
使用四块钱,选定一个包含 \((1,m)\) 的子矩阵,把矩阵中的元素全部反转。
使用两块钱,选定一个包含 \((n,m)\) 的子矩阵,把矩阵中的元素全部反转。
现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。
\(1\le n,m\le 500\)。
题解
首先 \(2,3\) 操作是无用的,只需考虑 \(1,4\) 操作。
整个矩阵取反很难搞,做个简单的变形:\(s_{i,j}=a_{i,j}\oplus a_{i,j+1}\oplus a_{i+1,j}\oplus a_{i+1,j+1}\),则操作 \(1\) 是单点取反,操作 \(4\) 是同时取反 \((x,y),(x,m),(n,y),(n,m)\)。倒着考虑,目标态是全为 \(0\)。称操作 \(4\) 为 \(\operatorname{op}(x,y)\)。
接下来是两个重要结论:
- \(\operatorname{op}(x,y)\) 的必要条件是 \(s_{x,y}=s_{x,m}=s_{n,y}=1\)。因为如果不是,操作后至少还需要 \(1\) 的代价使这三位都归零。不如直接三次操作 \(1\)。
- 不存在 \(\operatorname{op}(x_1,y_1),\operatorname{op}(x_2,y_2)\),有 \(x_1=x_2\) 或 \(y_1=y_2\)。因为如果存在,不妨设为 \(y_1=y_2\),则 \((n,y_1),(n,m)\) 两位是不动的,另外 \(4\) 位直接操作 \(1\) 即可。
第二个结论提供了很好的二分图模型。再稍加推导,易知答案为 \(rem-k\),其中 \(rem\) 为 矩阵变换后 \(1\) 的数目,\(k\) 为最大匹配。\((n,m)\) 处需特殊判断。
标签:题解,元素,矩阵,取反,CF1592F2,操作,operatorname,op From: https://www.cnblogs.com/fish07/p/17320700.html