一、普通枚举
P1003 [NOIP 2011 提高组] 铺地毯 - 洛谷
题目描述
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 n 张地毯，编号从 1 到 n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
输入格式
输入共 n+2 行。
第一行，一个整数 n，表示总共有 n 张地毯。
接下来的 n 行中，第 i+1 行表示编号 i 的地毯的信息，包含四个整数 a,b,g,k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标 (a,b) 以及地毯在 x 轴和 y 轴方向的长度。
第 n+2 行包含两个整数 x 和 y，表示所求的地面的点的坐标 (x,y)。
输出格式
输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
输入输出样例
输入 #1复制
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
输出 #1复制
3
输入 #2复制
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5
输出 #2复制
-1
说明/提示
【样例解释 1】
如下图，1 号地毯用实线表示，2 号地毯用虚线表示，3 号用双实线表示，覆盖点 (2,2) 的最上面一张地毯是 3 号地毯。
【数据范围】
对于 30% 的数据，有 n≤2。
对于 50% 的数据，0≤a,b,g,k≤100。
对于 100% 的数据，有 0≤n≤104, 0≤a,b,g,k≤105。
noip2011 提高组 day1 第 1 题。
思路：从后往前枚举所有的地毯，判断是否覆盖题目中给的点。
#include<iostream> using namespace std; const int N=1e5+10; int x[N],y[N],len_x[N],len_y[N]; int solve(int n,int a,int b) { while(n) { if(a>=x[n] && a<=(x[n]+len_x[n]) && b>=y[n] && b<=(y[n]+len_y[n])) return n; n--; } return -1; } int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>x[i]>>y[i]>>len_x[i]>>len_y[i]; int a,b; cin>>a>>b; int ret=solve(n,a,b); cout<<ret; return 0; }二、二进制枚举
1.子集
LCR 079. 子集 - 力扣（LeetCode）
给定一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。
示例 1：
输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素互不相同
二进制枚举：用一个数二进制表示中的0/1表示两种状态，从而达到枚举各种情况。
·利用二进制枚举时，会用到一些位运算的知识。不熟悉同学需要去补一下位运算相关的知识。
·关于用二进制中的0/1表示状态这种方法，会在动态规划章节中的状态压缩dp中继续使用到。
·二进制枚举的方式也可以用递归实现，后续递归课程中会再讲到。
解法：利用二进制枚举的方式，把所有情况都枚举出来。
用0表示不选某一位的数，用1表示选择某一位的数。
思路：
1.枚举0～1<<n-1之间所有的数。
2.枚举枚举的数中二进制表示中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; for(int i=0;i<n;i++) { //如果右移i位的结果末尾是1，就选择 if((st>>i)&1) tmp.push_back(nums[i]); } ret.push_back(tmp); } return ret; } };2.P10449 费解的开关 - 洛谷
题目描述
你玩过“拉灯”游戏吗？
25 盏灯排成一个 5×5 的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。
下面这种状态
10111 01101 10111 10000 11011在改变了最左上角的灯的状态后将变成：
01111 11101 10111 10000 11011再改变它正中间的灯后状态将变成：
01111 11001 11001 10100 11011给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。
输入格式
第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出-1。
输入输出样例
输入 #1复制
3 00111 01011 10001 11010 11100 11101 11101 11110 11111 11111 01111 11111 11111 11111 11111
输出 #1复制
3 2 -1
说明/提示
测试数据满足 0<n≤500。
性质：
1.每一盏灯，最多只会点一次，对于一盏灯而言，只有按或者不按两种状态。
2.按法的先后顺序，是不影响最终结果的。不用关心按的顺序，只用关心按了什么。
3.第一行的按法确定之后，后续灯的按法就跟着确定了，《扫雷》
解法：
1.暴力枚举第一行所有的按法；
2.根据第一行的按法，计算出当前行以及下一行被按之后的结果；
3.根据第一行的结果，推导出第二行的按法：重复2/3过程
4.直到按到最后一行，然后判断所有灯是否全亮。
如何实现这个解法？
1.如何枚举出第一行所有的按法呢？
用二进制枚举所有的状态st，0~（1<<5）-1。
2.如何计算出，一共按了多少次？
计算二进制表示中，有多少个1。
3.用二进制表示，来存储灯的初始状态
存的时候，把0->1，把1->0，此时，题目就从全亮变成全灭。
4.如何根据push这个按法，计算出当前行a[i]以及下一行a[i+1]被按之后的状态？
可以用位运算的知识，快速计算出被按之后的状态。
1）如果按照00100这个按法，将就将方框里的数字由0变1，由1变0。
2）正好就是 x ^ 1 ，因为 1 ^ 0 = 1 ，1 ^ 1 = 0 。
3）ai = ai ^ push ^ ( push << 1 ) ^ ( push >> 1 )
^ push : 把当前这个开关的二进制表示由1变0，由0变1
^ push << 1 :把左边这个开关的二进制表示由1变0，由0变1
^ push >> 1 :把右边这个开关的二进制表示由1变0，由0变1
4）如果push最高位是1，如果左移的话，会向高位移动，会把 a [ i ] 最高位下一位（红色圈）修改成1。但这一位是无效的位置，我们存储位置时，只要在前五位存储即可，所以要把这一位清空。
a [ i ] = a [ i ] & ( ( 1 << n ) -1 )
a [ i ] = 1 0 1 11
1<<n-1:1 1 1 1 0
result : 1 0 1 10
正好把多余的1变成0了。
5）下一行被按后的状态：
a [ i + 1 ] = a [ i + 1 ] ^ push
5.如何求出下一行怎末按？
next_push=a [ i ]
