自动搬运

查看原文

来自洛谷，原作者为

	Lemonlwl **

搬运于2025-08-24 22:41:57，当前版本为作者最后更新于2023-03-29 17:16:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8739 [蓝桥杯 2020 国 C] 重复字符串 题解

这道题题意很容易理解：

由一个子串重复 $K$ 次得到的字符串称为 $K$ 次字符串，现在需要将一个给定字符串 $S$ 改为 $K$ 次字符串。

我们可以利用贪心思想，在循环时将每一个循环节内的字符计数，选择出现次数最多的那个字符保留，将其他字符全都改动。

解题步骤如下：

1. 判断是否可以分成 $K$ 个循环节（子串），如果不能，输出 $-1$。（不写最后一个点会错，别问我怎么知道的）

2. 将循环节内的每一个字符放入桶，再进行比较，选择最大值。

附上 AC 代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int k,len,cir,ans,maxn,sum[1005];
string s;
int main(){
	cin>>k>>s;  //输入。
	len=s.length(); //字符串长度。
	cir=len/k;    //循环节长度。
	if(len%k!=0){  //判断是否可以分成K个循环节。
		cout<<-1<<endl;
		return 0;
	}
	for(int i=0;i<len/k;i++){     //因为下标加上循环节长度不能超过总长度，所以是len/k。
		memset(sum,0,sizeof(sum));  //初始化桶。
		maxn=0;       //最大值归零。
		for(int j=i;j<len;j+=cir){
			sum[s[j]]++;    //累加桶。
		}
		for(char c='a';c<='z';c++){
			maxn=max(maxn,sum[c]);  //比较选择最大值。
		}
		ans+=(k-maxn);   //其余字符改动次数累加。
	}
	cout<<ans<<endl;    //输出。
	return 0;
}

点个赞再走呗。