【每日一题】ABC202D - aab aba baa | 组合数 | 简单

题目内容

原题链接

给定 $a$ 个 'a' 和 $b$ 个 'b' ，求由这 $a+b$ 个字符组成的字典序第 $k$ 大字符串。

数据范围

• $1\le a,b\le 30$
• $1\le k\le S$, $S$ 是这 $a+b$ 个字符组成的不同字符串的数量

题解

考虑当前还有 $x$ 个 'a' ，$y$ 个 'b' ，尝试当前位安排 'a' ，

• 如果 $C_{a+b-1}^{a-1}>k$ ，说明如果安排了 'a' ，则凑成的最大的字符串也比第 $k$ 大的字典序小，所以应该安排 'b'
• 如果 $C_{a+b-1}^{a-1}\le k$，说明应该安排 'a'

此外，如果没有 'a' 了，那么说明后续都得安排 'b' 。

时间复杂度：$O((a+b)\times b)$

代码

#include 
using namespace std;

typedef long long ll;
ll get_cnt(int n, int a) {
    ll res = 1;
    for (int i = 1, j = n; i <= a; ++i, --j) {
        res = res * j / i;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b;
    ll k;
    cin >> a >> b >> k;

    int n = a + b;
    string ans(n, 'b');

    for (int i = 0; i < n && a > 0; ++i) {
        ll cnt = get_cnt(a + b - 1, a - 1);
        if (k > cnt) {
            k -= cnt;
            ans[i] = 'b';
            b -= 1;
        } else {
            ans[i] = 'a';
            a -= 1;
        }
    }

    cout << ans << "\n";

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40