简约一点写题解
这道题是很基础的一道递归题目（可能是太久没有Code，我卡了很久）
比较经典的做法，我们递归的时候决策无疑有两个，一个是选当前的数，另一个是不选。
用一个类似于堆的数组来记录当前选了那些数，关键代码如下
dfs(now + 1); //不选当前的数
a[++top] = now; //选当前的数
dfs(now + 1);
--top; //回溯
然后减枝比较基础，具体看代码吧。
我们普通的递归输出是降序的，和题目输出的要求不符，所以我们用一个数组存下答案，然后反向输出即可。（数据规模小，咋搞都能过。。。）
我们再来说一下思考题，不用递归如何做。
大家一定都想到了，就是用二进制来进行枚举，当然我们不能生枚举，要进行优化。
有两个东西，一个是lowbit，另一个是bitset。
lowbit相当于一个函数，返回的是一个数的二进制从最低位数第一个1带着后面的0的数（比如6的二进制是110，那么它的lowbit就是2 ，用二进制表示是10），这个可以用来快速把位数转化成数字。
也就是不断对一个数取lowbit，直到0，对每一个lowbit取2的对数+1即为相应位数代表的数字。
bitset是一种数据结构，类似于数组，本题使用是为了方便计算一个数二进制中1的个数，详细的使用方法Click Here，在此不进行赘述。
最后是代码。
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int n, top, m, len;
int a[30], ans[1000000];
bitset<30> s;
map <int, int> B;
struct NUM
{
vector <int> c;
}b[(1 << 21) + 1];
void dfs(int now)
{
if(top > m || top + (n - now + 1) < m) return;
if(now == n + 1)
{
for(int i = 1; i <= top; ++i)
ans[++len] = a[i];
// puts("");
return;
}
dfs(now + 1);
a[++top] = now;
dfs(now + 1);
--top;
}
bool cmp(NUM x, NUM y)
{
int now = 0;
while(x.c[now] == y.c[now]) ++now;
return x.c[now] < y.c[now];
}
#define lowbit(x) (x & (-x))
void dp()
{
len = 1;
B[1] = 0;
int tem = 2;
for(int i = 1; i <= 32; ++i)
{
B[tem] = i;
tem <<= 1;
}
#define lim ((1 << n) - 1)
for(int i = 0; i <= lim; ++i)
{
s |= i;
if(s.count() == m)
{
int temp = i;
while(temp)
{
b[len].c.push_back(B[lowbit(temp)] + 1);
temp ^= lowbit(temp);
}
++len;
}
s &= 0;
}
sort(b + 1, b + len, cmp);
for(int i = 1; i < len; ++i)
{
for(int j = 0; j < m; ++j)
printf("%d ", b[i].c[j]);
puts("");
}
#undef lim
}
#undef lowbit
int main()
{
scanf("%d%d", &n, &m);
/*
dfs(1);
for(int i = len; i >= 1; i -= m)
{
for(int j = m; j >= 1; --j)
printf("%d ", ans[i - j + 1]);
puts("");
}
*/
dp();
return 0;
}
2020 RP++
