题目大意
有一个字符串是由 m m m 个 ′ a ′ 'a' ′a′ 和 n n n 个 ′ b ′ 'b' ′b′ 字母组成的。求所有这样的字符串中,字典序第 k k k 小的字符串是哪个?
数据范围:
对于
15
%
15\%
15% 的数据,
1
≤
m
,
n
≤
2
1≤m,n≤2
1≤m,n≤2;
对于
25
%
25\%
25% 的数据,
1
≤
m
,
n
≤
10
1≤m,n≤10
1≤m,n≤10;
对于
100
%
100\%
100% 的数据,
1
≤
m
,
n
≤
30
,
1
≤
k
≤
C
m
+
n
m
1≤m,n≤30,1≤k≤C_{m+n}^m
1≤m,n≤30,1≤k≤Cm+nm。
输入格式
输入三个数: m m m n n n k k k,中间用空格分割。
输出格式
输出对应的字符串。
输入样例
2 2 4
输出样例
baab
基本思路
这题乍一看应该是康托展开,但又发现有不对劲的地方,这题的序列并不是数字。但是我们可以沿用康托展开的思想。
我们就拿样例分析:
首先我们在第一个位置填
a
a
a 然后我们还剩一个
a
a
a 可用,在剩下三个位置把它填上,一共有
3
3
3 种可能,可是我们要字典序为
4
4
4 的序列,第一个填
a
a
a 显然不行,所以第一个位置填
b
b
b。
第一个填完看到第二个,还是先尝试填
a
a
a ,此时已经排除第一位填
a
a
a 的
3
3
3 种可能,我们将
k
k
k 减
3
3
3 变为
1
1
1,我们在剩下两个位置中填剩下一个
a
a
a ,有
2
2
2 种可能,明显
k
k
k 就是在这个范围内的,以此类推即可。
然后就是处理计算排列组合的问题了,如果我们现用现算阶乘一定会超时,可是预处理结成会炸变量,所以仔细看看代码中的注释是如何处理的。
核心代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull m,n,k,C[100][100],index,tmp;
int main(){
ios::sync_with_stdio(false);
cin>>m>>n>>k;
C[0][0]=1;
//C(n,m)为在n个数中选取m个数的组合数
//C(n,m)=C(n-1,m)+C(n-1,m-1)
//可以理解为是否选择第n个数的两种情况
for(int i=1;i<=m+n;i++){
C[i][0]=1;
for(int j=1;j<=i;j++)
C[i][j]=C[i-1][j]+C[i-1][j-1];
}
tmp=m;//剩余a的个数
for(int i=1;i<=n+m;i++){
//假设这一位放a
index=C[n+m-i][tmp-1];//在剩下的位置中挑选存放剩余的a
if(tmp>0&&k<=index){
cout<<"a";
tmp--;
}
else{
cout<<"b";
k-=index;
}
}
return 0;
}