当前位置：首页 > news >正文

【算法】枚举

news 来源：原创 2025/6/18 9:58:20

枚举

普通枚举
- 1.铺地毯
- 2.回文日期
- 3.扫雷
二进制枚举
- 1.子集
- 2.费解的开关
- 3.Even Parity

顾名思义，就是把所有情况全都罗列出来，然后找出符合题目要求的那一个。因此，枚举是一种纯暴力的算法。
一般情况下，枚举策略都是会超时的。此时要先根据题目的数据范围来判断暴力枚举是否可以通过。如果不行的话，就要进行优化（比如⼆分，双指针，前缀和与差分等）。使用枚举策略时，重点思考枚举的对象（枚举什么），枚举的顺序（正序还是逆序），以及枚举的方式（普通枚举？递归枚举？⼆进制枚举）

普通枚举

1.铺地毯

P1003 [NOIP2011 提高组] 铺地毯

在这里插入图片描述

解法：枚举

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

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

#include<iostream>
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(x >= a[i] && y >= b[i] && x <= a[i] + g[i] && y <= b[i] + k[i]){return i;}}return -1;
}int main()
{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;
}

2.回文日期

P2010 [NOIP2016 普及组] 回文日期

在这里插入图片描述

解法：枚举

枚举0~99999999之间的所有数字，判断是否回文，若回文，求出对应的月日，判断是否合法。
枚举0~9999之间的年份，求出构成回文形式的月日，判断是否合法。
枚举所有月日的组合，然后根据回文的特性推出年份，然后比较这个数字时候在题目给定的区间内。

#include<iostream>
using namespace std;int x, y;
int day[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main()
{cin >> x >> y;int ret = 0;//枚举所有月日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;
}

3.扫雷

P2327 [SCOI2005] 扫雷

在这里插入图片描述

解法：枚举

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

#include<iostream>
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;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;return 0;
}int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> b[i];int ret = 0;ret += check1(); ret += check2();cout << ret << endl;
}

二进制枚举

二进制枚举：用一个数的二进制中的 0/1 表示两种状态，从而达到枚举各种情况。

1.子集

子集

在这里插入图片描述

解法：枚举

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

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;// 根据 st 的状态，还原出要选的数 for(int i = 0; i < n; i++){if((st >> i) & 1) tmp.push_back(nums[i]);}ret.push_back(tmp);}return ret;}
};

2.费解的开关

P10449 费解的开关

在这里插入图片描述

解法：枚举

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

每一个开关「最多只会被按一次」。因为按两次及以上是没有意义的，只会让按的次数增多；
按每一个开关的「先后顺序」不会影响最后的结果。可以想象，当所有开关按的方式确定之后，每一个开关被改变的「次数」也就被确定了，也就是说不管你先按谁后按谁，改变的次数是固定的，那么结果就是固定的。
如果「确定了第一行」的按法，后续行的按法就也固定下来了（这里可以参考《扫雷》这道题，有相似点）。因为第一行的按法固定之后，第二行的按法需要把第一行「全部点亮」。当第二行的按法确定之后，第三行的按法需要把第二行「全部点亮」…，依次类推，后续行的按法就都确定下来了。

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

暴力「枚举」第一行的所有按法；
然后根据第一行的按法，计算出当前行以及下一行被按之后的结果。
根据上一行被按了之后的状态，确定当前行的按法，然后重复 2 操作。
最后判断最后一行是否全部都亮。

接下来考虑每一步如何「优美」的实现。为了方便起见，我们读取原数据的时候把所有的 1 当成 0 ，把所有的 0 当成 1，这样题目要求的全亮，就变成全灭，后续各种操作都非常舒服。

读取数据时，我们直接用「⼆进制」存每一行的状态：比如：00101，对应的就是 5 。这样我们就可以用「位运算」快速实现一些操作，方便之处会在后续算法原理中体现。
枚举第一行所有的按法：枚举 1 ~ (1 << 5) 之间所有的数，如果二进制表示中第 i 位是 1 就表示第一行的第 i 位被按。
如何计算某个状态下，一共按了多少次：相当于计算二进制表示中 1 的个数。
如何优美的根据当前行的按法 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 循环来改变每一个位置的值。
求出当前行被按了之后的结果，如何求出下一行的按法：巨简单，当前行怎么亮，下一行就怎么按，这样就可以把当前行亮的位置暗灭：nextpush = a[i]。注意此时的 a[i] 是被按了之后的状态。
判断最后一行是否全灭：判断 a[4] == 0 即可，我们开头「反着存储」的优势就体现出来了。

#include <iostream>
#include <cstring>
using namespace std;const int N = 10;int n = 5;
int a[N];  //用二进制表示灯的存储状态
int t[N];  //备份 a 数组//计算 x 的二进制表示中一共有多少个1 
int calc(int x)
{int cnt = 0;while(x){cnt++;x &= x - 1;}return cnt;
} int main()
{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;
}

3.Even Parity

Even Parity

在这里插入图片描述

解法：模拟

每一个 0 如果变成 1，只「变一次」。
当第一行的「最终状态」确定之后，第二行的「最终状态」也会确定。所以我们可以「暴力枚举」第一行的最终状态，在这个最终状态「合法」的前提下，「递推」出来第二行的状态，「以此类推」下去。

考虑以下几个问题：
3. 如何枚举第一行所有的「最终状态」st：枚举 0 ~ (1 << n) 之间所有的数，「每一个数」就是第一行的最终状态。
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;
}

枚举

普通枚举

1.铺地毯

2.回文日期

3.扫雷

二进制枚举

1.子集

2.费解的开关

3.Even Parity

相关文章：