【蓝桥杯每日一题】3.17

Alt

🏝️专栏：【蓝桥杯备篇】
🌅主页： 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也正常，明天我们来点有意思的算法，前缀和和差分

"赛场上键盘冒火星？这是系统在为我颁发'钢铁直男'勋章！"

“啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊，烂命一条就是干啊，冲冲冲”