?

🏝?專欄：?【藍橋杯備篇】
🌅主頁：?f狐o貍x

他們說內存泄漏是bug，我說這是系統在逼我進化成SSR級程序員

---

? ? ? ? OK來吧，不多廢話，今天來點有難度的：二進制枚舉

? ? ? ? 二進制枚舉，就是如果題目中描述的情況只有兩種，就可以有 0 和 1 來表示，例如我們之前做過的掃雷游戲，每一個格子里面只有兩種情況，就是有雷和無雷，就可以有 0 和 1 來表示。這樣就可以使我們的枚舉大大提高效率

3.12 二進制枚舉

一、子集

? ? ? ? 題目鏈接：

? ? ? ? 78.子集

? ? ? ? 題目描述：

? ? ? ? 解題思路：

? ? ? ? 例如示例一的 [ 1, 2, 3 ]，他的子集就是[ 1?],?[ 2 ],?[ 3 ],?[ 1, 2 ],?[ 1, 3 ],?[ 2, 3 ], [ 1, 2, 3 ]，其實集合里面的每個元素都有兩種情況，出現和不出現，此時我們就可以用二進制來表示，如圖：

? ? ? ? 解題代碼：

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ret;int n = nums.size();for(int st = 0; st < (1 << n); st++){vector<int> tmp;for(int i = 0; i < n; i++){if((st >> i) & 1) tmp.push_back(nums[i]); }ret.push_back(tmp);}return ret;}
};

二、費解的開關

? ? ? ? 這題非常考驗我們的位運算的能力，如果看不懂的話可以私信煮波，煮波給你細細講解（主要是這里懶了）

? ? ? ? 題目鏈接：

????????P10449 費解的開關

? ? ? ? 題目描述：

? ? ? ? 解題思路：

? ? ? ? 對于每盞燈而言，只有亮與滅兩種情況，因此可以用二進制存儲關系，而且每排其實都是五個數字，因此我們可以將他每一排存的二進制變為一個十進制的數字來存儲，在通過位運算來改變每一盞燈的亮滅情況，即可破解此題

? ? ? ? 解題代碼：

#include <iostream>
#include <cstring>
using namespace std;const int N = 10;int a[N], t[N];int calc(int push)
{int cnt = 0;while (push){cnt++;push &= (push - 1);}return cnt;
}int main()
{int n; cin >> n;while (n--){// 清空上一組的數據memset(a, 0, sizeof a);// 輸入數據，每一排用十進制數字存儲二進制for (int i = 0; i < 5; i++){for (int j = 0; j < 5; j++){char ch; cin >> ch;if (ch == '0') a[i] |= (1 << j);}}int ret = 0x3f3f3f3f;// 枚舉第一排的情況for (int st = 0; st < (1 << 5); st++){memcpy(t, a, sizeof a);int push = st;int cnt = 0; // 記錄按了幾次for (int i = 0; i < 5; i++){cnt += calc(push);t[i] = t[i] ^ push ^ (push << 1) ^ (push >> 1);t[i] &= (1 << 5) - 1; // 清除影響t[i + 1] ^= push; // 修改下一行的狀態push = t[i];}if (t[4] == 0) ret = min(ret, cnt);}if (ret > 6) cout << "-1" << endl;else cout << ret << endl;}return 0;
}

三、Even Parity

? ? ? ? 這題和上面那題“費解的開關”類似，就不多廢話了

? ? ? ? 題目鏈接：

???????UVA11464 Even Parity - 洛谷

? ? ? ? 題目描述：

? ? ? ? 解題思路：

? ? ? ? 一樣的都是利用二進制來存儲數據，再巧妙地運用位運算解決題目

? ? ? ? 解題代碼：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
int n;
int a[N]; // ??進制存儲狀態
int t[N]; // 備份// 判斷 x->y 是否合法
// 返回 -1，表?不合法
// 其余的數，表?合法，并且表? 0->1 的次數
int calc(int x, int y)
{int sum = 0; for (int i = 0; i < n; i++){if (((x >> i) & 1) == 0 && ((y >> i) & 1) == 1) sum++;if (((x >> i) & 1) == 1 && ((y >> i) & 1) == 0) return -1;}return sum;
}
int solve()
{int ret = 0x3f3f3f3f; // 記錄最?的改變次數// 枚舉第??的最終狀態for (int st = 0; st < (1 << n); st++){memcpy(t, a, sizeof a);int change = st;int cnt = 0; // 統計 0->1 的次數bool flag = 1;for (int i = 1; i <= n; i++){// 先判斷 change 是否合法int c = calc(t[i], change);if (c == -1){flag = 0;break;}cnt += c; // 累加次數// 當前?的最終狀態t[i] = change;// 計算下??的最終狀態change = t[i - 1] ^ (t[i] << 1) ^ (t[i] >> 1);change &= (1 << n) - 1;}if (flag) ret = min(ret, cnt);}if (ret == 0x3f3f3f3f) return -1;else return ret;
}int main()
{int T; cin >> T;for (int k = 1; k <= T; k++){// 多組測試數據，記得清空memset(a, 0, sizeof a);cin >> n;for (int i = 1; i <= n; i++) // 避免越界訪問{for (int j = 0; j < n; j++){int x; cin >> x;if (x) a[i] |= 1 << j;}}printf("Case %d: %d\n", k, solve());}return 0;
}

? ? ? ? 最后這兩個題有些難，各位稍安勿躁，刷小怪的時候偶爾遇到點BOSS也正常，明天我們來點有意思的算法，前綴和和差分

????????"賽場上鍵盤冒火星？這是系統在為我頒發'鋼鐵直男'勛章！"

“啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊，爛命一條就是干啊，沖沖沖”