恐怖如斯

用户名：1658227145

访问量：913

签　名：

原谅我这一生，不羁放纵爱自由

等　　级
排　　名	4735
经　　验	1593
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

C++迷宫BFS+DP
浏览：194

你可能喜欢

C++思路清晰，通俗易懂

　　作者: 恐怖如斯　　　　发表时间：2022-03-20 21:01:01 浏览：457　|　评论：2　

原题链接：蓝桥杯2020年第十一届国赛真题-重复字符串

蓝桥杯官方原题链接：[蓝桥杯官方-1049.重复字符串](https://www.lanqiao.cn/problems/1049/learning/ "蓝桥杯官方-重复字符串")

**前言：**这道题数据有问题，一开始不知道，想了我半天，后来实在想不出问题在哪，看了看大佬的题解，看到说数据有问题，就去蓝桥杯官方下面运行了一遍，结果真是，**所有按照题目给的要求的正确的题解，都只能过91的用例**，正常的思路写出的解题，都是没问题的，是官方的数据有问题。

例如 ** S=“abcde", k=3 **时，按照题目给的要求，它应该是过不了的，但是能过得题解显示，最终的结果为 **2**，因为没钱冲会员，所以不懂其中的原理。如果有知道了大佬，可以解释一下。

------------

### 具体思路
这里写的是不考虑官方错误的数据的正确思路
1、首先排除特殊情况，字符串S不能平均分成K份的，即**S.length()%k！=0**，都不行，直接返回-1。
2、**满足条件1，但是K=1**，不用修改， 直接返回0
3、上述条件都不满足，
- 我们把它分成 K份,用vector数组保存
- 因为我们需要的是尽可能的修改最少的次数，所以我们就**把所有分割出来的字串的相同位置的字符进行比较，找出出现次数最多的字符**，剩下的字符就是我们需要修改的，即** 需要修改的=k-maxres**
- 不断的重复上面这条，直至子串结束

**例如：S=”aabaabcac" ,k=3 **

![](/image_editor_upload/20220320084420_25036.png)

### 代码
```cpp
#include<iostream>
#include<string>
#include<vector>
using namespace std;
#include<map>

int solve(string s,int k){
    if(s.length()%k!=0) return -1;
    if(k==1) return 0;
	
    int num=0,tag=0;	//num记录dp数组存放的位置，tag记录每个子串的初始位置
    vector<string> dp(k);	//取名dp纯属动态规划做多了，习惯
	
    int n=s.length()/k; //每段的长度
    while(num<k){
        dp[num]=s.substr(tag,n);
        tag+=n;
        num++;
    }
    int sum=0;	//总的修改次数
    for(int i=0;i<n;i++){   //第几个字母
        map<char,int> mp;	//用map来存放每个字母出现的次数
        int res=0;
        for(int j=0;j<k;j++){   //第几段子串
            mp[dp[j][i]]++;
            res=max(res,mp[dp[j][i]]);	//每一次都比较，找出出现最多的字母的次数
        }
        if(res<k)	//只有出现的次数小于份数，才需要修改
            sum+=k-res;
    }
    return sum;
}

int main(){
    int k;
    cin>>k;
    string s;
    cin>>s;
    
    int res=solve(s,k);
    cout<<res<<endl;
}
```
因为不知道官方数据的 后面是什么，所以本人写不出能通过测试的题解，这里只能附上我在前面看到的一个用Java写的大佬链接：[韩跳跳Java优质题解](http://https://blog.dotcpp.com/a/84820 "韩跳跳Java优质题解")

0.0分

7 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

晚风

我也是91 还以为那里一直出问题

2023-03-15 12:00:45

Passerby

我也是91，还以为想错了。

2022-04-03 16:02:45

恐怖如斯

TA的其他文章

你可能喜欢

C语言训练-字符串正反连接（C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

弟弟的作业（C++代码）

（格式错误） qq290048663 碰巧告知我吧

C二级辅导-求偶数和（C++代码）

C++思路清晰，通俗易懂

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言训练-自守数问题（C语言代码） long long

时间转换（Java代码）

回文串（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

WU-输出正反三角形（C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

母牛的故事（C语言代码）

水仙花（C语言代码）

恐怖如斯

TA的其他文章

你可能喜欢

C语言训练-字符串正反连接 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

弟弟的作业 （C++代码）

（格式错误） qq290048663 碰巧告知我吧

C二级辅导-求偶数和 （C++代码）

C++思路清晰，通俗易懂

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C语言训练-自守数问题 （C语言代码） long long

时间转换 （Java代码）

回文串 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

WU-输出正反三角形 （C++代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

母牛的故事 （C语言代码）

水仙花 （C语言代码）

C语言训练-字符串正反连接（C语言代码）

弟弟的作业（C++代码）

C二级辅导-求偶数和（C++代码）

　　评论区

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言训练-自守数问题（C语言代码） long long

时间转换（Java代码）

回文串（C语言代码）

WU-输出正反三角形（C++代码）

母牛的故事（C语言代码）

水仙花（C语言代码）