题目

• 原题地址：C. BA-String
• 题目编号：1620C
• 目标算法：dp（动态规划）
• 难度评分：1800

1.题目大意

• 给你一串序列长为 n，每位为 a 或 * ，n ≥ 1
• 每个 * 可以换成 0 到 k 个 b
• 重复的序列算一个，即连续的 * 中不同 * 替换成 b 后可能相同
• 求：按照字典序排列的第 x 个字符串

2.题目分析

• 既然可以通过改变 b 的数量和位置来实现按照字典序进行排序，那么这之间必然存在着一种对应关系。
• 我的想法是，先开一个数组，把一段连续的 * 进行统计，a 进行单独标记为 -2， 最后用 -1 标记统计结束。
• 例如：a * * * a * * a * * * * a
• 转换成数组后就变成了： -2， 3， -2， 2， -2， 4， -2， -1
• 通过举例分析，将按照字典序排好的序列的顺序实际上可以通过每位不同进制来实现。
• 还是上面的例子，先不看 a ，则每段连续的 * 最多可以替换成 b 的个数为：
• 3k， 2k, 4k
• 由于替换成的 b 可以从 0 开始取，所以每位的进制（最多可以表示的不同的数）为：
• 3k+1, 2k+1, 4k+1
• 需要注意的是，由于采用进制的方式是从 0 开始计数，所以 x 一开始要减 1。
• 所以到这里本题就变成了将 x-1 转换成一个特定的变进制数，每位的数值就是每段连续的 * 需要替换成的 b 的个数。
• 继续按照上面的例子来，具体的转换方式：

x = x - 1;
B3 = x % (4k + 1);
x /= (4k + 1);
B2 = x % (2k + 1);
x /= (2k + 1);
B1 = x % (3k + 1);

• （如果看不懂为什么这么做可以自己代数试试找找规律）
• 由于本题还需要在每组 b 之中插入 a ，所以直接在上面的数组中进行操作，同时将转换得到的进制数覆盖原来统计的个数即可（倒序进行），最后再顺序遍历数组输出就行。
• 本题的几个坑：
  1. k 可以为 0
  2. 输入序列中可以没有 *
  3. a 可以连续出现

3.题目代码

#include 

using namespace std;

int main()
{
    int t;
    //freopen("./in.txt","r",stdin);
    cin >> t;
    while(t--)
    {
        int n, k;
        long long x;
        cin >> n >> k >> x;
        x--;//按照进制来说是从0开始计数，因此要减一
        long long cnt[n+5] = {0};
        char ch;
        int i=0, j=0;
        cin >> ch;//首位特判
        if(ch=='*')//是*就统计个数
            cnt[j]++;
        else//是a就设置为-2
        {
            cnt[j] = -2;
            j++;
        }
        for(i=1,j;i> ch;
            if(ch=='*')//是*就统计个数
                cnt[j]++;
            else//是a就设置为-2
            {
                if(cnt[j]!=0)
                    j++;
                cnt[j] = -2;
                j++;
            }
        }
        if(cnt[j]==0)//最后一个是a
        {
            cnt[j] = -1;//表示结束
            j--;
        }
        else//最后一个是*
            cnt[j+1] = -1;
        while(cnt[j]==-2&&j>=0)//输入最后一位为a,就倒退，直至到达*,也有可能没有*
            j--;
        for(j;j>=0;j--)
        {
            if(cnt[j]!=-2)
            {
                //cout << cnt[j] << " ";
                long long tmp = cnt[j] * k + 1 ;//加一转化为对应进制数
                if(k==0)
                {
                    cnt[j] = 0;
                    continue;
                }
                cnt[j] = x % (tmp);
                x /= tmp;
            }
        }
        for(int m=0;cnt[m]!=-1;m++)
        {
            if(cnt[m]==-2)
                cout << 'a';
            else
                for(int z=0;z