P9211 题解

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