二进制枚举算法 cpp

3.2 二进制枚举用一个数的二进制表示中的0/1表示两种状态从而达到枚举的各种情况涉及位运算知识0/1表示状态的方法动态规划中的状态压缩dp中会继续使用二进制枚举也可使用递归实现位运算优先级不确定 加括号3.2.1 子集[!力扣]78. 子集中等给你一个整数数组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中的所有元素互不相同思路解法: 利用二进制枚举的方式, 把所有情况枚举出来[1,2,3]0 1 2 - 下标0~8 3 2 1 0 (下标)0 : 0 0 0 0 -[]1 : 0 0 0 1 -[1]2 : 0 0 1 0 -[2]3 : 0 0 1 1 -[1,2]4 : 0 1 0 0 -[3]5 : 0 1 0 1 -[1,3]6 : 0 1 1 0 -[2,3]7 : 0 1 1 1 -[1,2,3]8 : 1 1 1 1枚举 0 ~ 1 n-1 之间所有的数枚举枚举的数中1的位置, 把相应的数选出来代码classSolution{public:vectorvectorintsubsets(vectorintnums){vectorvectorintret;//统计最终结果intnnums.size();//计算数组长度//枚举所有状态// 等价与 × 2^n//(1 n) - 子集个数for(intst0;st(1n);st){//根据st状态,还原出要选的数vectorinttmp;//从当前选的子集//如果数组有 n 个元素那么二进制状态 st 就需要 n 个位来表示所有可能的选择情况。人为地“只用”它低位的 n 个位。for(inti0;in;i){if((sti)1)tmp.push_back(nums[i]);}ret.push_back(tmp);}returnret;}};[!补充知识]位运算中的左移 ()和右移 ()是计算机处理二进制数据最基础的操作。你可以把它们想象成在二进制数字的“队列”中移动位置。我们先把数字看成由0和1组成的串二进制。1. 左移运算符 ()口诀左移补零数值翻倍。操作规则把二进制数的所有位向左移动指定的位数。左边超出的位直接丢弃溢出。右边空出来的位全部补0。数学意义每向左移动1位相当于给这个数乘以 2。左移n nn位≈ \approx≈乘以2 n 2^n2n。举例演示假设我们要计算3 2把 3 左移 2 位。写出 3 的二进制假设用 8 位表示0000 0011向左移动 2 位原来的11往左跑了两格。右边空出的两个位置补0。变成0000 1100转换回十进制1100(二进制) 8 4 12 8 4 128412。验证数学规律3 × 2 2 3 × 4 12 3 \times 2^2 3 \times 4 123×223×412。完全一致回到你的代码1 n就是把数字1左移n位。1(二进制...001)左移n位后1后面多了n个0。二进制1后面跟n个0正是2 n 2^n2n的定义。2. 右移运算符 ()口诀右移丢弃数值减半。操作规则把二进制数的所有位向右移动指定的位数。右边超出的位直接丢弃就像切掉尾巴。左边空出来的位怎么补这取决于数字是正数还是负数但在你的子集代码中全是正数所以只需关注正数情况正数左边补0。负数通常左边补1这叫“算术右移”为了保持符号位不变但在算法题处理索引时通常不涉及负数。数学意义每向右移动1位相当于给这个数除以 2并向下取整整数除法。右移n nn位≈ \approx≈除以2 n 2^n2n。举例演示假设我们要计算13 2把 13 右移 2 位。写出 13 的二进制13 8 4 1 13 8 4 113841即0000 1101向右移动 2 位最右边的01被挤出去了丢弃。左边空出的两个位置补0。变成0000 0011转换回十进制11(二进制) 3 33。验证数学规律13 / 2 2 13 / 4 3.25 13 / 2^2 13 / 4 3.2513/2213/43.25。因为是整数运算小数部分扔掉结果就是3。完全一致3. 结合你的代码场景在你的子集代码中这两个运算符是配合使用的“黄金搭档”if((sti)1)这行代码的目的是检查变量st的第i位是不是 1。执行步骤拆解假设st 6(二进制110)我们要检查第1位 (i1) 是不是 1。(注意计算机里通常从右往左数第0位是最右边)st(110) 的位分布第2位:1第1位:1-- 我们想检查这个第0位:0右移 (st i)6 1把110向右移 1 位。最右边的0丢掉。变成011(十进制 3)。关键点原本在第 1 位的那个1现在被移到了第 0 位最右边。按位与 ( 1)现在的数是011。1的二进制是001。011 001011 001 ----- 001 (结果是 1)只要最后一位是 1结果就是 1如果是 0结果就是 0。判断结果是 1说明原数字的第 1 位确实是 1。条件成立选中该元素。总结图示操作符号动作方向空缺补什么数学等价例子 (二进制)左移← \leftarrow←右边补0× 2 n \times 2^n×2n0011(3) 1→ \to→0110(6)右移→ \rightarrow→左边补0(正数)÷ 2 n \div 2^n÷2n1101(13) 1→ \to→0110(6)一句话记忆左移是让数字变大后面加 0。右移是讓数字变小砍掉尾巴常用来把某一位“挪”到最右边去检查。3.2.2 费解的开关[!洛谷]P10449 费解的开关P10449 费解的开关 - 洛谷题目描述你玩过“拉灯”游戏吗25 2525盏灯排成一个5 × 5 5 \times 55×5的方形。每一个灯都有一个开关游戏者可以改变它的状态。每一步游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应和这个灯上下左右相邻的灯也要相应地改变其状态。我们用数字1 11表示一盏开着的灯用数字0 00表示关着的灯。下面这种状态10111 01101 10111 10000 11011在改变了最左上角的灯的状态后将变成01111 11101 10111 10000 11011再改变它正中间的灯后状态将变成01111 11001 11001 10100 11011给定一些游戏的初始状态编写程序判断游戏者是否可能在6 66步以内使所有的灯都变亮。输入格式第一行输入正整数n nn代表数据中共有n nn个待解决的游戏初始状态。以下若干行数据分为n nn组每组数据有5 55行每行5 55个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。输出格式一共输出n nn行数据每行有一个小于等于6 66的整数它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。对于某一个游戏初始状态若6 66步以内无法使所有灯变亮则输出-1。输入输出样例 #1输入 #13 00111 01011 10001 11010 11100 11101 11101 11110 11111 11111 01111 11111 11111 11111 11111输出 #13 2 -1说明/提示测试数据满足0 n ≤ 500 0 n \le 5000n≤500。思路:性质:每一盏灯, 最多只会点一次(点偶次没按 , 点奇次点1次) , 对于一盏灯而言, 只有按或者不按两种状态按法的先后顺序, 不影响最终的结果, 不用关心按的顺序, 只关心发生了什么第一行的按法(随机)确定之后, 后续灯的按法就跟着确定了(下一行必须要把上一行的灯全部点亮, 否则后面上一行就无法再次被点亮)解法:暴力枚举第一行所有的按法根据第一行的按法, 计算出当前行以及下一行被按之后的结果根据第一行的结果, 推导出第二行的按法; 重复2/3过程直到按倒最后一行, 然后判断所有的灯是否全亮如何实现:枚举第一行的所有算法二进制枚举所有的状态, 0~(15) - 1统计按了多少次二进制表示中如何表示中一共有多少个1 ---- cpp - lowbit存初始状态的方法用二进制表示来存储灯的初始状态, 存的时候, 把 0-1, 把 1- 0, 此时题目从全亮变成全灭 - 便于判断根据push这个按法, 可以用位运算的知识计算出档期那行a[i]以及下一行a[i1]被按之后的状态a[i] a[i] ^ push ^ (push 1) ^ (push 1)a[i] a[i] [(1n) - 1]a[i1] a[i1] ^ push如何求出下一行怎么按nextpush a[i]代码:#includebits/stdc.husingnamespacestd;constintN10;intn5;inta[N];//用二进制表示, 来储存灯的状态intt[N];// 备份 a 数组//计算 x 的二进制表示中一共有多少个 1intcalc(intx){intcnt0;while(x){cnt;xx-1;}returncnt;}intmain(){intT;cinT;while(T--){//多组测试时, 一定要注意清空之前的数据memset(a,0,sizeofa);for(inti0;in;i){for(intj0;jn;j){charch;cinch;//存成相反的if(ch0)a[i]|1j;}}intret0x3f3f3f3f;//统计所有合法的按法中的最小值//枚举完第一行所有的按法for(intst0;st(1n);st){memcpy(t,a,sizeofa);intpushst;//当前行的按法intcnt0;// 统计当前按法下一共按了多少次//依此计算后续行的结果以及按法for(inti0;in;i){cntcalc(push);//修改当前行被按的结果t[i]t[i]^push^(push1)^(push1);t[i](1n)-1;// 清空影响//修改下一行的状态t[i1]^push;pusht[i];}if(t[n-1]0)retmin(ret,cnt);}if(ret6)cout-1endl;elsecoutretendl;}return0;}