题目描述

难度分:$966$

在长度为$A+B$的字符串中，出现过$A$次a和$B$次b的字符串，请找出按词典顺序排列为$K$次的字符串（其中$A,B \in [1,30]$，$K$不会超过字符串的排列数）。

输入样例$1$

2 2 4

输出样例$1$

baab

输入样例$2$

30 30 118264581564861424

输出样例$2$

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

算法

递归

从第一个字符开始，逐位考虑每个位置应该放什么字母。假设目标字符串长度为$A+B=len$，字符串的索引从$1$开始。如果当前到了索引$i$，还剩下$a$个字母a要放，$b$个字母b要放，则按以下规则分类讨论：

1. 当$a \gt 0$时，从下一个位置$i+1$放到末尾，一共有$t=\frac{(a+b-1)!}{(a-1)!b!}$个方案，也就是说在$[1,i]$确定的情况下，后面无论怎么排列，也只能产生$t$种串。如果$t \lt k$，那当前位置就肯定只能放b了，因为覆盖不到原问题字典序第$k$的字符串，接下来考虑下一位，确定$[i+1,len]$字典序第$k=k-t$的字符串是哪个。如果$t \geq k$，那当前位置放a能够覆盖住原问题字典序第$k$的串，继续考虑下一位，确定$[i+1,len]$字典序第$k$的字符串是哪个。
2. 当$a=0$时，当前位置只能放b，直接考虑下一位，确定$[i+1,len]$字典序第$k$的字符串。

复杂度分析

这个递归带有限制，相当于对DFS做剪枝，不便于分析时间和空间复杂度，只能粗略估计是指数级别。

python 代码

from math import factorial

def dfs(rest_a: int, rest_b: int, k: int):
    if rest_a:
        # 尝试放一个a
        t = factorial(rest_a - 1 + rest_b) // factorial(rest_a - 1) // factorial(rest_b)
        if t < k:
            # 此时只能放b
            print('b', end='')
            dfs(rest_a, rest_b - 1, k - t)
        else:
            # 此时可以放a
            print('a', end='')
            dfs(rest_a - 1, rest_b, k)
    else:
        # 此时只能放b
        if rest_b:
            print('b', end='')
            dfs(rest_a, rest_b - 1, k)

if __name__ == '__main__':
    a, b, k = map(int, input().split())
    dfs(a, b, k)