题目大意:
从 $1∼n$ 这 $n$ 个整数中随机选出 $m$ 个,输出所有可能的选择方案。
解题方法:
这题分为如下几个步骤:
- 用位运算找到所有满足条件的情况
- 将其转化为字符串,进行字典序排序
完事了。
完整代码,时间复杂度:$O(2^nn)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 60;
int n, m, cnt;
char a[200020][N];
string s[200020];
int main()
{
cin >> n >> m;
for (int i = 0; i < 1 << n; i ++ ) {
int x = 0;
for (int j = 0; j < n; j ++ )
if (i >> j & 1)
x ++ ;
if (x == m) {
cnt ++;
for (int j = 0; j < n; j ++ ) {
a[cnt][j] = '0';
a[cnt][j] += (i >> j) & 1;
}
s[cnt] = a[cnt];
}
}
sort(s + 1, s + cnt + 1);
for (int i = cnt; i >= 1; i -- ) { //这里必须注意!!!
//对于两个字符串 00100 和 00010,显然第二个输出出来应该是靠后的,但是字典序确实靠前,所以必须倒着枚举。
for (int j = 0; j < n; j ++ )
if ((s[i][j] - '0') == 1)
cout << j + 1 << " ";
cout << endl;
}
return 0;
}
qp兜售小面包和冰可乐
根本看不懂www
建议先学会二进制枚举再来看