题解：P10810 【MX-S2-T1】变

· · 题解

首先，题面明示二分（让循环节最小）。

我们很容易就可以想到二分枚举循环节长度。假设循环节长度为 k，有 n 个字符（注意与题面中的表示不同），我们把模 k 余数相同的每 \dfrac{n}{k} 位统计一下（开个桶），把这些位的字符改为原来出现次数最多的字符，这样显然最优，因为模 k 余数不相同的两个位是没有联系的（严格循环节）。

但是我们会想到一个问题：如果 n=7，但是 k=3，这样显然不是严格循环节，然而，这有可能影响到答案。难道假了吗？

我们知道，办法总比困难多。k 有一个性质，那就是一定是 n 的因数。所以我们先把 n 的因数找出来，然后二分 k 是 n 第几小的因数。

我们知道，如果 x=\displaystyle{\prod_{i=1}^{m}p_i^{a_i}}（整数唯一分解定理，p_i 为质数），则 d(x)=\displaystyle{\prod_{i=1}^{m}(a_i+1)}，其中 d 表示 a_i 的因数个数。

我们不妨来一个夸张的估算，假设 x 的质因数两两不同，并且这些质因数都 \ge 2，显然有 d(x) \leq 2^{\log_2 x}。从而得到 d(x) \leq x，实际上，当 x 比较大的时候，d(x) 会比 x 小很多。

我写了个程序，测得 10^6 以内，\dfrac{d(x)}{x} 的平均值约为 0.000112。也就是说，d(x) 的值大约为 \sqrt{x}。

所以，这个算法平均时间复杂度为 O(n\log\sqrt{n})，可以说非常优秀了。

当然，最坏情况下依然能取到 O(n \log n)，但是这个时候的 n 会非常小。

#include<bits/stdc++.h>
#error Don't copy the solution!
using namespace std;
int k, cnt;
vector<int> ys;
string s;
int buk[300];
int work(int x){
    for (int i = 1; i <= x; i++)
        if (x % i == 0){
            cnt++;
            ys.push_back(i);
        }
    return cnt - 1;
}
bool check(int x){
    int u = ys[x], sum = 0;
    for (int i = 1; i <= u; i++){
        memset(buk, 0, sizeof buk);
        for (int j = i; j < s.size(); j += u)
            buk[s[j] - 'a']++;
        sort(buk, buk + 26, [](int a, int b){return a > b;});
        int tot = (s.size() - 1) / u;
        sum += (tot - buk[0]);
    }
    if (sum <= k)
        return 1;
    else
        return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> k;
    cin >> s;
    s = " " + s;
    int l = 0, r = work(s.size() - 1), ans = r;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (check(mid))
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    cout << ys[ans];
    return 0;
}