NO.58十六届蓝桥杯备战|基础算法-枚举|普通枚举|二进制枚举|铺地毯|回文日期|扫雷|子集|费解的开关|Even Parity(C++)

枚举

顾名思义，就是把所有情况全都罗列出来，然后找出符合题⽬要求的那⼀个。因此，枚举是⼀种纯暴⼒的算法。
⼀般情况下，枚举策略都是会超时的。此时要先根据题⽬的数据范围来判断暴⼒枚举是否可以通过。
使⽤枚举策略时，重点思考枚举的对象（枚举什么），枚举的顺序（正序还是逆序），以及枚举的⽅式（普通枚举？递归枚举？⼆进制枚举）

普通枚举

P1003 [NOIP 2011 提高组] 铺地毯 - 洛谷

枚举所有的地毯，判断哪⼀个地毯能够覆盖(x, y)这个位置。
优化枚举⽅式：

• 因为我们要的是最后⼀个能够覆盖x，y位置的地毯，那么逆序枚举所有的地毯，第⼀次找到覆盖x，y位置的就是结果；
• 如果从前往后枚举，我们⾄少要把所有地毯都枚举完，才能知道最终结果。
  

a要小于等于x
b要小于等于y
x要小于等于a+g
y要小于等于b+k

#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 10;
int n;
int a[N], b[N], g[N], k[N];
int x, y;int find()
{for (int i = n; i >= 1; i--){if (a[i] <= x && b[i] <= y && a[i] + g[i] >= x && b[i] + k[i] >= y){return i;}}return -1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> g[i] >> k[i];cin >> x >> y;cout << find() << endl;return 0;
}

P2010 [NOIP 2016 普及组] 回文日期 - 洛谷

方法一：枚举x-y之间所有的数字，然后判断是否回文，如果回文，就拆分成年月日，判断是否是合法日期即可
方法二：仅需枚举年份，因为每个年份对应的回文日期只有一个，拆分成回文形式的月日，然后判断是否合法即可
方法三：枚举所有的月和日，然后拼接成相应的年份，判断是否合法

