傳送門
題目：給定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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/3878.html
標籤：其他
上一篇：GMOJ 3569. 正則運算式