蓝桥杯学习-14子集枚举，二进制枚举

子集枚举

一、回溯3-子集枚举（递归实现指数型枚举）

一旦涉及选与不选，删和不删，留和不留-->两种状态-->就要想到子集枚举

例题1–递归实现指数型枚举19685

其实看不懂这个题目，好奇怪的题目。根据老师的解析来写。
大致理解为从1-n中，输出所有的组合数就对了。
我知道了，就是要按照题目的要求来，要先判断0不选，再判断1选。具体看代码更了解。

暴力做法

假设n=3.

public class Main {static int[] st = new int[10];//主逻辑函数public static void solve(){int n = 3;for (int i = 0; i <=1; i++) {//表示选或不选st[1] = i;for (int j = 0; j <= 1; j++) {//表示选或不选st[2] = j;for (int k = 0; k <= 1; k++) {//表示选或不选st[3] = k;for (int l = 1; l <= 3; l++) {//选中的输出if(st[l] == 1) System.out.print(l);}System.out.println();}}}}public static void main(String[] args) {solve();}
}

使用回溯dfs来实现

import java.util.Scanner;//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {static int n;static int[] st = new int[20];//递归函数public static void dfs(int u){if(u > n){//一次结束，输出结果for (int l = 1; l <= n; l++) {//选中的输出if(st[l] == 1) System.out.print(l + " ");}System.out.println();return;//这里要返回，因为？}for (int i = 0; i <= 1; i++) {st[u] = i;dfs(u + 1);//下一个数选或不选}}//主逻辑函数public static void solve(){Scanner sc = new Scanner(System.in);n = sc.nextInt();dfs(1);
//        for (int i = 0; i <=1; i++) {//表示选或不选
//            st[1] = i;
//            for (int j = 0; j <= 1; j++) {//表示选或不选
//                st[2] = j;
//                for (int k = 0; k <= 1; k++) {//表示选或不选
//                    st[3] = k;
//                    for (int l = 1; l <= 3; l++) {
//                        //选中的输出
//                        if(st[l] == 1) System.out.print(l);
//                    }
//                    System.out.println();
//                }
//            }
//        }}public static void main(String[] args) {solve();}
}

特别注意输出的格式问题，空格或者逗号特别注意，总因为这个没通过！！！

使用二进制枚举来实现

