CF1063F String Journey

蔚落 2021-11-13 15:36 243阅读 0赞

[CF1063F String Journey][]

### 法一： ###

[题解][Link 1]

首先发现，答案一定可以是长度为k,k-1,....1的串

而且后一个是前一个串删掉第一个字符或者删掉最后一个字符得到的

设fi表示i开始的后缀，最大的k是多少

发现f\_i<=f\_\{i+1\}+1

所以可以从高到低暴力枚举f\_i=val，每次最多+1，总复杂度O(n)

考虑验证是否可以存在转移。

即对于删掉第一个和删掉最后一个的字符串在后面的出现位置\{pos\}中，是否存在一个位置的f\[\]>=val-1

发现，出现位置是后缀数组一段区间，可以线段树取max维护

i+val位置单调不增，所以可以i+val过去了之后，把f\[i+val\]更新到rk\[i+val\]位置上。

复杂度O(nlogn)

### 法二： ###

[题解][Link 2]

发现答案最多是O(sqrt(n))<=1000

所以枚举答案len。

考虑每个长度为len的子串能否生成一个journey

bool exi存hash值为i的子串能否作为len-1合法

从后往前，边更新exi边查找更新ans

O(n\*sqrt(n))

代码：

非常之暴力

5e8的bool数组不滚动

5e9次memset，，，，

hash的模数是7000007，base是129不会被卡。。。。

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define fi first
    #define se second
    #define mk(a,b) make_pair(a,b)
    #define numb (ch^'0')
    #define pb push_back
    #define solid const auto &
    #define enter cout<<endl
    #define pii pair<int,int>
    using namespace std;
    typedef long long ll;
    template<class T>il void rd(T &x){
        char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}
    template<class T>il void output(T x){
        if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
        if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}
    template<class T>il void prt(T a[],int st,int nd){
        for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}
    namespace Modulo{
    const int mod=998244353;
    int ad(int x,int y){
        return (x+y)>=mod?x+y-mod:x+y;}
    void inc(int &x,int y){x=ad(x,y);}
    int mul(int x,int y){
        return (ll)x*y%mod;}
    void inc2(int &x,int y){x=mul(x,y);}
    int qm(int x,int y=mod-2){
        int ret=1;while(y){
        if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}
    }
    //using namespace Modulo;
    namespace Miracle{
    const int N=5e5+5;
    const int mod=7000007;
    char s[N];
    bool f[1003][N];
    bool exi[mod];
    int n;
    int h[N];
    int main(){
        rd(n);
        scanf("%s",s+1);
        for(reg i=1;i<=n;++i){
            h[i]=s[i]-'a'+1;
        }
        int ans=1;
        memset(f[1],1,sizeof f[1]);
        for(reg i=2;i<=1000;++i){
            memset(exi,0,sizeof exi);
            for(reg j=n-i;j>=1;--j){
                if(f[i-1][j+i]){
                    exi[h[j+i]]=1;
                }
                if(exi[h[j]]||exi[h[j+1]]){
                    f[i][j]=1;
                    ans=i;
                }
            }
            for(reg j=1;j<=n-i+1;++j){
                h[j]=(h[j]*129+(s[j+i-1]-'a'+1))%mod;
            }
        }
        ot(ans);
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

转载于:https://www.cnblogs.com/Miracevin/p/10988975.html

[CF1063F String Journey]: https://www.luogu.org/problemnew/show/CF1063F
[Link 1]: https://www.cnblogs.com/jefflyy/p/9794746.html
[Link 2]: https://www.cnblogs.com/ywwyww/p/9789607.html