pku3581 Sequence

Sequence"/>

pku3581 Sequence

搞掂这题我用了三张草稿纸。。。这得感谢我的小学班主任黄向阳老师，您在我毕业的时候塞给我的n叠作文纸，直到现在还没用完，搞得我每撕一张就想您一次。。。

（省略一万字）

说说我的做法，这题用后缀数组不难想，但要注意以下几点：

1，假设要分开的是两段而不是三段，看看以下两个数据：

2 1 2 1 3    ->   1 2 1 2 3 （1）

2 1 2 1 0    ->   1 2 0 1 2 （2）

看得出两个数据分段的地方不一样。可以试一试最后的数字分别是0、1、2、3的情况，会发现当最后的数字大于等于3时有最小字典序的串按（1）来分段，小于3时按（2）来分段，也就是说分段情况是由最后一个数字决定的。有了这个结论，我的做法是先将原串置反，然后将逆串的第一个数字加到逆串的末尾跑后缀数组，得出的长度不大于原串长度-2的最小后缀就是第一段输出。从逆串中去掉第一段后再按以上步骤得出第二段输出，剩下的就是第三段了。总共跑了两趟后缀数组。 （这里错了，正解看评论）

2，如果后缀数组当中用到了桶排序，一定要先将串离散化，不然桶装不下。

3，用while(scanf()!=EOF)真的会WA，至于为什么呢我也不清楚。

 

#include  < iostream >
#include  < algorithm >
using   namespace  std;

#define  MAXN 200010

int  b[MAXN],array[ 4 ][MAXN], * rank, * nrank, * sa, * nsa,n,len;
int  seq[MAXN];
int  mx;

int  num[MAXN],change[MAXN];

void  make_sa(){
     int  i,k;
    
    sa = array[ 0 ];
    nsa = array[ 1 ];
    rank = array[ 2 ];
    nrank = array[ 3 ];
    
    memset(b, 0 , sizeof (b));
     for (i = 0 ;i < n;i ++ )
        b[seq[i]] ++ ;
     for (i = 1 ;i <= mx;i ++ )
        b[i] += b[i - 1 ];
     for (i = n - 1 ;i >= 0 ;i -- )
        sa[ -- b[seq[i]]] = i;
    
     for (rank[sa[ 0 ]] = 0 ,i = 1 ;i < n;i ++ ){
        rank[sa[i]] = rank[sa[i - 1 ]];
         if (seq[sa[i]] != seq[sa[i - 1 ]])
            rank[sa[i]] ++ ;
    }
    
    
     for (k = 1 ;k < n  &&  rank[sa[n - 1 ]] < n - 1 ;k *= 2 ){
         for (i = 0 ;i < n;i ++ )
            b[rank[sa[i]]] = i;
        
         for (i = n - 1 ;i >= 0 ;i -- )
             if (sa[i] - k >= 0 )
                nsa[b[rank[sa[i] - k]] -- ] = sa[i] - k;
            
             for (i = n - k;i < n;i ++ )
                nsa[b[rank[i]] -- ] = i;
            
             for (nrank[nsa[ 0 ]] = 0 ,i = 1 ;i < n;i ++ ){
                nrank[nsa[i]] = nrank[nsa[i - 1 ]];
                 if (rank[nsa[i]] != rank[nsa[i - 1 ]]  ||  rank[nsa[i] + k] != rank[nsa[i - 1 ] + k])
                    nrank[nsa[i]] ++ ;
            }
             int   * t = sa;sa = nsa;nsa = t;
            t = rank;rank = nrank;nrank = t;
    }
}

class  CP{
public :
     int   operator ()( int  a, int  b){
         return  num[a] < num[b];
    }
};

void  init(){
     int  i;
    scanf( " %d " , & n);
    mx = n; // 桶排序的范围在1~mx

     for (i = n - 1 ;i >= 0 ;i -- ){
        scanf( " %d " , & num[i]);
        b[i] = i;
    }
    sort(b,b + n,CP());
     int  m = 1 ;
    seq[b[ 0 ]] = 1 ;
    change[ 1 ] = num[b[ 0 ]];
     for (i = 1 ;i < n;i ++ ){
         if (num[b[i]] != num[b[i - 1 ]])
            m ++ ;
        seq[b[i]] = m;
        change[m] = num[b[i]];
    }
}



int  main(){
     int  i,cnt,t;
    init();

    seq[n ++ ] = seq[ 0 ]; // *
    make_sa();
    t = 0 ;
     while (sa[t] == n - 1   ||  sa[t] <= 1 )t ++ ;
    cnt = 0 ;
     for (i = sa[t];i < n - 1 ;i ++ ){
        cnt ++ ;
        printf( " %d\n " ,change[seq[i]]);
    }

    n -= cnt + 1 ;
    seq[n ++ ] = seq[ 0 ]; // *
    make_sa();
    t = 0 ;
     while (sa[t] == n - 1   ||  sa[t] < 1 )t ++ ;
     for (i = sa[t];i < n - 1 ;i ++ )
        printf( " %d\n " ,change[seq[i]]);
     for (i = 0 ;i < sa[t];i ++ )
        printf( " %d\n " ,change[seq[i]]);


     return   0 ;
}

 

 

转载于:.html