题解 P2743 【[USACO5.1]乐曲主题Musical Themes】

· · 题解

楼教主男人八题 AND 2009年集训队论文的例题之一，在POJ上n的范围是20000，dp和hash什么的应该都会被卡，所以后缀数组才是真正的正解

先不考虑转调，马上想到可以二分判断长度为mid是否可行

先求出字符串的height数组，然后在height上分组

每组是height上连续的一段，且其中除第一个以外所有height值都不小于mid（无法满足的就自己单独一个组）

满足这两点的情况下使一组尽量长， 比如这样(图片也出自论文)

我们只需要检查是否存在一组， 满足其中最大的sa-最小的sa>mid，若满足即可行

因为按这样分组，组内任意两个后缀的lcp长度都不会小于mid

现在考虑转调，其实也很简单

我们只需要在原音乐序列的差分数组上求height即可

因为若原序列有两个子段的差分序列一样，那么他们一定可以通过加/减同一个数得到

(再次注意转调不是最大的sa-最小的sa+1>mid，因为我们要在原序列的差分数组上求height)

//niiick
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
typedef long long lt;

int read()
{
    int x=0,f=1;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return x*f;
} 

const int maxn=40010;
int n,m;
int a[maxn];
int rak[maxn],sa[maxn],tp[maxn],tax[maxn];
int height[maxn];

void rsort()
{
    for(int i=0;i<=m;++i) tax[i]=0;
    for(int i=1;i<=n;++i) tax[rak[i]]++;
    for(int i=1;i<=m;++i) tax[i]+=tax[i-1];
    for(int i=n;i>=1;--i) sa[tax[rak[tp[i]]]--]=tp[i];
}

void ssort()
{
    m=210;
    for(int i=1;i<=n;++i)
    rak[i]=a[i],tp[i]=i;

    rsort();
    for(int k=1;k<=n;k<<=1)
    {
        int p=0;
        for(int i=n-k+1;i<=n;++i) tp[++p]=i;
        for(int i=1;i<=n;++i) if(sa[i]>k) tp[++p]=sa[i]-k;

        rsort();
        swap(rak,tp);
        rak[sa[1]]=p=1;
        for(int i=2;i<=n;++i)
        rak[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+k]==tp[sa[i-1]+k])?p:++p;
        if(p>=n) break;
        m=p;
    }
}

void getH()
{
    int k=0;
    for(int i=1;i<=n;++i)
    {
        if(k) k--;
        int j=sa[rak[i]-1];
        while(a[i+k]==a[j+k]) k++;
        height[rak[i]]=k;
    }
}

int check(int x)
{
    int mx=sa[1],mi=sa[1];
    for(int i=2;i<=n;i++)
    {
        if(height[i]<x) mx=mi=sa[i];
        else
        {
            if(sa[i]<mi) mi=sa[i];
            if(sa[i]>mx) mx=sa[i];
            if(mx-mi>x) return 1;
        }
    }
    return 0;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        for(int i=1;i<=n;++i) a[i]=read();
        for(int i=1;i<n;++i) a[i]=a[i+1]-a[i]+90;
        n--;//差分数组长度少1

        ssort(); getH();

        int ans=0;
        int L=0,R=n,mid;
        while(L<R)
        {
            mid=L+R>>1;
            if(check(mid)) ans=mid,L=mid+1;
            else R=mid;
        }
        if(ans<4) printf("0\n");
        else printf("%d\n",ans+1);
    }
    return 0;
}