题解 CF1391D 【505】

这道题目的话看似没有头绪，我们分析一下。 偶数长度平方矩阵为：$2 \times 2$、$4 \times 4$、$8 \times 8$…… 我们考虑是否可能同时满足所有 $2 \times 2$ 的矩阵 $1$ 的个数为奇数，所有 $4 \times 4$ 的矩阵 $1$ 的个数为奇数。  如图，每个黑色正方形是一个 $2 \times 2$ 的矩阵，为了满足要求它们 $1$ 的个数都为奇数，由 $4$ 个 $2 \times 2$ 的矩阵拼成的 $4 \times 4$ 大矩阵为了复合要求也必须由奇数个 $1$，然后这和我们上面的东西矛盾，因为奇数 $\times 4=$ 偶数，所以，$n\geq 4$ 且 $m \geq 4$ 的矩阵，一定不能满足所有条件。 那么由于 $n\leq 3$，所以我们分类讨论。 - 对于 $n=1$ ，答案显然为 $0$。 - 对于 $n=2$ ，显然对于连续的 $2$ 列，这两列 $1$ 的个数必须奇偶性不相同，因为只有奇数+偶数=奇数。所以一共就只有 $2$ 钟情况。 1. 第 $1$ 列 $1$ 的个数为奇数，第 $2$ 列 $1$ 的个数为偶数…… 2. 第 $1$ 列 $1$ 的个数为偶数，第 $2$ 列 $1$ 的个数为奇数…… 时间复杂度 $O(n)$。 - 对于 $n=3$，我们可以用状压 $dp$ 来做，我们设 $f_{i,j}$ 表示第 $i$ 列状态为 $j$，转移的话，我们枚举前一列的合法状态，对所有可行解取个 $\min$ 即可，最后不要忘记加上这 $1$ 列修改的方格数。 不难发现，每个状态可以转移的状态数均为 $2$，因此此题复杂度为 $O(n)$，$16$ 倍常数，但这是可以 $A$ 的。 代码： ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; template<typename T>inline void read(T &FF){ T RR=1;FF=0;char CH=getchar(); for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1; for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48); FF*=RR; } int a[15][1000010],f[1000010][11]; vector<int>v[15]; bool check(int x,int y){//判断2个状态是否能相互转移 int a1=x&1,a2=(x>>1)&1,a3=(x>>2)&1; int b1=y&1,b2=(y>>1)&1,b3=(y>>2)&1; if((a1+a2+b1+b2)%2==0)return false; if((a2+a3+b2+b3)%2==0)return false; return true; } int work(int y,int x){//算修改了几个格子 int a1=x&1,a2=(x>>1)&1,a3=(x>>2)&1; return (a[1][y]!=a1)+(a[2][y]!=a2)+(a[3][y]!=a3); } int main(){ int n,m;read(n);read(m); if(n>=4&&m>=4){ puts("-1"); return 0; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ char ch=getchar(); for(;ch!='0'&&ch!='1';ch=getchar()); a[i][j]=(ch=='1'); } if(n==1){ puts("0"); return 0; } if(n==2){ int ans1=0,ans2=0; for(int j=1;j<=m;j++) if((a[1][j]+a[2][j])%2!=(j&1))ans1++; for(int j=1;j<=m;j++) if((a[1][j]+a[2][j])%2!=((j&1)^1))ans2++; cout<<min(ans1,ans2); return 0; } for(int i=0;i<(1<<3);i++) for(int j=0;j<(1<<3);j++) if(check(i,j)) v[j].push_back(i); for(int j=0;j<(1<<3);j++)f[1][j]=work(1,j);//边界 for(int i=2;i<=m;i++) for(int j=0;j<(1<<3);j++){ f[i][j]=n*m+1; for(auto k:v[j]){ f[i][j]=min(f[i][j],f[i-1][k]+work(i,j)); } } int ans=n*m+1; for(int j=0;j<(1<<3);j++)ans=min(ans,f[m][j]); cout<<ans; return 0; } ```