P10810 【MX-S2-T1】变 题解

大致思路：

首先我们知道，要使一个字符串的循环节，那么循环节长度必须是字符串长度的因数，那么我们可以先给字符串的长度，去找一遍他的所有因子，这一操作，需要 $O(\log |S|)$ 的时间。到这里，先不要着急写，因为里面需要用到一个贪心的策略，因为我们会根据每个因子，判断它是否能通过修改其中不超过 $k$ 个字符，那么我们要怎样尽可能少的修改字符呢？找标准串？首先，我们会发现，一个循环节一个循环节不好搞，可以通过每个循环节的同一个位置上的字符去贪心修改，可以发现，假设我们目前枚举的是长度为 $x$ 的循环节是否合法，现在再看循环节的第 $1$ 位，显然，他们的位置分别在 $1, x + 1, 2 × x + 1...$，那么我们根据这个特性来计算同一个位置上，出现次数最多的字符，因为相应的，如果都变成这个出现最多的字符，那么修改的肯定最少，判断他是否超过限制 $k$，最后再看看所有位置至少需要改的数量总和，是否超过 $k$，没超过则为合法循环节长度，否则则继续枚举，以此类推，就能得到最终的答案，在枚举前，如果对每个因子从大到小进行排序，在一些测试点中可以更快的通过。

代码实现：

#include <bits/stdc++.h>

using namespace std;
int n;
string s;
int len, ans[100005], cnt, mx, t[100005];
void init(int x)
{
	//int y = sqrt(x);
	for (int i = 1;i * i <= x; ++ i)
	{
		if(x % i == 0)
		{
			ans[ ++ cnt] = i;
		}
		if(i * i != x && x % i == 0)
		{
			ans[ ++ cnt] = x / i;
		}
	}
}
signed main()
{
	cin >> n >> s;
	len = s.size();
	s = " " + s;
	init(len);
	sort(ans + 1, ans + cnt + 1);
	int mn = len;
	for (int i = 1;i <= cnt; ++ i)
	{
		int p = len / ans[i];//循环节个数
		bool f = 0;
		int sum = 0;
		for (int j = 1;j <= ans[i]; ++ j)
		{
			mx = 0;
			for (int k = 1;k <= 26; ++ k)//用桶来存每个循环节同个位置字母出现次数
			{
				t[k] = 0;
			}
			int o = j;
			++ t[int(s[j] - 96)];
			for (int k = 2;k <= p; ++ k)
			{
				o += ans[i];
				++ t[int(s[o] - 96)];
			}
			for (int k = 1;k <= 26; ++ k)//用桶来存每个循环节同个位置字母出现次数 
			{
				mx = max(mx, t[k]);
			}
			if(p - mx > n)
			{
				f = 1;
				break;
			}
			sum += (p - mx);
			if(sum > n)
			{
				f = 1;
				break;
			}
		}
		if(f)continue;
		if(sum <= n)
		{
			mn = ans[i];
			break;
		}
	}
	cout << mn << "\n";
	return 0;
}

这样这道题目就完成啦！！！