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

liuyuannb · 2024-07-28 08:47:53 · 题解

2024.7.28 14:53

感谢@ CSP_juruo，@qijianci，@AeeE5x 等大佬指出本蒟蒻的题解的错误，这题不能用二分。

虽然该题目不具有单调性，但可以通过枚举字符串的长度的因数，并进行判断。一直到找到符合题意的严格循环节的长度，最后输出结束。

代码实现

#include<bits/stdc++.h>
using namespace std;
string s;
int t[30],k,a[11451419],cnt;
int ddj(int mid)
{
    int sum=0;
    for(int i=0;i<a[mid];i++)
    {
        int ans=0;
        memset(t,0,sizeof(t));
        for(int j=i;j<s.size();j+=a[mid])
        {
            t[int(s[j]-'a')]++;//计算每个循环节对应的字符的出现次数。
            ans++;
        }
        int ma=-1;
        for(int j=0;j<=29;j++)
          ma=max(ma,t[j]);
        sum+=(ans-ma);//计算最小修改次数。
    }
    if(sum>k)
      return 0;//判断。
    return 1;
}
int main()
{
    scanf("%d",&k);
    cin>>s;
    for(int i=1;i<=s.size();i++)
    {
        if(s.size()%i==0)
        {
            a[++cnt]=i;//先求出字符串长度的因数，毕竟如果不是字符串长度的因数是不能做严格循环节的长度的。
        }
    }
    int l=1,r=cnt;
    for(int i=1;i<=cnt;i++)//枚举。
    {
        if(ddj(i))
        {
            printf("%d\n",a[i]);//由于数组的因数是按从小到大加入的，因此最先找到符合题意的严格循环节的长度一定最小。
            return 0;
        }
    }
    //printf("%d\n",(ddj(l)?a[l]:a[r]));
    return 0;
}

补充

理论上，这道题如果用暴力枚举的话，是临近极限的 （但不知道为什么跑得最慢的一点也没有时限的一半） 。并且不排除加强数据的可能性，所以最好卡常一下。