[POJ 3581]Sequence
标签： 后缀数组
题意
给你一串序列(A_i)，保证对于$ forall i in [2,n],都有A_1 >A_i$。
现在需要把这个序列分成三段，并且将这三段分别翻转，求如何翻转使整个序列字典序最小。（每一段不能为空）
题解
首先可以确定第一段的位置。
注意到，(A_1)是最大的，所以我们就只用考虑怎样找到一个前缀使其翻转后的字典序最小。
（假如不是的话，就可能找到两个前缀翻转之后，一个为另一个的前缀，无法解决）
这等价于翻转之后找到一个后缀使其字典序最小，用后缀数组处理一下。
然后确定第二段的位置。
先翻转之后，找一个分割点使整个串最小。这等价于最小循环表示法问题。
可以直接用后缀数组解决，也有O(n)的做法。
Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
inline int read()
{
int sum=0,p=1;char ch=getchar();
while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
if(ch=='-')p=-1,ch=getchar();
while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
return sum*p;
}
const int maxn=4e5+20;
int n,a[maxn],sa[maxn],S[maxn],cnt;
void init()
{
n=read();
REP(i,0,n-1)a[i]=read(),S[cnt++]=a[i];
sort(S,S+cnt);
cnt=unique(S,S+cnt)-S;
REP(i,0,n-1)a[i]=lower_bound(S,S+cnt,a[i])-S;
}
int r[maxn*2];
int x[maxn],y[maxn]={0},bug[maxn]={0},v[maxn*2];
void suffix_array(int *r,int n)
{
int p=0,m=200000;
memset(v,-1,sizeof(v));
REP(i,0,m)bug[i]=0;
REP(i,0,n-1)bug[x[i]=r[i]]++;
REP(i,1,m)bug[i]+=bug[i-1];
DREP(i,n-1,0)sa[--bug[x[i]]]=i;
for(int j=1;p<n;j*=2,m=p)
{
p=0;REP(i,n-j,n-1)y[p++]=i;
REP(i,0,n-1)if(sa[i]>=j)y[p++]=sa[i]-j;
REP(i,0,m)bug[i]=0;
REP(i,0,n-1)bug[v[i]=x[y[i]]]++;
REP(i,1,m)bug[i]+=bug[i-1];
DREP(i,n-1,0)sa[--bug[v[i]]]=y[i];
REP(i,0,n-1)v[i]=x[i];p=1;x[sa[0]]=0;
REP(i,1,n-1)x[sa[i]]=v[sa[i-1]]==v[sa[i]] && v[sa[i-1]+j]==v[sa[i]+j] ?p-1:p++;
}
}
void doing()
{
REP(i,0,n-1)r[i]=a[n-i-1];
suffix_array(r,n);
int X=0;
REP(i,0,n-1)if(sa[i]>1){X=sa[i];break;}
REP(i,X,n-1)cout<<S[r[i]]<<endl;
//REP(i,0,n-X-1)x[i]=a[i+X+1];
n=X;
REP(i,n,2*n-1)r[i]=r[i-n];
suffix_array(r,2*n);
REP(i,0,2*n-1)if(sa[i]<n && sa[i]){X=sa[i];break;}
REP(i,X,n-1+X)cout<<S[r[i]]<<endl;
}
int main()
{
init();
doing();
return 0;
}内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