import java.util.*;
//s
public class Main {static int n;public static void solve(){Scanner sc = new Scanner(System.in);n = sc.nextInt();for (int i = 0; i < (1<<n); i++) {//0-7for (int j = n-1, k = 1; j >= 0; j--, k++) {if((i>>j&1) == 1){//选中System.out.print(k + " ");}}System.out.println();}}public static void main(String[] args) {solve();}
}

例题2–19880

例题3–蛋糕的美味值8664

package huisu;import java.util.Scanner;public class TasteCake {static int[] cake = new int[30];static int[] st = new int[30];static int n,k;static int max;//获得最大的总和public static void getMax(){int sum = 0;for (int i = 1; i <= n; i++) {if(st[i] == 1){//被选中并且美味值小于ksum += cake[i];}}//结束后返回目前最大值if(sum < k){max = Math.max(sum,max);}}//递归public static void dfs(int u){//u表示第几个蛋糕if(u > n){//表示n个蛋糕选与不选完了getMax();return;}for (int i = 0; i <= 1; i++) {//选与不选st[u] = i;dfs(u + 1);//下一个蛋糕}}//主逻辑函数public static void solve(){Scanner sc = new Scanner(System.in);//输入n，kn = sc.nextInt();k = sc.nextInt();//输入蛋糕的美味值for (int i = 1; i <= n; i++) {cake[i] = sc.nextInt();}//递归dfs(1);//输出结果System.out.println(max);}public static void main(String[] args) {solve();}
}

注意：
一定要看清题目啊，看题目和观察样例。
这里是要选出的蛋糕的总值小于k，而不是选出的每一个小于k的。
我第一次写理解为后面那一种，就错了。
其实看样例也能看出来。
题目真难理解。。。

例题4–luoguP1036

二、二进制枚举

思想就是把选与不选，留与不留等两种状态的问题转换为二进制的01，0表示不选，1表示选。

前提

位运算

位运算（&、|、^、~、>>、 | 菜鸟教程

计算机对二进制数据进行的运算（如加、减、乘、除）被称为位运算，即对二进制数的每一位进行操作的运算。与直接使用 +、-、*、/ 运算符相比，合理运用位运算可以显著提高代码在机器上的执行效率。

符号	描述	运算规则
&	与	两个位都为1时，结果才为1
|	或	两个位都为0时，结果才为0
^	异或	两个位相同为0，相异为1
~	取反	0变1，1变0
<<	左移	各二进位全部左移若干位，高位丢弃，低位补0
>>	右移	各二进位全部右移若干位，高位补0或符号位补齐

按位与运算符（&）

定义：对参与运算的两个数据的二进制位进行"与"运算。

运算规则：

0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1

总结：只有两位同时为1时，结果才为1，否则结果为0。

例如：3 & 5 即 0000 0011 & 0000 0101 = 0000 0001，因此 3 & 5 的值为1。

注意：负数按补码形式参与按位与运算。

用途：

1. 清零：如果想将一个单元清零，只要与一个各位都为零的数值相与，结果为零。

2. 取一个数的指定位：例如，取数 X = 1010 1110 的低4位，只需另找一个数 Y = 0000 1111，然后 X & Y = 0000 1110 即可得到 X 的指定位。

3. 判断奇偶：通过判断最未位是0还是1来决定奇偶，可以用 if ((a & 1) == 0) 代替 if (a % 2 == 0) 来判断 a 是否为偶数。

左移运算符（<<）

定义：将一个运算对象的各二进制位全部左移若干位，高位丢弃，低位补0。

例如，设 a = 1010 1110，a = a << 2 将 a 的二进制位左移2位、右补0，即得 a = 1011 1000。

若左移时舍弃的高位不包含1，则每左移一位，相当于该数乘以2。

右移运算符（>>）

定义：将一个数的各二进制位全部右移若干位，高位补0或补符号位，右边丢弃。

例如，a = a >> 2 将 a 的二进制位右移2位，左补0 或补符号位，具体取决于数的正负。

操作数每右移一位，相当于该数除以2。

思想

模板

package erjinzhimeiju;public class Test1 {public static void main(String[] args) {int n = 3;//n=3即三位二进制数//共有(1<<n)种排列方式（1为选中，0为没选）for (int i = 0; i < (1<<n); i++) {//0-7//循环每一种排列方式for (int j = n-1, k = 1; j >= 0; j--, k++) {//取出每种排列方式的最后一位数，并判断输出//为什么j从n-1到0呢，因为要从头开始判断二进制数的各个位。if((i>>j&1) == 1){  //取出右移后的最后一位//选中System.out.print(k + " ");}}System.out.println();}}
}
///
"C:\Program Files\Java\jdk1.8.0_201\bin\java.exe" 3 
2 
2 3 
1 
1 3 
1 2 
1 2 3 Process finished with exit code 0

二进制枚举的时间复杂度是n*2^n

例题–五子棋对弈lanqiao19694

思路，对于这种落子问题，虽然有两个主体，但只对一个主体来说，依旧是选与不选的情况，-->子集枚举-->二进制枚举/递归实现指数型枚举？
1.想要平局，肯定是白棋13个对黑棋12个。
2.用1表示白棋，用0表示黑棋。
3.用二进制枚举来枚举每一种情况，只有白棋即1的数量等于13时，才进行一个平局的判断。若是平局则ans加加
4.对于判断平局，因为用1表示白棋，用0表示黑棋。
所以只要横竖线以及主副对角线数组的值不要等于0或者5即可。
5.注意：循环的时候先将情况放在一维数组上，后面判断再放到二维数组进行判断。

package erjinzhimeiju;public class Test2 {static int n = 25;static int ans = 0;static int[] a = new int[30];//记录棋局static int[][] b = new int[10][10];//把棋局放在二维数组更好判断情况//判断在铺满棋盘的情况下是否为平局public static boolean check(){int pos = 0;//把棋局铺到棋盘上for (int i = 0; i < 5; i++) {for (int j = 0; j < 5; j++) {b[i][j] = a[pos++];}}for (int i = 0; i < 5; i++) {int col = 0;//行int row = 0;//列for (int j = 0; j < 5; j++) {col = col + b[i][j];row = row + b[j][i];}if (col == 0 || col == 5 || row == 0 || row == 5)return false;//不是平局}//横竖没问题判断对角线int b1 = 0;//主对角线int b2 = 0;//副对角线for (int i = 0; i < 5; i++) {b1 = b1 + b[i][i];b2 = b2 + b[i][4-i];}if(b1 == 0 || b1 == 5 || b2 == 0 || b2 == 5)return false;//不是平局//都判断完了就是平局return true;}//主逻辑函数public static void solve(){for (int i = 0; i < (1<<n); i++) {//共2^n种情况int s = 0;//记录白棋的个数for (int j = 0; j < n; j++) {if((i>>j&1) == 1){//选中s++;}a[j] = i>>j&1;}if(s != 13) continue;//不满13个肯定不能是平局//都铺满棋盘后判断是否有连线情况发生if(check()){ans++;}}System.out.println(ans);}public static void main(String[] args) {solve();}
}