P10801

题目大意

给一个字符串，求通过改变最多 $k$ 个字符后最小化这个字符串的严格循环节的长度。

思路

从题目，我们能初步分析出一下几点：

• 答案肯定是字符串长度的因子；
• 由于随着答案的减小，需要操作的次数会增加，那么我们就能想到二分。

我们可以先统计字符串长度的每个因子，然后存到数组里面。

然后二分这个数组，找到最小符合条件的答案。

二分的 check​ 函数可以先枚举循环节的每一位，然后统计所有循环节中这一位每一个字符出现的次数，根据贪心的思想我们发现把这一位都变成出现次数最大的是最优的，所以先统计出最大值然后拿总和去减，具体可以看我的代码。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
int k;
string s;
int n;
int a[1000005], cnt, m;
bool check(int x) {
    int sum = 0;
    for (int i = 0; i < a[x]; i ++) {//循环节的每一位
        int cntt[300] = {}, ss = 0, maxn = -1e9;
        memset(cntt, 0, sizeof cntt);
        for (int j = i; j < s.size(); j += a[x]) {
            cntt[s[j] - 'a'] ++;
            // cout << j << " ";
        }
        // cout << "\n";
        for (int j = 0; j < 27; j ++) maxn = max(cntt[j], maxn);
        for (int j = 0; j < 27; j ++) ss += cntt[j];
        // for (int j = 0; j < 300; j ++) if (cntt[j]) cout << char(j) << " : " << cntt[j] << "\n";
        // cout << maxn << " " << ss << "\n";
        sum += ss - maxn;
    }
    // cout << x << " " << sum << "\n";
    return (sum <= k);
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> k >> s;
    n = s.size();
    for (int i = 1; i <= n; i ++) {
        if (n % i == 0) a[++cnt] = i;
    }
    m = cnt;
    int l = 1, r = m;
    while (l < r - 1) {
        int mid = (l + r) / 2;
        // cout << l << ' ' << r << " " << mid << " -\n";
        if (check(mid)) r = mid;
        else l = mid;
    }
    if (check(l)) cout << a[l];
    else cout << a[r];
    return 0;
}