Codeforces 1493C（贪心+思维）

题目描述

给定一个\(n\)和\(k\)，和一个长度为\(n\)的字符串，要求在当前字符串的基础上，构造出字符串，使得字符串中每个字母出现的次数都能够整除\(k\)，构造的字符串的字典序应该尽可能的小，如果不存在，输出\(-1\)。(不能比给定的字符串字典序小)

思路

先考虑特殊情况，当\(n\%k!=0\)时，显然无法构造出题目要求的字符串。如果字符串最初就符合条件，那么答案就是它本身。

再考虑一般情况，要想字典序最小，我们优先考虑靠后的元素，所以我们从后往前枚举前缀，假设当前枚举到了第\(i\)位，我们使用\(sum\)表示\([1,i-1]\)位置上要满足题意需要改变的字母个数，\(cnt\)数组表示每个字母出现的次数。即\(sum=\sum_{i=0}^{26}(k-cnt[i]\%k)\%k\)。

从后往前枚举，对于枚举到的第\(i\)位，枚举\([s[i]+1,z]\)，当\(i+sum≤n\)时，符合题目条件。\([1,i-1]\)的字母不变，第\(i\)位放当前枚举的字母，\([i+1,n]\)位置用来补充出现次数不能整除\(k\)的字母。对于\([i+1,n]\)位置上的字母，枚举\(26\)个字母，依次摆放出现次数不符合条件的字母，接着剩下的位置全部放\(a\)，由于题目要求字典序最小，所以我们再对这部分字符串进行排序即可。

对于剩下位置全部放\(a\)的证明：
因为\(n\)是\(k\)的倍数，且\(sum\)都用填充的字母补齐，故也是\(k\)的倍数，那么剩下的位置也全是\(k\)的倍数，所以剩下位置全部放\(a\)是可行的。

AC代码

#include "iostream"
#include "cstring"
#include "string"
#include "vector"
#include "cmath"
#include "algorithm"
#include "map"
#include "set"
#include "queue"
#include "stack"
#include "cassert"
#include "unordered_map"
#include "sstream"
#include "cstdio"
 
using namespace std;
 
#define fi first
#define se second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) a.begin(),a.end()
#define rep(x,l,u) for(ll x=l;x=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define seteps(N) setprecision(N)
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#define lson (ind<<1)
#define rson (ind<<1|1) 
 
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair PII;
typedef pair PCC;
typedef pair PDD;
typedef pair PLL;
typedef pair PIII;
 
 
struct Scanner {
 
    bool hasNext = 1;
    bool hasRead = 1;
 
    int nextInt() {
        hasRead = 0;
        int res = 0;
        char flag = 1, ch = getchar();
        while(ch != EOF && !isdigit(ch)) {
            hasRead = 1;
            flag = (ch == '-') ? -flag : flag;
            ch = getchar();
        }
        while(ch != EOF && isdigit(ch)) {
            hasRead = 1;
            res = res * 10 + (ch - '0');
            ch = getchar();
        }
        if(ch == EOF)
            hasNext = 0;
        return res * flag;
    }
 
    ll nextLL() {
        hasRead = 0;
        ll res = 0;
        char flag = 1, ch = getchar();
        while(ch != EOF && !isdigit(ch)) {
            hasRead = 1;
            flag = (ch == '-') ? -flag : flag;
            ch = getchar();
        }
        while(ch != EOF && isdigit(ch)) {
            hasRead = 1;
            res = res * 10 + (ch - '0');
            ch = getchar();
        }
        if(ch == EOF)
            hasNext = 0;
        return res * flag;
    }
 
    char nextChar() {
        hasRead = 0;
        char ch = getchar();
        while(ch != EOF && isspace(ch)) {
            hasRead = 1;
            ch = getchar();
        }
        if(ch == EOF)
            hasNext = 0;
        return ch;
    }
 
    int nextString(char *str) {
        hasRead = 0;
        int len = 0;
        char ch = getchar();
        while(ch != EOF && isspace(ch)) {
            hasRead = 1;
            ch = getchar();
        }
        while(ch != EOF && !isspace(ch)) {
            hasRead = 1;
            str[++len] = ch;
            ch = getchar();
        }
        str[len + 1] = 0;
        if(ch == EOF)
            hasNext = 0;
        return len;
    }
 
} sc;
 
ll rd() {
    ll x = sc.nextLL();
    return x;
}
 
void rd(int &x) {
    x = sc.nextInt();
}
 
void rd(ll &x) {
    x = sc.nextLL();
}
 
void rd(char &x) {
    x = sc.nextChar();
}
 
void rd(char* x) {
    sc.nextString(x);
}
 
template
void rd(pair &x) {
    rd(x.first);
    rd(x.second);
}
 
template
void rd(T *x, int n) {
    for(int i = 1; i <= n; ++i)
        rd(x[i]);
}
 
template
void rd(vector &x,int n){
    for(int i = 1; i <= n; ++i)
        rd(x[i]);
}
 
void printInt(int x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x >= 10)
        printInt(x / 10);
    putchar('0' + x % 10);
}
 
void printLL(ll x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x >= 10)
        printLL(x / 10);
    putchar('0' + x % 10);
}
 
void pr(int x, char ch = '\n') {
    printInt(x);
    putchar(ch);
}
 
void pr(ll x, char ch = '\n') {
    printLL(x);
    putchar(ch);
}
 
//#define LOCAL
template
void pr(pair x, char ch = '\n') {
#ifdef LOCAL
    putchar('<');   
    pr(x.first, ' ');
    pr(x.second, '>');
    putchar(ch);
    return;
#endif //LOCAL
    pr(x.first, ' ');
    pr(x.second, ch);
}
template
void pr(T *x, int n) {
    for(int i = 1; i <= n; ++i)
        pr(x[i], " \n"[i == n]);
}
 
template
void pr(vector &x) {
    int n = x.size();
    for(int i = 1; i <= n - 1; ++i)
        pr(x[i], " \n"[i == n - 1]);
}
 
const int N=1005;
const int M=1<<12;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int mod1=998244353;
const lll oone=1;
const double eps=1e-6;
const double pi=acos(-1);
 
int f(int x,int k){
    return (k-x%k)%k;
}
int cnt[26];
void solve(){
    mst(cnt,0);
    int n,k;
    rd(n);rd(k);
    string s;
    cin>>s;
    rep(i,0,n) cnt[s[i]-'a']++;
    bool ok=true;
    rep(i,0,26) if(cnt[i]%k) ok=false;
    if(n%k) puts("-1");
    else if(ok) puts(s.c_str());
    else{
        int sum=0;
        rep(i,0,26) sum+=f(cnt[i],k);
        rrep(i,n-1,0){
            sum-=f(cnt[s[i]-'a'],k);
            cnt[s[i]-'a']--;
            sum+=f(cnt[s[i]-'a'],k);
            rep(j,s[i]-'a'+1,26){
                int last=sum;
                sum-=f(cnt[j],k);
                cnt[j]++;
                sum+=f(cnt[j],k);
                if(i+1+sum<=n){
                    rep(t,0,i) cout<