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

· · 题解

Part 0 题目大意：

给定 k 次更改次数和长度为 n 字符串 str，求最小循环节长度。（循环节的定义：若str 是由若干个字符串（字符）s 拼接组成，则 s 为 str 的循环节）

Part 1 算法分析：

最开始看到这个题目，是想用动态规划的，但发现不好推动态转移方程，就算推出来也是 O(n^2)，n \le 10^6，会炸。于是就想去打暴力，那暴力该如何打呢？应该很容易发现，循环节长度一定为 n 的因子。那么我们就枚举循环节长度，只有当 n mod i 为 0 时才执行下一步操作。

接下来，我们设 m 为 n \div i（也就是区间个数），遍历每个区间第 k 位上出现最多的字符数，那么我们将所有区间第 k 位的字符全部更改为它，更改次数就为 m - num（num 是最多出现的字符数），遍历区间的每一位令 ans 加上 m - num，我们就得到了区间长度为 i 时的最小更改值，只要操作数小于 k，那就输出，一定保证最优。

Part 2 时间复杂度：

表面上我们用了三层循环，时间复杂度应是 O(n^3)，实则不然。里面两层循环实际上总共才遍历了 n 次，而外面那层循环如果 i 不为 n 的因子会直接跳出循环，而一个数 n 最多拥有的因子数不超过 \sqrt{n}。所以时间复杂度最多是 O(\sqrt{n} \times n) \le 10^9，但竟然过了。但正解似乎要用二分（来自 tzhengqing 巨佬的提示）。

Code：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5;
int k;
string str;
int s[30];
signed main()
{
    cin>>k>>str;
    int len=str.size();
    str=' '+str;
    for(int i=1;i<=len;i++)//枚举最小循环节
    {
        if(len%i==0)
        {
            int mod=len/i;//区间个数
            int ans=0;
            for(int j=1;j<=i;j++)//枚举区间中的每一位
            {
                int maxn=-1;
                memset(s,0,sizeof s);
                for(int k=1;k<=mod;k++)//枚举每个区间
                {
                    int l=j+(k-1)*i;
                    s[str[l]-'a'+1]++;
                    maxn=max(maxn,s[str[l]-'a'+1]);//最多有几个区间不要改
                }
                ans+=mod-maxn;
//              cout<<ans<<" ";
            }
            if(ans<=k)
            {
                cout<<i<<'\n';
                exit(0);
            }
        }
    }
    return 0;
}

悄咪咪的说一句，这题思维无，代码难度无，所以建议降橙，但也算一道下位黄吧。