【bzoj1692】[Usaco2007 Dec]队列变换

2015.06.15 07:53 Mon | 20次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给定一个字符串,每次从头部或尾部选一个字符加入新队列的尾部,求能获得的最小字典序。长度<=30000

题解

找到后缀数组的题刷一刷,这题就是把原串反着在后面接一遍,然后求后缀数组,建立两个指针指向首字母和反向之后的首字母,也就是尾字母,每次选择rk值较小的一个作为答案
注意每隔80个要换行。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 60005
char str[2];
int n,a[N],ans[N],len;
int v[N],sa[2][N],rk[2][N],p=1,q;
void mul(int k,int *sa,int *rk,int *SA,int *RK)
{
    int i;
    for(i=1;i<=len;i++) v[rk[sa[i]]]=i;
    for(i=len;i;i--) 
        if(sa[i]>k) 
            SA[v[rk[sa[i]-k]]--]=sa[i]-k;
    for(i=len-k+1;i<=len;i++) SA[v[rk[i]]--]=i;
    for(i=1;i<=len;i++) 
    RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);
} 
void get_sa(int lim)
{
    int i,k;
    for(i=1;i<=len;i++) v[a[i]]++;
    for(i=1;i<=lim;i++) v[i]+=v[i-1];
    for(i=1;i<=len;i++) sa[p][v[a[i]]--]=i;
    for(i=1;i<=len;i++) 
        rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i]]!=a[sa[p][i-1]]);
    for(k=1;k<len;k<<=1,swap(p,q)) mul(k,sa[p],rk[p],sa[q],rk[q]);
}
int main()
{
    cin>>n;len=n*2;
    for(int i=1;i<=n;i++) 
    {
        scanf("%s",str);
        a[i]=a[len+1-i]=str[0]-'A'+1;
    }
    get_sa(27);
    int a1=1,a2=n+1,cnt=0;
    while(cnt<n)
    {
        cnt++;
        if(rk[p][a1]<rk[p][a2]) ans[cnt]=a[a1++];
        else ans[cnt]=a[a2++];
    }
    for(int i=1;i<=n;i++) 
    {
        printf("%c",ans[i]+'A'-1);
        if(i%80==0) puts("");
    }
}```