NC25192. 实际问题
描述
本题的出题人在实习（摸鱼）中遇到了一个非常有意思的问题，这个问题的核心即需要枚举“组合”。
组合即数学上的“C”的概念，我们知道 C(x,y)=y!/x!/(y-x)!
如果我们想枚举 C(3,4),我们有：
1 2 3
1 2 4
这道题就是这个意思，当然为了简化输出，我们只要你给出按顺序的第 k 个组合即可，如 C(3,4)的第 3 个是：1 3 4
注意组合内部是无序的，但是我们希望得到一个递增顺序的结果，即结果是
1 3 4，而非诸如 1 4 3 之流。输入描述
首先是一个整数T，表示数据输入的组数，T<=10。
对于每组数据，一行三个数n,m,k：
欲求C(m,n)的第k个组合。保证n<=100000，m<=n，k<=1000000，k<=C(m,n)。
输出描述
对应T行，每行即结果。
示例1
输入:
2 6 3 10 100 5 1000
输出:
1 5 6 1 2 3 14 99
说明:
对于第一组的样例，按顺序的组合：C++14(g++5.4) 解法, 执行用时: 528ms, 内存消耗: 6604K, 提交时间: 2019-10-02 17:50:12
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int a[maxn],p[maxn],cnt,k,m,n,flag;
void dfs(int x,int y)
{
if(flag)return ;
if(y==m+1)
{
++cnt;
if(cnt==k)
{
for(int i=1;i<m;i++)
cout<<a[i]<<" ";
cout<<a[m]<<"\n";
flag = 1;
}
return ;
}
for(int i=x;i<=n-m+y;i++)
{
a[y] = i;
dfs(i+1,y+1);
if(flag)return ;
}
}
int main()
{ int T;
cin>>T;
while(T--)
{
cin>>n>>m>>k;
cnt = 0;
flag = 0;
dfs(1,1);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 25ms, 内存消耗: 1504K, 提交时间: 2020-05-23 16:32:41
#include<bits/stdc++.h>
using namespace std;
int C(int x,int y){
long long int tmp=1,i=1,j=x,k=min(y,x-y);
while(i<=k){
tmp*=j;
tmp/=i;
j--;i++;
if(tmp>1000000){return 1919810;}
}
return (int)tmp;
}
int i,j,k,m,n,a,b,c;
int main(){
scanf("%d",&n);
for(j=1;j<=n;j++){
scanf("%d%d%d",&a,&b,&c);m=0;
for(i=1;i<=b;i++){
m++;
while(c>C(a-m,b-i)){c-=C(a-m,b-i);m++;
}
printf("%d ",m);
}
printf("\n");
}
}