K-beautiful Strings

Created by LXC on Mon Sep 11 20:48:43 2023

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

ranting: 2000

tag: binary search, brute force, constructive algorithms, greedy, strings

problem

给出一个长度为n的字符串s，以及一个数字k。

求一个长度为n的字典序最小的字符串，满足条件在字典序大于等于s，且每个字符出现的次数是k的倍数。

solution

首先，判断s是否已经是每个字符出现次数都是k的倍数。如果是则s就是答案。

否则，我们将尽量修改s的后缀使得满足条件。

为了满足字典序大于s，我们选择了一个位置x，让s[x]字典序变大，则x之后的字符可以随便改也能保证构造出的字典序大于s。

为了满足每个字符出现的次数是k的倍数，统计x之前的字符出现频次，并统计当前x修改为的字符。我们需要让这些频次变为k的倍数，所以可以统计出每个字符还需要多少个，设个数为sum。

现在存在n-1-x个位置需要修改，如果n-1-x大于等于sum，且n-1-x-sum是k的倍数。则可以构造答案了。

前x个字符不用变，x位置字符是修改后的字符。后续的字符按照字典序升序填充，先是n-1-x-sum个a，然后是每种字符补充到k的倍数所缺失的个数。

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;

void sol() {
    int k, n;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> c(26);
    for (char i : s)
        c[i - 'a']++;
    int cnt = 0;
    for (int t : c)
        cnt += t % k;
    if (cnt == 0) {
        cout << s << "\n";
        return;
    }
    for (int i = n - 1; i >= 0; i--) {
        c[s[i] - 'a']--;
        for (int j = s[i] - 'a' + 1; j < 26; j++) {
            c[j]++;
            int sum = 0;
            for (int t : c)
                sum += (k - t % k) % k;
            if (n - 1 - i >= sum && (n - 1 - i - sum) % k == 0) {
                cout << s.substr(0, i);
                cout << char(j + 'a');
                cout << string(n - 1 - i - sum, 'a');
                for (int x = 0; x < 26; x++) {
                    // cout << x << " " << (k - c[x] % k) % k << endl;
                    for (int y = 0; y < (k - c[x] % k) % k; y++) {
                        cout << char(x + 'a');
                    }
                }
                cout << "\n";
                return;
            }
            c[j]--;
        }
    }
    cout << "-1\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;
}