传送门

分析

这个道题的题意是给你一个n * m的01矩阵，然后可以更改矩阵中的数字，比如把0改成1，或者把1改成0，要求最后矩阵中没有任何一个边长为偶数的子矩阵中含有偶数个1，如果不含偶数边长的子矩阵，则不需要改动

首先分析一下，我们能找到的最小的子矩阵应该是2 * 2 ，如果一个2 * 2矩阵内含有奇数个1，那么四个2 * 2矩阵拼接形成一个4 * 4矩阵中肯定就含有偶数个1，所以易得出，如果n和m同时大于3，那么一定无法构造出符合题意的矩阵

然后根据题意，n == 1的时候可以特判，所以我们需要讨论的情况只有n = 1的情况和n = 3的情况

首先来看n = 2的情况，如果我们需要让一个2 * 2的小矩阵内的1个数为0，不外乎一下几种情况

第一列：0个1 1个1 2个1 
第二列：1个1 0个1 1个1

所以只需要暴力枚举每一种情况即可

然乎再来分析n = 3的情况
首先每一列有3个数，对应2进制应该是0 - 8，而我们通过分析可以得出在每种状态下下一列可能的情况，分别对应两种，这个时候我们可以通过dp的思路来求解
假设我们把第i列的状态转化成j，那么第i + 1列的状态就只有两种，我们只需要计算出将第i列转化成j状态需要改动多少位数字，将第i + 1列转化为对应的状态需要改动多少位数字，然后两种转移方式取min即可，最后遍历最后一列0 - 8的状态所需要改动的数字的最小值，输出即可

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>using namespace std;const int N = 500006;
char a[4][N];
vector<int> st;
int n,m;
vector<int> g[8];
int f[N][8];int lowbit(int x){ //统计二进制中1的个数return x & -x;
}void res1(){int ans1 = 0,ans2 = 0;for(int i = 0;i < st.size();i += 2){if(st[i] == 0 ||st[i] == 3) ans1++;if((st[i + 1] == 1 || st[i + 1] == 2) && i + 1 < st.size()) ans1++;}for(int i = 0;i < st.size();i += 2){if(st[i] == 1 || st[i] == 2) ans2++;if(i + 1 < st.size() && (st[i + 1] == 0 || st[i + 1] == 3)) ans2++;}printf("%d",min(ans1,ans2));
}void res2(){//各种状态下的转移矩阵g[0] = {5,2};g[1] = {4,3};g[2] = {7,0};g[3] = {1,6};g[4] = {1,6};g[5] = {0,7};g[6] = {4,3};g[7] = {5,2};for (int i = 0; i < 8; i++) {f[0][i] = lowbit(i ^ st[0]); // 统计转移成相应状态需要改动多少位}for(int i = 1;i < st.size();i++)for(int j = 0;j < 8;j++){ //枚举每一种状态f[i][j] = min(f[i - 1][g[j][0]] + lowbit(j ^ st[i]),  //相同为0，不同为1f[i - 1][g[j][1]] + lowbit(j ^ st[i]));//当第i - 1列的状态为g[j][0]或者g[j][1]的时候为合法状态，进行状态转移}int ans = 0x3f3f3f3f;for(int i = 0;i < 8;i++) ans = min(ans,f[st.size() - 1][i]);printf("%d",ans);
}int main(){scanf("%d%d",&n,&m);if(n >= 4 && m >= 4){puts("-1");return 0;}if(n == 1||m == 1){puts("0");return 0;}for(int i = 0;i < n;i++)scanf("%s",a[i]);for(int i = 0;i < m;i++){int x = 0;for(int j = 0;j < n;j++){if(j) x <<= 1;x += a[j][i] - '0';}st.push_back(x);}if(n == 2) res1();else res2();return 0;
}