「ALFR Round 3」C 割

cff_0102 · 2024-12-10 15:04:36 · 题解

给定一个字符串 s，假设它的最大字符 c 在 s 中出现了 x 次，那么 f(s) 一定以 x 个 c 开头。

给定两个字符串 s_1,s_2，假设它们的最大字符都是 c，且 c 在 s_1,s_2 中分别出现了 x_1,x_2 次。若 x_1>x_2，那么 f(s_1) 在字典序上一定大于 f(s_2)，因为它们开头的 c 的个数不一样。

因此，最终的划分方案中，一定要让每个子串中 c 出现的个数的最大值尽可能小。根据抽屉原理（鸽巢原理），这个数是 \lceil\frac{x}{k}\rceil。

把那些出现个数更大的分段放到前面。除了最后一段外，让划分的边界刚好在每一段最后一个 c 的右边，这样前 k-1 段的 f 值都正好是 \lceil\frac{x}{k}\rceil 个 c，后面不会再有多余的字符，就做到了字典序尽量小。

如果 k\nmid x，那么正确答案就是 \lceil\frac{x}{k}\rceil 个 c，因为最后一段的 c 的数量小于前面的 c 的数量，它的 f 值不可能成为最终的权值。

否则，最后一段的 c 的个数与前面相同，那么就还需要在最后一个 c 的后面加上从整个字符串的最后一个 c 的后缀最大字典序子序列。这个只需要提前预处理一下，记录下每个位置的后缀最大字符出现的位置即可。

#include<bits/stdc++.h>
using namespace std;
char s[240520];
int a[240520];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,k;cin>>n>>k;
    vector<int>v;
    char mx=' ';
    cin>>s+1;
    for(int i=1;i<=n;i++)mx=max(mx,s[i]);
    for(int i=1;i<=n;i++)if(s[i]==mx)v.emplace_back(i);
    int pos=n;a[n]=n+1;
    for(int i=n-1;i>=1;i--){
        a[i]=pos;
        if(s[i]>=s[pos])pos=i;
    }
    if(v.size()%k){
        cout<<string(v.size()/k+1,mx);
    }else{
        cout<<string(v.size()/k,mx);
        for(int i=a[v.back()];i<=n;i=a[i])cout<<s[i];
    }
    return 0;
}

另注：上面代码中的 cin>>s+1 从 C++20 开始就不能用了，会 CE。