BA-String

Created by LXC on Sun Mar 31 00:11:55 2024

https://codeforces.com/problemset/problem/1620/C

ranting: 1800

tag: brute force, dp, greedy, implementation, math

problem

您拥有一个整数 $k$，以及一个由字符 a 与字符 * 组成的长度为 $n$ 的字符串。

在这其中，每一个星号都必须替换成 $0\sim k$ 个字符 b，在所有的星号替换完成后，得到的字符串我们称为 BA-String。

请您求出给定字符串所转化出的字典序第 $x$ 小的 BA-String。

本题采用多组数据，数据组数为 $T$。

$1\leqslant T,n,k\leqslant2000$

$1\leqslant x\leqslant10^{18}$

solution

对于连续的t个星号，可以替换最多$0\sim t\cdot k$个b

我们逆序遍历字符串，依次统计出现连续星号的个数，得到序列$c_1, c_2, \cdots, c_{p}$，共计p个连续段，第i段的星号个数是$c_{i}$。

要求第k小字典序只需将$x-1$转为化为混合基数的数字，$\overline {a_{p}a_{p-1}\cdots a_{2}a_{1}} = \sum \limits_{i=1}^{p} a_{i}\prod \limits_{j=0}^{i-1}c_j$，设$c_0=1$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    ll n, k, x;
    cin >> n >> k >> x;
    x--;
    string s, ans;
    cin >> s;
    for (int i=n-1; i>=0; ) {
        int j = i;
        while (j>=0 && s[j] == '*') j--;
        if (j == i) {
            i--;
            ans.push_back('a');
        } else {
            ll c = ((i-j)*k+1);
            for (int t=0; t<x%c; t++) ans.push_back('b');
            x/=c;
            i = j;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}