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

· · 题解

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;
}

点个赞再走呗。