恐怖如斯

用户名：1658227145

访问量：1016

签　名：

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

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

　　自我简介：

TA的其他文章

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

你可能喜欢

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

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

原题链接：蓝桥杯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编程助手吧

　　评论区

验题君

数据已经修改并重判！感谢反馈！

2024-07-20 11:55:59

晚风

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

2023-03-15 12:00:45

Passerby

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

2022-04-03 16:02:45

恐怖如斯

TA的其他文章

你可能喜欢

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

数字整除（C语言代码）

C语言考试练习题_排列（C++代码）

剔除相关数（C语言代码）

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

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

评论区

精彩推荐

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

1009题解

幸运数（C++代码）

数对（C语言代码）

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

1013题解

数字游戏（C++代码）

钟神赛车（C语言代码）

交换Easy （C语言代码）

企业奖金发放（C语言代码）

恐怖如斯

TA的其他文章

你可能喜欢

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

数字整除 （C语言代码）

C语言考试练习题_排列 （C++代码）

剔除相关数 （C语言代码）

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

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

评论区

精彩推荐

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

1009题解

幸运数 （C++代码）

数对 （C语言代码）

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

1013题解

数字游戏 （C++代码）

钟神赛车 （C语言代码）

交换Easy （C语言代码）

企业奖金发放 （C语言代码）

数字整除（C语言代码）

C语言考试练习题_排列（C++代码）

剔除相关数（C语言代码）

　　评论区

幸运数（C++代码）

数对（C语言代码）

数字游戏（C++代码）

钟神赛车（C语言代码）

企业奖金发放（C语言代码）