AcWing 92. 递归实现指数型枚举

文章目录

• 前言
• 代码
• 思路

前言

简单题只有那么一些，后面的稍微难一点点的题，自己写一道可能就要一个小时。现在不写之后需要的时候可能就来不及了。好吧。种一棵树最好的时间是十年前，对，假设我十年之前是信息竞赛选手，把这些题刷得非常熟练，现在可能就不需要写这些算法题了，但是肯定有其他问题要去做，所以现在努努力也不错。哈哈。不错不错。。。呜呜呜。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
void dfs(int u,int state){
    if(u==n){
        for(int i=0;i<n;i++){
            if(state>>i&1){
                cout<<i+1<<' ';
            }
        }
        cout<<endl;
        return;
    }
    dfs(u+1,state);
    dfs(u+1,state|1<<u);
}
int main(){
    cin>>n;
    dfs(0,0);
    return 0;
}

思路

数据范围比较小，就直接指数级别的做法就可以。二叉树这种感觉一般都是指数级别的做法，这里是一个深搜。另外这里代码里面有一些位运算。我之前查过好多次，现在又忘了，有点难受了。浅析位运算符（左移、右移、与、或、异或）。看一下这个博客复习一下位运算的知识。只能算复习吗哈哈哈。

奥对，之前简单记的就是右移就是除以 2 的若干次方，左移就是乘以 2 的若干次方。但是有一个问题，就是可能出现什么符号位改变之类的情况，我暂时不想深入研究。数字是转换成二进制之后进行移位操作的。左移和右移就是字面的意思，比较直观。& 符号，只有全真才是真，也就是说只有 1&1 才是 1，具体到上面那份代码里面就是两个数字都是 1 的时候才表示选择了这个数字，右移 i 位表示的是把第 i 位数字移动到个位，注意这里是二进制的数字，其实就是用二进制的数字表示布尔数组，看选不选该位数字，写的比较简单了，好像是什么状态压缩还是啥，好像是叫二进制压缩。题解里面说是状态压缩递归。具体叫啥我不是很感兴趣哈哈。所以这里的状态的数字的位数和十进制数字不太一样，奥也不是，十进制是从左边往右边，从大到小，但是这里是从右边到左边，从小到大。别人的注解。奥，那我前面理解错了，这里的 state 表示的是 u 这个数字选不选，选的话做相应的改变。

| 这个只要有一个 1 ，表达式就全是 1 ，也比较好理解，关键是这个：左移的优先级比 | 的优先级高。1<<u 表示的是让 u 这一位变成 1 ，具体的例子可能好理解一些。假设二进制数字是 8 位数，然后最开始 state=1000 0000 ，这里写成的是二进制的形式，方便理解，在代码里面其实是十进制数字。然后假设 u=3 ，那么 1<<3 其实就是 0000 1000 ，然后 0000 1000 | 1000 0000=1000 1000 ，表示选这一位，但是有点奇怪，因为我们选的 u==3 ，但是这个改变的好像是从右边往左边数 3 位。嗷嗷，前面 state>>i&1 也是从右边往左边数来看的，那就懂了。

比如说 0000 0011 ，表示选前面两个数，1100 0000 表示选最后面两个数，应该是这样。位运算还是有点炫技了。好难。