CF1620C

DDF_ · 2025-09-04 18:49:12 · 题解

题面

有一个长为 n 串由 a 和 * 组成，里面所有的 * 都可以替换为 i 个 b（0 \le i \le k）。求将所有 * 替换后，按字典序排序第 x 小的串。

题解

由于不管填法只管可以得到的所有串，所以可以将连续多个 * 合并为一个空格，这个空格就可以填 t \times k 个 b（t 为 * 个数）。

手玩一下，填最右边肯定增加的排名最少，填满最右边的空格后，上一位填一个并把这一空格清空，排名就 +1，可以在最右边继续填。

这是进位。

于是可以把这个串转化成一个随机进制数，每一位的进制不同，然后题目转化为求从 0 开始第 x 小的数。

然后求出这个数，对于每一个空格，它在数中这一位是多少，就在这个空格中填多少个 b。

怎么求这个数？先令 x=x-1，然后对 x 进制转换为这个数即可。

记得要防爆 long。如果这一位比 x 大，就直接设为 x+1。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int _;
int n,tot;
ll k,x;
ll num[2025];
int put[2025];
char s[2025];
void solve() {
    tot=0;
    scanf("%d%lld%lld",&n,&k,&x),x--;
    cin>>(s+1);
    if(k==0) {
        for(int i=1;i<=n;i++) if(s[i]=='a') putchar(s[i]);
        puts("");
        return;
    }
    for(int i=1;i<=n;i++) {
        if(s[i]=='*') {
            int j=i;
            num[++tot]=1;
            while(s[j]=='*'&&j<=n) num[tot]+=k,j++;
            i=j;
        }
    }
    num[++tot]=1;
    for(int i=tot-1;i;i--) {
        if(num[i]>x/num[i+1]&&num[i+1]>x/num[i]) num[i]=x+1ll;
        else num[i]*=num[i+1];  
    }
    for(int i=1;i<=tot;i++) put[i]=max(x/num[i],0ll),x%=num[i];
    int l=1;
    for(int i=1;i<=n;i++) {
        if(s[i]=='*') {
            int j=i;
            while(s[j]=='*') j++;
            l++,i=j-1;
            while(put[l]) putchar('b'),put[l]--;
        }
        else putchar('a');
    }
    puts("");
    return;
}
int main() {
    scanf("%d",&_);
    while(_--) solve();
    return 0;
}