蓝桥杯枚举算法精讲：从普通枚举到二进制枚举

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

#include<iostream>
#include<string>
using namespace std;

int date1, date2;
int cnt;

int main()
{
	cin >> date1 >> date2;
	for (int num = date1; num <= date2; num++)
	{
		//判断是否回文
		string s = to_string(num);
		bool pal = (s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4]);
		if (!pal) continue;
		//拆分年月日
		int year = num / 10000;
		int month = (num / 100) % 100;
		int day = num % 100;
		//判断月份是否合法
		if (month < 1 || month > 12) continue;
		//判断日期是否合法
		int maxDay = 0;
		if (month == 2)
		{
			bool isLeap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
			maxDay = isLeap ? 29 : 28;
		}
		else if (month == 4 || month == 6 || month == 9 || month == 11) {
			maxDay = 30;
		}
		else {
			maxDay = 31;
		}
		if (day >= 1 && day <= maxDay) cnt++;
	}
	cout << cnt << endl;
	return 0;
}

#include<iostream>
using namespace std;

int date1, date2;
int count;

bool isLeap(int year)
{
	return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

bool isLegal(int year, int month, int day)
{
	//检验月份是否合法
	if(month < 1 || month > 12) return false;
	//每月的最大天数
	int maxDay;
	switch(month)
	{
		case 1: case 3: case 5: case 7: case 8: case 10: case 12:
			maxDay = 31; break;
		case 4: case 6: case 9: case 11:
			maxDay = 30; break;
		case 2:
			maxDay = isLeap(year) ? 29 : 28; break;
		default:
			maxDay = 0;
	}
	//检验天数是否合法
	return (day >= 1 && day <= maxDay); 
}

int main()
{
	cin >> date1 >> date2;
	//确定年份区间
	int startYear = date1 / 10000;
	int endYear = date2 / 10000;
	for(int year = startYear; year <= endYear; year++)
	{
		//拆分年的每一位
		int y1 = year / 1000;
		int y2 = (year / 100) % 10;
		int y3 = (year / 10) % 10;
		int y4 = year % 10;
		//根据回文规则生成月和日 
		int month = y4 * 10 + y3;
		int day = y2 * 10 + y1;
		//判断日期是否合法
		if(!isLegal(year, month, day)) continue;
		//将日期与年份拼接为8位
		int trueDate = year * 10000 + month * 100 + day;
		if(trueDate >= date1 && trueDate <= date2)
		{
			count++;
		} 
	}
	cout << count << endl; 
	return 0;
}

//策略三：枚举所有的月日组合 
#include<iostream>
using namespace std;

int day[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int x, y;

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(num >= x && num <= y)
				ret++;
		}
	}
	cout << ret << endl;
	return 0;
}

#include<iostream>
using namespace std;

const int N = 1e4 + 10;
int n;
int a[N], b[N];

//a[1]不放雷 
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;
	}
} 

//a[1]放雷
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()
{
	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;
}

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

#include<iostream>
#include<cstring>
using namespace std;

const int N = 10;
int n = 5;
int a[N];//用二进制表示，来存储灯的状态 
int t[N];//备份a数组 

//统计当前行一共有多少个 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;
				//把第j位设为1，用一个整数存下整行需要翻转的灯 
				if(ch == '0') a[i] |= 1 << j;
			} 
	 	}
	 	//统计所有合法的按法中的最小值，将ret初始化为无穷大
		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;
}

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; // 灭灯→第j位设为1
    }
}

for(int st = 0; st < (1 << 5); st++) { // 枚举32种按法
    memcpy(t, a, sizeof a); // 备份初始状态
    int push = st; // 当前行的按法（先赋值第一行的按法）
    int cnt = 0; // 统计步数
}

for(int i = 0; i < 5; i++) { // 遍历每一行
    cnt += calc(push); // 统计当前行按的步数（后面讲calc）
    
    // 1. 翻转当前行自身+左右
    t[i] ^= push ^ (push << 1) ^ (push >> 1);
    // 2. 清空无效位
    t[i] &= (1 << 5) - 1;
    // 3. 翻转下一行+更新下一行按法
    if(i + 1 < 5) t[i+1] ^= push;
    push = t[i]; // 下一行按法=当前行剩余需要翻转的灯
}

int calc(int x) {
    int cnt = 0;
    while(x) {
        cnt++;
        x &= x - 1; // 消除最右边的1
    }
    return cnt;
}

if(t[n - 1] == 0) ret = min(ret, cnt); // 最后一行全亮则更新最小步数
// 输出结果
if(ret > 6) cout << -1 << endl;
else cout << ret << endl;

#include<iostream>
#include<cstring>
using namespace std;

const int N = 20;
int a[N], t[N];
int 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;
}