题解 CF1391D 【505】

给出一个$n\times m$的$01$矩阵，如果每个长宽都为偶数的子矩阵内都只有奇数个$1$，则称这个矩阵是好的。 问能否把矩阵改成好的，如果能改几下。 首先证明：$m,n\ge4$时无解。 取 $(1,1)$ 到 $(2,2)$、$(1,3)$ 到 $(2,4)$、$(3,1)$ 到$(4,2)$ 和 $(3,3)$ 到 $(4,4)$ 四个子矩阵，他们中间都有奇数个 $1$，所以$(1,1)$到 $(4,4)$ 有偶数个 $1$，和好矩阵的定义矛盾，故不存在这样的好矩阵。 之后，由于 $n$ 较小，并且 $n\le m$，所以压根不用状压，直接暴力分类讨论： 1. $n=1$：输出0 2. $n=2$：令 $f_{i,a,b}$ 表示第 $i$ 列，第一个元素是 $a$，第二个元素是 $b$，让 $(1,1)$ 到 $(2,i)$ 是好矩阵的最少变动数 3. $n=3$：令 $f_{i,a,b,c}$ 表示第 $i$ 列，第一个元素是 $a$，第二个元素是 $b$，第三个元素是 $c$，让 $(1,1)$ 到 $(3,i)$ 是好矩阵的最少变动数 之后对总共的 $12$ 种情况，分别画图讨论就可以了，思维难度瞬间降低。 代码有一种宏伟的气势23333333 ```cpp #include <iostream> using namespace std; const int MAXNM = 1e6 + 5; int n, m; char mat[MAXNM << 2]; int dp[MAXNM][2][2][2]; #define str(i, j) mat[(i - 1) * m + j] int main() { scanf("%d%d", &n, &m); if(n > 3 && m > 3) { cout << -1 << endl; } for(int i = 1; i <= n; i++) { scanf("%s", &str(i, 1)); } if(n == 1) { cout << 0 << endl; } else if(n == 2) { for(int i = 1; i <= m; i++) { dp[i][1][0][0] = min(dp[i - 1][1][1][0], dp[i - 1][0][0][0]) + (str(1, i) == '0') + (str(2, i) == '1'); dp[i][0][1][0] = min(dp[i - 1][1][1][0], dp[i - 1][0][0][0]) + (str(1, i) == '1') + (str(2, i) == '0'); dp[i][0][0][0] = min(dp[i - 1][1][0][0], dp[i - 1][0][1][0]) + (str(1, i) == '1') + (str(2, i) == '1'); dp[i][1][1][0] = min(dp[i - 1][1][0][0], dp[i - 1][0][1][0]) + (str(1, i) == '0') + (str(2, i) == '0'); } cout << min(min(dp[m][0][0][0], dp[m][0][1][0]), min(dp[m][1][0][0], dp[m][1][1][0])) << endl; } else if(n == 3) { for(int i = 1; i <= m; i++) { dp[i][0][0][0] = min(dp[i - 1][1][0][1], dp[i - 1][0][1][0]) + (str(1, i) == '1') + (str(2, i) == '1') + (str(3, i) == '1'); dp[i][0][0][1] = min(dp[i - 1][1][0][0], dp[i - 1][0][1][1]) + (str(1, i) == '1') + (str(2, i) == '1') + (str(3, i) == '0'); dp[i][0][1][0] = min(dp[i - 1][1][1][1], dp[i - 1][0][0][0]) + (str(1, i) == '1') + (str(2, i) == '0') + (str(3, i) == '1'); dp[i][0][1][1] = min(dp[i - 1][1][1][0], dp[i - 1][0][0][1]) + (str(1, i) == '1') + (str(2, i) == '0') + (str(3, i) == '0'); dp[i][1][0][0] = min(dp[i - 1][0][0][1], dp[i - 1][1][1][0]) + (str(1, i) == '0') + (str(2, i) == '1') + (str(3, i) == '1'); dp[i][1][0][1] = min(dp[i - 1][1][1][1], dp[i - 1][0][0][0]) + (str(1, i) == '0') + (str(2, i) == '1') + (str(3, i) == '0'); dp[i][1][1][0] = min(dp[i - 1][1][0][0], dp[i - 1][0][1][1]) + (str(1, i) == '0') + (str(2, i) == '0') + (str(3, i) == '1'); dp[i][1][1][1] = min(dp[i - 1][0][1][0], dp[i - 1][1][0][1]) + (str(1, i) == '0') + (str(2, i) == '0') + (str(3, i) == '0'); } int ans = 1e9 + 1; for(int i = 0; i < 2; i++) { for(int j = 0; j < 2; j++) { for(int k = 0; k < 2; k++) { ans = min(ans, dp[m][i][j][k]); } } } cout << ans << endl; } } ```