poj 3581 Sequence（后缀数组，离散化）详解-白红宇

poj 3581 Sequence（后缀数组，离散化）详解

阅读量：6253 次

发布时间：2019-06-22

本文共 1439 字，大约阅读时间需要 4 分钟。

题目链接：http://poj.org/problem?id=3581

题目大意：给一个数列，要求将其分成三段，每段进行翻转后形成后合并成新数列，求按字典顺序最小的新数列。

思路：

注意到题目中数列a0,a2,a3...an-1, a0是最大的，因此将原数列翻转后an-1,an-2,...,a1,a0,求后缀数组，

sa[0]所代表的后缀即为所求第一段翻转后的数列，注意到要分成三份，因此sa[0]<2时不可取，此时找sa[1],

sa[2]看是否可取。找第一个位置后，设剩下数列是an-1,an-2,...,ak, 问题转化为找一个分割位置m，使得

am,..ak, an-1,an-2,...,am+1,字典顺序最小。因此将原数列扩展成an-1,an-2,...,ak,an-1,an-2,...,ak,求后缀数组

这样，找到一个最小的i, 使得sa[i]>0, sa[i]<n-k(即要在前一部分），则m=sa[i]. 此时后缀sa[i]的前n-k个前缀刚好是

要求的翻转后的第二三部分。

另外就是要进行离散化，但要保证原数列之间的相对大小关系。

详细代码：

1 #include  2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define rank rk 6 using namespace std; 7  8 const int maxn=200010; 9 int s[maxn];10 int n;11 int sa[maxn],t[maxn],t2[maxn],c[maxn];12 // 后缀数组模板13 void build_sa(int m){14     int *x=t, *y=t2;15     memset(c, 0, sizeof(int)*m);16     for(int i=0; i
         
          =0; --i) sa[--c[x[i]]]=i;19     for(int k=1; k<=n; k<<=1){20         int p=0;21         for(int i=n-k; i
          
           =k) y[p++]=sa[i]-k;24 memset(c, 0, sizeof(int)*m);25 for(int i=0; i
           
            =0; --i) sa[--c[x[y[i]]]]=y[i];28 std::swap(x,y);29 y[n]=-1;30 p=1; x[sa[0]]=0;31 for(int i=1; i
            
             =n) break;35 }36 }37 // 用于离散化38 map
             
               src2i, i2src;39 map
              
               ::iterator it;40 41 void print(int i, int t){42 while(i
               
                first;55 it->second=cnt++;56 }57 for(int i=0; i
                
                 =idx1 || idx2<1) idx2=sa[i++];67 print(idx2, idx2+idx1);68 return 0;69 }