POJ3581：Sequence——题解

时间：2023-03-08 20:20:34

http://poj.org/problem?id=3581

给一串数，将其分成三个区间并且颠倒这三个区间，使得新数列字典序最小。

参考：http://blog.****.net/libin56842/article/details/46417301

（不是论文题，但是还是借鉴了题解，我是真的菜）

首先我们分成的三个区间肯定是一个前缀+中间一段+一个后缀。

那么我们先求前缀，方法很简单，只需要将原数列倒着存，然后找字典序最小的后缀即可。可以用后缀数组实现。

（因为原数列前缀的颠倒肯定是原数列颠倒后的其中一个后缀）

再考虑如何求中间一段。我们先把前面求完的部分扣掉，然后求字典序最小的后缀……？

并不是这样，比如3 5 0 5 0 5，按照这个方法我们得到的是0 5，但实际上我们要得到0 5 0 5。

所以为了避免这种情况，我们将这个数列倍长，这样就能使得0505小于05了。

最后再把剩下的一点输出即可。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cctype>

#include<cstdio>

#include<vector>

#include<queue>

#include<cmath>

using namespace std;

const int N=4e5+;

int n,m,t,rank[N],sa[N],height[N],w[N],b[N],s[N];

inline bool pan(int *x,int i,int j,int k){

    int ti=i+k<n?x[i+k]:-;

    int tj=j+k<n?x[j+k]:-;

    return x[i]==x[j]&&ti==tj;

}

inline void SA_init(){

    int *x=rank,*y=height,r=N-;

    for(int i=;i<r;i++)w[i]=;

    for(int i=;i<n;i++)w[s[i]]++;

    for(int i=;i<r;i++)w[i]+=w[i-];

    for(int i=n-;i>=;i--)sa[--w[s[i]]]=i;

    r=;x[sa[]]=;

    for(int i=;i<n;i++)

    x[sa[i]]=s[sa[i]]==s[sa[i-]]?r-:r++;

    for(int k=;r<n;k<<=){

    int yn=;

    for(int i=n-k;i<n;i++)y[yn++]=i;

    for(int i=;i<n;i++)

        if(sa[i]>=k)y[yn++]=sa[i]-k;

    for(int i=;i<r;i++)w[i]=;

    for(int i=;i<n;i++)++w[x[y[i]]];

    for(int i=;i<r;i++)w[i]+=w[i-];

    for(int i=n-;i>=;i--)sa[--w[x[y[i]]]]=y[i];

    swap(x,y);r=;x[sa[]]=;

    for(int i=;i<n;i++)

        x[sa[i]]=pan(y,sa[i],sa[i-],k)?r-:r++;

    }

    for(int i=;i<n;i++)rank[i]=x[i];

}

inline void LSH(){

    sort(b,b+m);

    m=unique(b,b+m)-b;

    for(int i=;i<n;i++){

        s[i]=lower_bound(b,b+m,s[i])-b;

    }

    return;

}

int main(){

    scanf("%d",&n);

    for(int i=n-;i>=;i--){

    scanf("%d",&b[i]);

    s[i]=b[i];

    }

    m=n;

    LSH();

    SA_init();

    for(t=;;t++){

    if(sa[t]>)break;

    }

    for(int i=sa[t];i<n;i++)

    printf("%d\n",b[s[i]]);

    for(int i=;i<sa[t];i++)

    s[i+sa[t]]=s[i];

    n=sa[t]*;

    SA_init();

    for(t=;;t++){

    if(sa[t]==)continue;

    if(sa[t]<(n>>))break;

    }

    for(int i=sa[t];i<(n>>);i++)

    printf("%d\n",b[s[i]]);

    for(int i=;i<sa[t];i++)

    printf("%d\n",b[s[i]]);

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

相关文章