【6.12校内test】T2 子集

这道题大概是这三道题里最简单的啦

但这阻止不了我废的脚步

---

【问题描述】 对于 n=4 时，对应的集合 s={4,3,2,1}，他的非空子集有 15 个依次如下：

{1} {2} {1,2} {3} {1,3} {2,3} {1,2,3} {4} {1,4} {2,4} {1,2,4} {3,4} {1,3,4} {2,3,4} {1,2,3,4}；

当 n=4 时，集合{4,3,2,1}的 15 个子集分别对应于 4 位二进制数：

{1}：0001；{2}：0010；{1,2}：0011；{3}：0100，…，{1,2,3,4}：1111。

把二进制数相对应的十进制数的 1,2,3，…,15 分别作为相应集合的编号。

如子集{1,2,4}对应的二进制数是 1011，相应的十进制数是 11，所以子集{1,2,4}的编号 为 11。

任务： 对于给定的 n 和 m，输出集合{1,2，…,n}的编号为 m 的子集。

【输入格式】

n,m

【输出格式】

集合的第 m 个子集的元素，元素从小到大输出，中间一个空格隔开。

【样例输入】

4 11

【样例输出】

1 2 4

【数据范围及约定】 100%的数据：n<=20,m<=2^n-1。

---

对于这个题，我还是游刃有余的，毕竟我的特长就是写循环嘛【灿烂】

其实感觉n压根没有什么用处，只需要把输入的数m转化成二进制看对应哪一位就好啦；

因为深受之前快速幂的影响，我是用“&”做的：

#include<bits/stdc++.h>

using namespace std;

int n,m,cnt,a[100];

int main(){
    scanf("%d%d",&n,&m);
    while(m){
        if(m&1) a[++cnt] = 1;
        else a[++cnt] = 0;
        m>>=1;
    }
    
    for(int i=1;i<=cnt;i++) if(a[i]) cout<<i<<" ";
    return 0;
}

嗯，没有了；