蓝桥备赛（23）算法篇【枚举】
一、枚举
顾名思义 ， 就是把所有情况所有罗列出来 ， 然后找出符合题目要求的哪一个 。因此 ， 枚举是一种纯暴力的算法 。一般情况下 ， 枚举策略都是会超时的 ， 此时要先根据题目的数据范围来判断暴力枚举是否可以通过 ， 如果不行的话 ， 就需要用到后面介绍的各种算法来优化 （比如二分、双指针 、前缀 、 差分等）
使用枚举策略时 ， 重点思考枚举对象（枚举什么），枚举的顺序（正序还是逆序） ， 以及枚举的方式（普通枚举？递归枚举？二进制枚举？）
二、普通枚举
2.1 铺地毯
P1003 [NOIP 2011 提高组] 铺地毯 - 洛谷
#include <iostream>
using namespace std;
const int N = 1e4 + 10;
int a[N],b[N],g[N],k[N];
int x,y;
int n;
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()
{
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.2 回文日期
P2010 [NOIP 2016 普及组] 回文日期 - 洛谷
#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;
}2.3 扫雷
P2327 [SCOI2005] 扫雷 - 洛谷
#include <iostream>
using namespace std;
const int N = 1e4 + 10;
int a[N],b[N];
int n;
//a[1]不放地雷
int check1()
{
a[1] = 0;
for(int i = 2;i<=n+1;i++)
{
a[i] = b[i-1] - a[i-2] - a[i-1];
if(a[i] < 0 || a[i] >1)return 0;
}
if(a[n+1]==0)return 1;
else return 0;
}
//a[1]放地雷
int check2()
{
a[1] = 1;
for(int i = 2;i<=n+1;i++)
{
a[i] = b[i-1] - a[i-2] - a[i-1];
if(a[i] < 0 || a[i] >1)return 0;
}
if(a[n+1]==0)return 1;
else return 0;
}
int main()
{
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 表示两种情况 ， 从而达到枚举各种情况
1）利用二进制枚举的时候 ， 会用到一些位运算的知识 。
如果不是很了解，
蓝桥备赛（八）- 位运算和操作符属性（上）-CSDN博客
蓝桥备赛（八）- 位运算和操作符属性（上）-CSDN博客
2）关于二进制中的 0/1 表示状态这种方法 ， 会在动态规划章节中的状态压缩 dp 中继续用到
3）二进制枚举的方式也可以用递归实现 ， 后续递归章节中会介绍噢~
3.1 子集
78. 子集 - 力扣（LeetCode）
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;
}
};3.2 费解的开关
P10449 费解的开关 - 洛谷
#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.3 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;
//第一行必须放在下标为1，否则存在越界行为
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;
}这道题目是收录UVa（国外的OJ平台），需要洛谷绑定相关账号