# 题解 CF1391D

## 题意：

$$n \times m \geq 10^6$$

## 题解:

$$4$$ 个加起来就是偶数了。

$$n(m) == 1$$$$puts("0");$$ 就行了。

$$n(m) == 2$$

$$dp[i][k] = min(dp[i][k], dp[i-1][j]$$ ^ $$a[i])$$

$$n(m) == 3$$

$$dp[i][k] = min(dp[i][k], dp[i-1][j]$$ ^ $$a[i])$$

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#define maxn 1000010
#define maxm 1000010
#define ls x << 1
#define rs x << 1 | 1
#define inf 2000000000
#define inc(i) (++ (i))
#define dec(i) (-- (i))
#define mid ((l + r) >> 1)
#define int long long
#define XRZ 1000000000
#define debug() puts("XRZ TXDY");
#define mem(i, x) memset(i, x, sizeof(i));
#define Next(i, u) for(register int i = head[u]; i ; i = e[i].nxt)
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout);
#define Rep(i, a, b) for(register int i = (a) , i##Limit = (b) ; i <= i##Limit ; inc(i))
#define Dep(i, a, b) for(register int i = (a) , i##Limit = (b) ; i >= i##Limit ; dec(i))
int dx[10] = {1, -1, 0, 0};
int dy[10] = {0, 0, 1, -1};
using namespace std;
register int x = 0, f = 1; register char c = getchar();
while(c < ‘0‘ || c > ‘9‘) {if(c == ‘-‘) f = -1; c = getchar();}
while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - 48, c = getchar();
return x * f;
} int a[maxn], f[maxn][8], b[8]; char s;
if(n >= 4 && m >= 4) { puts("-1"); goto QwQ;}
if(n >= m) Rep(i, 1, n) Rep(j, 1, m) scanf(" %c", &s), a[i] = (a[i] << 1) + s - ‘0‘;
else { Rep(i, 1, n) Rep(j, 1, m) scanf(" %c", &s), a[j] = (a[j] << 1) + s - ‘0‘; swap(n, m);}
if(m == 1) { puts("0"); goto QwQ;} Rep(i, 1, 7) b[i] = b[i - (i & -i)] + 1;
if(m == 2) { Rep(i, 1, n) Rep(j, 0, 3) f[i][j] = inf; Rep(i, 0, 3) f[1][i] = b[i ^ a[1]]; int Ans = inf;
Rep(i, 2, n) Rep(j, 0, 3) Rep(k, 0, 3) if(b[j] + b[k] & 1) f[i][k] = min(f[i][k], f[i - 1][j] + b[k ^ a[i]]);
Rep(i, 0, 3) Ans = min(Ans, f[n][i]); if(Ans > XRZ) puts("-1"); else printf("%lld", Ans);
} else { Rep(i, 1, n) Rep(j, 0, 7) f[i][j] = inf; Rep(i, 0, 7) f[1][i] = b[i ^ a[1]]; int Ans = inf;
Rep(i, 2, n) Rep(j, 0, 7) Rep(k, 0, 7) if((b[j & 3] + b[k & 3] & 1) && (b[j >> 1] + b[k >> 1] & 1)) f[i][k] = min(f[i][k], f[i - 1][j] + b[k ^ a[i]]);
Rep(i, 0, 7) Ans = min(Ans, f[n][i]); if(Ans > XRZ) puts("-1"); else printf("%lld", Ans);
} QwQ:; return 0;
}


(0)
(0)