题解 CF1391D 【505】

这道题目的话看似没有头绪，我们分析一下。

偶数长度平方矩阵为：$2 \times 2$2×2、$4 \times 4$4×4、$8 \times 8$8×8……

我们考虑是否可能同时满足所有 $2 \times 2$2×2 的矩阵 $1$1 的个数为奇数，所有 $4 \times 4$4×4 的矩阵 $1$1 的个数为奇数。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uD8pFpHw-1597048634801)(https://i.loli.net/2020/08/10/Wb7EZy8nuXHwVMl.png)]

如图，每个黑色正方形是一个 $2 \times 2$2×2 的矩阵，为了满足要求它们 $1$1 的个数都为奇数，由 $4$4 个 $2 \times 2$2×2 的矩阵拼成的 $4 \times 4$4×4 大矩阵为了复合要求也必须由奇数个 $1$1，然后这和我们上面的东西矛盾，因为奇数 $\times 4=$×4= 偶数，所以，$n\geq 4$n≥4 且 $m \geq 4$m≥4 的矩阵，一定不能满足所有条件。

那么由于 $n\leq 3$n≤3，所以我们分类讨论。

• 对于 $n=1$n=1 ，答案显然为 $0$0。

• 对于 $n=2$n=2 ，显然对于连续的 $2$2 列，这两列 $1$1 的个数必须奇偶性不相同，因为只有奇数+偶数=奇数。所以一共就只有 $2$2 钟情况。

  1. 第 $1$1 列 $1$1 的个数为奇数，第 $2$2 列 $1$1 的个数为偶数……
  2. 第 $1$1 列 $1$1 的个数为偶数，第 $2$2 列 $1$1 的个数为奇数……

  时间复杂度 $O(n)$O(n)。

• 对于 $n=3$n=3，我们可以用状压 $dp$dp 来做，我们设 $f_{i,j}$fi,j​ 表示第 $i$i 列状态为 $j$j，转移的话，我们枚举前一列的合法状态，对所有可行解取个 $\min$min 即可，最后不要忘记加上这 $1$1 列修改的方格数。

  不难发现，每个状态可以转移的状态数均为 $2$2，因此此题复杂度为 $O(n)$O(n)，$16$16 倍常数，但这是可以 $A$A 的。

代码：

#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;
}