洛谷P2743 乐曲主题Musical Themes [USACO5.1] SA

时间：2021-07-02 10:34:16

正解:SA

解题报告:

传送门

这题三个条件嘛,那就一个个考虑下都解决了就把这题解决了嘛QwQ

那就直接分别针对三个条件写下各个击破就欧克辣?

1)长度大于等于5:求出答案之后和5比大小

2)不能有公共部分:记录连续的满足hei>=d的子串的SA,如果max-min>=d就说明没有公共部分了

3)在乐曲中重复出现(可能经过转调:做个差就是一样儿的了

那就先跑个SA然后二分一下长度,check就是判断有麻油连续的满足hei>=d的满足SA的max-min>d

然后就做完了,,,

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=+;

int n,a[N],x[N],y[N],sa[N],rk[N],hei[N],t[N],l,r;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il bool cmp(ri gd,ri gs,ri k){return y[gd]==y[gs] && y[gd+k]==y[gs+k];}

il void SA()

{

    ri m=;

    rp(i,,n)++t[x[i]=a[i]];

    rp(i,,m)t[i]+=t[i-];

    my(i,n,)sa[t[x[i]]--]=i;

    for(ri k=;k<=n;k<<=)

    {

        ri p=;

        rp(i,,n)y[i]=;rp(i,,m)t[i]=;

        rp(i,n-k+,n)y[++p]=i;

        rp(i,,n)if(sa[i]>k)y[++p]=sa[i]-k;

        rp(i,,n)++t[x[y[i]]];

        rp(i,,m)t[i]+=t[i-];

        my(i,n,)sa[t[x[y[i]]]--]=y[i];

        swap(x,y);

        x[sa[]]=p=;

        rp(i,,n)x[sa[i]]=cmp(sa[i],sa[i-],k)?p:++p;

        if(p>=n)break;

        m=p;

    }

    rp(i,,n)rk[sa[i]]=i;

    ri h=;

    rp(i,,n)

    {

        if(h)--h;

        while(a[i+h]==a[sa[rk[i]-]+h])++h;

        hei[rk[i]]=h;

    }

}

il bool check(ri lth)

{

    ri mn=n,mx=;

    rp(i,,n)

    {

        if(hei[i]<lth)mn=mx=sa[i];

        else

        {

            mx=max(mx,sa[i]);mn=min(mn,sa[i]);if(mx-mn>lth)return true;

        }

    }

    return false;

}

int main()

{

//    freopen("2743.in","r",stdin);freopen("2743.out","w",stdout);

    r=n=read();rp(i,,n)a[i]=read();rp(i,,n)a[i]=a[i+]-a[i]+;SA();

    while(l<r){ri mid=(l+r)>>;if(check(mid+))l=mid+;else r=mid;}

    ++l;if(l>=)printf("%d\n",l);else printf("%d\n",);

    return ;

}

这儿是代码!

相关文章