自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

搬运于2025-08-24 22:46:23，当前版本为作者最后更新于2023-04-15 08:31:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目分析

感觉没有很好的性质，但是观察 $n=3\times10^3,m=10^4,l=3\times10^5$ 的数据范围发现限制给的很松，一方面是 $S_\text{real}$ 与 $S_\text{fin}$ 的差距很小，另一方面是 $S'_\text{fin}$ 的容错率比较大，所以考虑简单的随机算法。

我们直接枚举 $S'_0$ 的长度 $len$, 对于每个长度随一些位置 $p_{1\dots k}$, 检测在随的这些 $p_i$ 中有多少个满足 $S_\text{real}[p_i]=S_\text{real}[p_i+len]$, 记作 $f_{len}$, 然后取 $\max f_{len}$ 所对应的 $len$ 作为 $l_0$ 即可，看数据范围容易发现正确率极高（因为时间限制足够随很多次，于是 $f_{len}\over k$ 与整体情况的偏差超过 $m\over n$ 的概率极低）。

那么随 $600$ 次，令 $S'_0$ 的每一位 $S'_0[i]$ 取 $S_\text{real}[k\times l_0+i]$ 中出现次数最多的字符即可通过本题。

代码

/*
  author: PEKKA_l  
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <random>
using namespace std;

int l,n,m,lmx,cnt[35];
char s[300005],ans[300005];
mt19937 mt_rand(time(0));

int getrd(int l,int r) {return l+mt_rand()%(r-l+1);}

int check(int len)//随机
{
	int cntt=0;
	for(int i=1;i<=600;i++) {int wz=getrd(0,l-len-1); if(s[wz]==s[wz+len]) cntt++;}
	return cntt;
}

signed main()
{
	cin>>l>>lmx>>n>>m>>s;
	int mxx=0,nmm;//枚举 l_0
	for(int i=lmx;i>=1;i--) {int nans=check(i); if(nans>mxx) {mxx=nans; nmm=i;}}
	for(int j=0;j<nmm;j++)
	{
		memset(cnt,0,sizeof(cnt)); int nnum=-1,nmax=0;
		for(int k=j;k<l;k+=nmm)
		{
			cnt[s[k]-'a'+1]++; if(cnt[s[k]-'a'+1]>nmax) {nmax=cnt[s[k]-'a'+1]; nnum=s[k]-'a'+1;}
		}
		ans[j]=(char)(nnum+'a'-1);
	}
	cout<<nmm<<endl<<ans<<endl;
}