自动搬运

查看原文

来自洛谷，原作者为

	kind_Ygg 这个家伙很懒，什么也没有留下

搬运于2025-08-24 23:01:29，当前版本为作者最后更新于2024-07-27 22:48:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$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;
}

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