虽然题目本身很简单,但可能会有题目要求枚举组合数,介绍一个简单的方法。
我们要枚举 $n$ 选 $k$ 的组合数,拿一个数组,将前 $k$ 个元素赋为 $1$,调用 prev_permutation
,它会按照字典序降序将排列依次得到,我们据此输出即可。
注意到这个调用 prev_permutation
的次数是组合数,不需要担心复杂度变成 $O(n!)$。
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
using pii = pair<int, int>;
using ll = long long;
inline void read(int &x){
int s=0; x=1;
char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
const int N=50;
int n, k;
int a[N];
int main(){
int n, k; cin>>n>>k;
rep(i,1,k) a[i]=1;
do{
rep(i,1,n) if(a[i]) cout<<i<<' ';
cout<<endl;
}while(prev_permutation(a+1, a+1+n));
return 0;
}
顺便附上递归的做法:
// Problem: 递归实现组合型枚举
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/95/
// Memory Limit: 256 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
using pii = pair<int, int>;
using ll = long long;
inline void read(int &x){
int s=0; x=1;
char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
x*=s;
}
int n, m;
int top, stk[50];
void dfs(int u){
if(top>m || top+(n-u)<m) return;
if(u==n && top==m){
rep(i,1,top) cout<<stk[i]<<' ';
cout<<endl;
return;
}
stk[++top]=u+1;
dfs(u+1);
top--;
dfs(u+1);
}
int main(){
cin>>n>>m;
dfs(0);
return 0;
}
#include [HTML_REMOVED]
using namespace std;
const int N=50;
int n, k;
int a[N];
int main(){
int n, k;
cin >> n >> k;
for(int i = 1; i <= k; i++) a[i]=1;
}
为什么只是把数组1~k赋值1,k之后的数也可以排序呢?
?这个做法相当于是将前 k 个设成 1,然后剩下后面的 n-k 个设成 0,然后使用 prev_permutation 的时候是对区间 [1, n] 操作的
为啥前k个要赋值为1啊
表示选取的元素,然后使用 prev_permutation 来改变选取元素的位置
为啥 prev_permutation 复杂度不是 O(n!)呢!
因为它是按照字典序的逆序枚举的,比如一个串
1 1 0 0
,那么一共有 $C_4^2 = 6$ 种字典序而不是 $4!=24$ 种这个用法太妙了 Orz
嗯嗯qwq~