#include <bits/stdc++.h>
using namespace std;int x, y;
int day[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main()
{ios::sync_with_stdio(false);cin.tie(0);int ret = 0;cin >> x >> y;//枚举月日的组合for (int i = 1; i <= 12; i++){for (int j = 1; j <= day[i]; j++){int k = j % 10 * 1000 + j / 10 * 100 + i % 10 * 10 + i / 10;int num = k * 10000 + i * 100 + j;if (x <= num && num <= y) ret++;}}cout << ret << endl;return 0;
}

P2327 [SCOI2005] 扫雷 - 洛谷

我们发现，当第⼀列中，第⼀⾏的⼩格⼦的状态确定了之后，其实后续⾏的状态也跟着固定下来。⽽第⼀列中，第⼀⾏的状态要么有雷，要么没有雷，所以最终的答案就在0, 1, 2中。
因此，我们枚举第⼀列中，第⼀⾏的两种状态：要么有雷，要么没雷。然后依次计算剩下⾏的值，看看是否能满⾜所给的数据。

#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 10;int n;
int a[N], b[N];int check1()
{a[1] = 0;for (int i = 2; i <= n+1; i++){a[i] = b[i-1] - a[i-1] - a[i-2];if (a[i] < 0 || a[i] > 1) return 0;}if (a[n+1] == 0) return 1;else return 0;
}int check2()
{a[1] = 1;for (int i = 2; i <= n+1; i++){a[i] = b[i-1] - a[i-1] - a[i-2];if (a[i] < 0 || a[i] > 1) return 0;}if (a[n+1] == 0) return 1;else return 0;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> b[i];int ret = 0;ret += check1(); //a[1]不放地雷ret += check2(); //a[1]放地雷cout << ret << endl;return 0;
}

⼆进制枚举

⼆进制枚举：⽤⼀个数⼆进制表⽰中的0/1 表⽰两种状态，从⽽达到枚举各种情况。

• 利⽤⼆进制枚举时，会⽤到⼀些位运算的知识。
• ⼆进制枚举的⽅式也可以⽤递归实现。

78. 子集 - 力扣（LeetCode）

枚举1 ~1<<n之间所有的数，每⼀个数的⼆进制中1的位置可以表⽰数组中对应位置选上该元素。那么1 ~1<<n就可以枚举出原数组中所有的⼦集。
根据枚举的每⼀个状态，选出原数组中对应的元素，然后存在结果数组中

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++){//根据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 费解的开关 - 洛谷

在这个「拉灯游戏」中我们可以得到「三个性质」：

1. 每⼀个开关「最多只会被按⼀次」。因为按两次及以上是没有意义的，只会让按的次数增多；
2. 按每⼀个开关的「先后顺序」不会影响最后的结果。可以想象，当所有开关按的⽅式确定之后，每⼀个开关被改变的「次数」也就被确定了，也就是说不管你先按谁后按谁，改变的次数是固定的，那么结果就是固定的；
3. 如果「确定了第⼀⾏」的按法，后续⾏的按法就也固定下来了。因为第⼀⾏的按法固定之后，第⼆⾏的按法需要把第⼀⾏「全部点亮」；当第⼆⾏的按法确定之后，第三⾏的按法需要把第⼆⾏「全部点亮」…，依次类推，后续⾏的按法就都确定下来了。

核心思路

有了这三个性质，那么我们的核⼼思路就是：

1. 暴⼒「枚举」第⼀⾏的所有按法；
2. 然后根据第⼀⾏的按法，计算出当前⾏以及下⼀⾏被按之后的结果；
3. 根据上⼀⾏被按了之后的状态，确定当前⾏的按法，然后重复2 操作；
4. 最后判断最后⼀⾏是否全部都亮。
   接下来考虑每⼀步如何「优美」的实现。为了⽅便起⻅，我们读取原数据的时候把所有的1当成0，把所有的0当成1，这样题⽬要求的全亮，就变成全灭，后续各种操作都⾮常舒服。

实现

1. 读取数据时，我们直接⽤「⼆进制」存每⼀⾏的状态：
   ⽐如：00101 ，对应的就是5。这样我们就可以⽤「位运算」快速实现⼀些操作，⽅便之处会在后续算法原理中体现；
2. 枚举第⼀⾏所有的按法：
   枚举1~ (1<<5)-1之间所有的数，如果⼆进制表⽰中第i位是1就表⽰第⼀⾏的第i位被按；
3. 如何计算某个状态下，⼀共按了多少次：
   相当于计算⼆进制表⽰中11 的个数，常规操作
4. 如何优美的根据当前⾏的按法push，得到当前⾏a[i]以及下⼀⾏a[i+1]被按push了之后的状态：
   a. 当前⾏：被按的位置会影响「当前位置」以及「左右两个位置」的状态，如果状态是0会被变
   成1，如果状态是1会被变成0，不正好是x^1之后的结果么？⼜因为会改变「当前位置」以及「左右两个位置」，所以a[i]的最终状态就是：

a[i] = a[i] ^ push ^ (push<<1) ^ (push>>1);

其中，push<<1有可能会让第5位变成1，这⼀位是⼀个「⾮法」的位置，有可能影响后续判断，我们要「截断⾼位」：(push<<1)^((1<<5)-1)；
最终：

a[i] = a[i] ^ push ^ (push>>1) ^ ((push << 1) ^ ((1 << 5)-1));

b. 下⼀⾏：当前⾏的push只会对下⼀⾏「对应的位置」做修改：a[i + 1] = a[i + 1]^ push; 发现没，使⽤「⼆进制」表⽰存状态之后，改变的时候只⽤使⽤「位运算」即可，不然还要写for循环来改变每⼀个位置的值
5. 求出当前⾏被按了之后的结果，如何求出下⼀⾏的按法：
巨简单，当前⾏怎么亮，下⼀⾏就怎么按，这样就可以把当前⾏亮的位置暗灭：nextpush = a[i] ，注意此时的a[i]是被按了之后的状态。
6. 判断最后⼀⾏是否全灭：
判断a[4] == 0即可，我们开头「反着存储」的优势就体现出来了

#include <bits/stdc++.h>
using namespace std;const int N = 10;
int n = 5;
int a[N]; //用二进制存储状态
int t[N];// 计算1的个数
int calc(int x)
{int cnt = 0;while (x){cnt++;x &= x - 1;}return cnt;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int T; cin >> T;while (T--){memset(a, 0, sizeof a);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){char ch; cin >> ch;if (ch == '0') a[i] |= 1 << j;}}int ret = 0x3f3f3f3f; //统计所有合法的按法的最小值//枚举第一行所有方法for (int st = 0; st < (1 << n); st++){memcpy(t, a, sizeof a);int push = st;//记录当前行的按法int cnt = 0; //统计次数//依次计算后续行的结果for (int i = 0; i < n; i++){cnt += calc(push);//修改当前行被按的结果t[i] = t[i] ^ push ^ (push << 1) ^ (push >> 1);t[i] &= (1 << n) - 1;  //清空影响//修改下一行t[i+1] ^= push;//下一行按法push = t[i];}if (t[n-1] == 0) ret = min(ret, cnt);}if (ret > 6) cout << -1 << endl;else cout << ret << endl;}return 0;
}

UVA11464 Even Parity - 洛谷

1. 每⼀个0 如果变成1 ，只会「变⼀次」；
2. 当第⼀⾏的「最终状态」确定之后，第⼆⾏的「最终状态」也会确定。所以我们可以「暴⼒枚举」第⼀⾏的最终状态，在这个最终状态「合法」的前提下，「递推」出来第⼆⾏的状态，「以此类推」下去。
   考虑⼀下⼏个问题：
3. 如何枚举第⼀⾏所有的「最终状态」st ：
   枚举1 ∼ (1 << n) - 1 之间所有的数，「每⼀个数」就是第⼀⾏的最终状态；
4. 由于本题只能0 变1 ，所以我们还要「判断」每⼀⾏的最终状态y 「是否合法」：
   很简单，⽐较初始状态x以及最终状态y中「⼆进制表⽰的每⼀位」，如果是0变1 ，就是
   「合法」操作，计数；如果是1变0 ，「⾮法」操作，直接「跳出本次循环」，枚举第⼀⾏的下
   ⼀个状态；
5. 当前⾏的最终状态a[i]确定之后，如何「递推」下⼀⾏的最终状态a[i + 1]：
   规则是当前位置「上下左右」1的个数之和是「偶数」，根据「异或」运算「⽆进位相加」的特
   性，正好就是上下左右位置「异或」的结果是0 。那么下⼀⾏对应位置的状态就是「当前⾏右移⼀位」与「当前⾏左移⼀位」与「上⼀⾏对应位置」异或的结果：

a[i + 1] = (a[i] >> 1) ^ (a[i] << 1) ^ a[i - 1];  

其中a[i] << 1 会造成不合法的位置是1的情况，注意「⾼位截断」：

(a[i] << 1) & ((1 << n) - 1)

#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;
}