自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 23:07:22，当前版本为作者最后更新于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。