思路

设 $n=|s|$。
根据题目定义，严格循环节的长度必为 $n$ 的一个正因子。
通过查表可知，$n\le10^6$ 时 $\max \{ d(n) \} \le240$。
于是我们可以 $O \left( d(n) \right)$ 枚举严格循环节的长度，并 $O(n)$ 检验。
检验时，我们先将原字符串分成长度为 $i$ 的 $\frac{n}{i}$ 个字符串。对于第 $j\in [1,i]$ 位，这些字符串要全部修改为同一个字母。
显然每个第 $j$ 位互不影响。

我们假定要将这些字符串的第 $j$ 位修改成字母 $a$，那么除了本身第 $j$ 位就是 $a$ 的字符串无需修改以外，其他字符串都需要进行 $1$ 次修改。
我们要让修改次数尽可能小，就是要找到这些字符串第 $j$ 位上出现次数最多的字母，并将其他字符串第 $j$ 位修改成那个字母。
只需要对每个字符串第 $j$ 位遍历一遍即可。

复杂度

时间复杂度

$O(d(|s|)\times |s|)$

空间复杂度

$O(|s|)$

代码

#include<bits/stdc++.h>
using namespace std;
int k,l;
string s;
int cnt[26];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>k>>s;
	l=s.length();
	for(int i=1;i<=l;i++){
		if(l%i)continue;//不是因子，不处理
		bool f=1;
		int kk=k;
		for(int j=0;j<i;j++){
			int mx=0;
			memset(cnt,0,sizeof(cnt));
			for(int t=j;t<l;t+=i){
				int x=s[t]-'a';
				cnt[x]++;
				mx=max(cnt[x],mx);//统计出现次数最多的字母
			}
			kk-=(l/i-mx);//计算剩余修改次数
			if(kk<0){//修改次数不够，直接退出
				f=0;
				break;
			}
		}
		if(f){
			cout<<i;
			return 0;
		}
	}
	return 0;
}

解题思路

这道题的目标是通过修改字符串中的字符，使其具有最小的严格循环节长度。在不超过 $k$ 次操作的限制下，需要计算可能的最小循环节长度。解题的关键在于如何有效地计算在不同循环节长度下所需的最小修改次数。

核心思路

1. 循环节长度遍历：

   • 对于字符串 $s$ 的每个可能的循环节长度 $l$，从 $1$ 到 $|s|$ 进行遍历。
   • 检查 $l$ 是否能整除 $|s|$，即 $|s| \% l == 0$，只有这样的 $l$ 才有可能成为循环节长度。

2. 计算最小修改次数：

   • 对于每个可能的循环节长度 $l$，计算将字符串变成以 $l$ 为循环节长度所需的最小修改次数。
   • 具体方法是对于每个长度为 $l$ 的位置，统计所有该位置的字符出现频率，找出出现最多的字符，并计算需要修改的次数，使得该位置上的所有字符都变成最多出现的字符。
   • 总修改次数为每个位置所需的修改次数之和。

3. 判断是否满足条件：

   • 对于每个可能的循环节长度 $l$，如果所需的最小修改次数不超过 $k$，则该长度 $l$ 即为可能的最小严格循环节长度，返回该长度。

4. 返回结果：

   • 如果遍历完所有可能的循环节长度，未找到满足条件的长度，则返回字符串的总长度 $|s|$ 作为严格循环节长度。

详细讲解

1. 函数 getmin：

   • 输入：字符串 s 和循环节长度 l。
   • 输出：将字符串变为以 l 为循环节长度所需的最小修改次数。
   • 步骤：
     • 初始化总修改次数 c 为 0。
     • 对于每个位置 $i$ (从 0 到 $l-1$)，统计以 $l$ 为步长的所有字符出现频率。
     • 找出出现最多的字符，并计算将其他字符修改为该字符所需的次数。
     • 累加所有位置的修改次数，即为总修改次数 c。

2. 函数 getans：

   • 输入：整数 k 和字符串 s。
   • 输出：在不超过 $k$ 次修改情况下，使字符串变为最小严格循环节长度的长度。
   • 步骤：
     • 遍历所有可能的循环节长度 l (从 1 到 $|s|$)。
     • 对于每个长度 l，如果 |s| \% l == 0，则调用 getmin(s, l) 计算最小修改次数。
     • 如果最小修改次数不超过 $k$，返回该长度 l。
     • 如果没有找到满足条件的长度，返回字符串的总长度 $|s|$。

代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

// 获取当前长度 l 下需要的最小修改次数
int getmin(string s, int l) {
    int lens = s.length();
    int c = 0;

    for (int i = 0; i < l; ++i) {
        vector<int> f(26, 0); 
        for (int j = i; j < lens; j += l) {
            f[s[j] - 'a']++;
        }

        int maxx = *max_element(f.begin(), f.end());//max_element(u, v)  求(u, v)之间最大值
        int all = (lens - i + l - 1) / l;

        c += all - maxx;
    }

    return c;
}

// 获取最小的严格循环节长度
int getans(int k, string s) {
    int lens = s.length();

    for (int l = 1; l <= lens; ++l) {
        if (lens % l == 0) {
            if (getmin(s, l) <= k) {
                return l;
            }
        }
    }
    return lens;
}

int main() {
    int k;
    string s;
    cin >> k >> s;
    cout << getans(k, s) << endl;
    return 0;
}

复杂度分析

• 时间复杂度：
  • 函数 getmin 的时间复杂度为 $O(n \cdot \frac{n}{l})$，其中 $n$ 为字符串的长度，$l$ 为循环节长度。
  • 函数 getans 遍历所有可能的循环节长度，时间复杂度为 $O(n^2)$。
• 空间复杂度：
  • 使用了长度为 26 的频率数组 f，空间复杂度为 $O(1)$。

审核大大求过

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

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

标题

思路

解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

标题

思路

解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

标题

思路

解题方法

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code