CF 1391D 505

题目：给定n个长度为m的"0""1"串，你可以改变任意一个位置的二进制，使得边长为偶数的任意一个子矩阵中"1"的个数为奇数，如果不可能输出"-1"，可能的话，最少需要改变几个位置的二进制。

思路：硬想太难想。。。（对我来说），然后自己构造了下边长为2，4，6的矩阵，推出一个性质，边长为4的子矩阵是由4个不重合的边长为2的子矩阵组成的，通过题目的性质可以得到这四个边长为2的子矩阵中"1"的个数一定为奇数，则边长为4的子矩阵一定不可能包含奇数个"1"，于是我们推出（n>=4）答案不存在，（n = 1）答案明显为0，现在只有（n = 2，3）的情况没有讨论。

样例：

1 0 1

0 0 1

1 1 0

转换：

1 0 0

0 1 0

①n = 2，我们可以想到让第一行和第二行相同下标相加组成新的序列，则这个序列的序列从左到右一定满足"奇偶奇偶..."或者"偶奇偶奇..."，只有2种情况。

③ n = 3，我们只需要让第一行和第二行，第二行和第三行相加组成新的序列，按照①中描述序列的性质，则（n = 3）有4种情况。

对于（n = 3）我们可以分析出一个规律，我们假设新的序列上为up，下为down，满足奇偶性为ok，不满足为not ok（如果枚举的某个情况为up为"奇偶...",down为"偶奇..."，看样例下面的转换(ok为1)）：

up is ok ① down is ok 0

　　　　 ② down is not ok 1

up is not ok ① down is ok 1

　　　　 ② down is not ok 1

（后面的数字为需要改变二进制的个数）

然后我们只需要模拟上面的所有情况就行，代码有些地方是可以简略的

  1 #include<iostream>
  2 #include<string>
  3 #include<vector>
  4 #include<cstdio>
  5 
  6 #define ll long long
  7 #define pb push_back
  8 
  9 using namespace std;
 10 
 11 const int N = 1e6 + 10;
 12 vector<string > str;
 13 int cnt[2][N];
 14 
 15 void solve()
 16 {
 17     int n, m;
 18     cin >> n >> m;
 19     string s;
 20     for(int i = 0; i < n; ++i){
 21         cin >> s;
 22         str.pb(s);
 23     }
 24 
 25     int cnt = 1e9;
 26     if(n >= 4) cnt = -1;
 27     else if(n == 1) cnt = 0;
 28     else if(n == 2){
 29         //odd even
 30         int t1, t2;
 31         t1 = t2 = 0;
 32         for(int i = 0; i < m; ++i){
 33             int x = str[0][i] + str[1][i] - '0' - '0';
 34             if(i & 1 && (x & 1)) t1++;
 35             else if((!(i & 1)) && (!(x & 1))) t1++;
 36         }
 37         //even odd
 38         for(int i = 0; i < m; ++i){
 39             int x = str[0][i] + str[1][i] - '0' - '0';
 40             if(i & 1 && (!(x & 1))) t2++;
 41             else if((!(i & 1)) && (x & 1)) t2++;
 42         }
 43         cnt = min(t1, t2);
 44     }else if(n == 3){
 45 
 46         int up, down, t1, t2, t3, t4;
 47         t1 = t2 = t3 = t4 = 0;
 48         for(int i = 0; i < m; ++i){
 49             up = (str[0][i] + str[1][i] - '0' - '0') % 2;
 50             down = (str[1][i] + str[2][i] - '0' - '0') % 2;
 51             //odd even odd even
 52             if(i & 1){
 53                 if(!up){ // up is ok
 54                     if(!down) t1 += 0;// down is ok
 55                     else t1 += 1;
 56                 }else{
 57                     if(!down) t1 += 1;
 58                     else t1 += 1;
 59                 }
 60             }else{
 61                 if(up){ // up is ok
 62                     if(down) t1 += 0;
 63                     else t1 += 1;
 64                 }else {
 65                     if(down) t1 += 1;
 66                     else t1 += 1;
 67                 }
 68             }
 69             //odd even even odd
 70             if(i & 1){
 71                 if(!up){
 72                     if(down) t2 += 0;
 73                     else t2 += 1;
 74                 }else{
 75                     if(down) t2 += 1;
 76                     else t2 += 1;
 77                 }
 78             }else{
 79                 if(up){
 80                     if(!down) t2 += 0;
 81                     else t2 += 1;
 82                 }else{
 83                     if(!down) t2 += 1;
 84                     else t2 += 1;
 85                 }
 86             } 
 87             //even odd odd even
 88             if(i & 1){
 89                 if(up){
 90                     if(!down) t3 += 0;
 91                     else t3 += 1;
 92                 }else{
 93                     if(!down) t3 += 1;
 94                     else t3 += 1;
 95                 }
 96             }else{
 97                 if(!up){
 98                     if(down) t3 += 0;
 99                     else t3 += 1;
100                 }else{
101                     if(down) t3 += 1;
102                     else t3 += 1;
103                 }
104             }
105             //even odd even odd 
106             if(i & 1){
107                 if(up){
108                     if(down) t4 += 0;
109                     else t4 += 1;
110                 }else{
111                     if(down) t4 += 1;
112                     else t4 += 1;
113                 }
114             }else{
115                 if(!up){
116                     if(!down) t4 += 0;
117                     else t4 += 1;
118                 }else{
119                     if(!down) t4 += 1;
120                     else t4 += 1;
121                 }
122             }
123         }
124 
125         cnt = min(min(t1, t2), min(t3, t4));
126     }
127 
128     //cout << "cnt = " << cnt << endl;
129     cout << cnt << endl;
130 }
131 
132 int main() {
133 
134     ios::sync_with_stdio(false);
135     cin.tie(0);
136     cout.tie(0);
137     solve();
138     //cout << "ok" << endl;
139     return 0;
140 }