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

说在前面，本题的标程是存在问题的，下面会分析标程与正确程序

题目

题目连接

题解

思维吧。

整体思路：将字符串分割成k段，假设每段m个字符，我们统计每段相同位置的每种字符出现的次数，每段都统计上后，每个位置（0 ~ m-1）都取出现次数最多的字符作为要变成的字符，将每一段的对应位置的字符都变成这个字符就行了，因为这个字符在该位置出现最多，其他字符变到该字符能保证次数最少，如果要是变成别的字符，那么出现次数最多的字符变动次数会很多，并非最优解。累加每个位置（0 ~ m-1）上变换次数就是答案。

关于标程出错的问题：

正常人的思路，包括题目也说“字符串 S 恰好可以由某个字符串重复 K 次得到”，很容易想到如果k不能整除字符串长度，那么输出-1；但是标准程序的判断方式是，如果长度小于k输出-1，因为标程不要求能整除才算合法，即使存在不到m个的一段，我们就将这段忽略即可，只按照上面的思路处理前面长度为m的多干段即可，由于长度小于k时会输出0，而这显然应该输出-1，所以特判。

代码

非AC但正确的代码

#include<iostream>
using namespace std;
const int N = 1e5+10;
int k, ans, cnt[N][30], res[N]; 
// cnt[i][j]: i:[0, m), j:[0, 26) 统计每一段第i个位置字符j+'a'出现的次数 
// res[i]:  i:[0, m) 每一段第i个位置字符出现的最大次数 
string s;

int main()
{
    cin >> k;
    cin >> s;
    if (s.size () % k) return puts ("-1"), 0;
    int m = s.size() / k; // 每段长度 
    for (int i = 0;i < s.size();i += m) {
        for (int j = i;j < i + m;j ++) { // 一段 
            cnt[j % m][s[j] - 'a'] ++;
            res[j % m] = max (res[j % m], cnt[j % m][s[j] - 'a']);
        }
    }
    
    for (int i = 0;i < m;i ++)
        ans += k - res[i]; // 累加其他字符串变到出现次数最多的字符的次数，也即非出现次数最多的字符的个数 
    
    cout << ans << endl;
    return 0;
}

AC代码

#include<iostream>
using namespace std;
const int N = 1e5+10;
int k, ans, cnt[N][30], res[N];
string s;

int main()
{
    cin >> k;
    cin >> s;
    if (s.size () < k) return puts ("-1"), 0;
    int n = s.size() - s.size() % k; // 减去多余的部分 
    int m = s.size() / k;
    for (int i = 0;i < n;i += m) {
        for (int j = i;j < i + m;j ++) {
            cnt[j % m][s[j] - 'a'] ++;
            res[j % m] = max (res[j % m], cnt[j % m][s[j] - 'a']);
        }
    }
    
    for (int i = 0;i < m;i ++)
        ans += k - res[i];
    
    cout << ans << endl;
    
    return 0; 
}