poj 3581 Sequence(接尾辞配列)
12222 ワード
転載は出典を明記してください. http://www.cnblogs.com/fraud/ ——by fraud
Sequence
Time Limit: 5000MS
Memory Limit: 65536K
Case Time Limit: 2000MS
Description
Given a sequence, {A1, A2, ..., An} which is guaranteed A1 > A2, ..., An, you are to cut it into three sub-sequences and reverse them separately to form a new one which is the smallest possible sequence in alphabet order.
The alphabet order is defined as follows: for two sequence {A1, A2, ..., An} and {B1, B2, ..., Bn}, we say {A1, A2, ..., An} is smaller than {B1, B2, ..., Bn} if and only if there exists such i ( 1 ≤ i ≤ n) so that we have Ai < Bi and Aj = Bj for each j < i.
Input
The first line contains n. (n ≤ 200000)
The following n lines contain the sequence.
Output
output n lines which is the smallest possible sequence obtained.
Sample Input
Sample Output
Hint
{10, 1, 2, 3, 4} -> {10, 1 | 2 | 3, 4} -> {1, 10, 2, 4, 3}
タイトル:
n個の数を与えて、この数の列を3段に分けて、更に3段を反転した後につなぎ合わせて1つの新しい列になって、辞書の順序の最小の新しい列を求めます.
考え方:
最初の数は他のすべての数よりも大きいことを保証するので、最初のセグメントを取るときに反転後の辞書順の最小の接尾辞を直接取ればよい.接尾辞配列を用いて求めることができる.
その後、残りの文字列を2つのセグメントに分けて、辞書順を最小にします.まず,反転後の辞書順の最小接尾辞をとるという第1段のような方法を容易に考える.
しかし、この方法では、10 1 2 3という反例のセットを簡単に見つけることができます.
上記の方法では,第1セグメントを10 1,反転,1 10とする.
そして残りの文字列は2 2 2 3となり、この列に対しては反転後3 2 2となり、辞書順が最小2となる.列全体が1 10 2 3 2となる
明らかに私たちが2を取るとき、列全体の辞書順は1 10 2 3で最も小さい.
長さmのシリアルs[1]......s[m]について、s[1]......s[k]とs[k+1]......s[m]に分ける
これを反転するとs[k]......s[1]s[m]......s[k+1]となり、この列がs[m]......s[k+1]s[k]......s[1]s[m]......s[k+1]s[k]......s[k]......s[k]......s[k]......s[1]のサブ列であることがわかり、この列の長さがm辞書順の最小より大きい接尾辞を探すことで答えを得ることができる.
上記の例3 2については、3 2 2 3 2となり、長さがmより大きい辞書順の最小接尾辞が2 2 2 3 2となる.その前のセグメントを求める第2のセグメントとする.
また、本題は単組入力でなければなりません.そうしないとWAになります.これは長い間穴があいていました...
コード君
Sequence
Time Limit: 5000MS
Memory Limit: 65536K
Case Time Limit: 2000MS
Description
Given a sequence, {A1, A2, ..., An} which is guaranteed A1 > A2, ..., An, you are to cut it into three sub-sequences and reverse them separately to form a new one which is the smallest possible sequence in alphabet order.
The alphabet order is defined as follows: for two sequence {A1, A2, ..., An} and {B1, B2, ..., Bn}, we say {A1, A2, ..., An} is smaller than {B1, B2, ..., Bn} if and only if there exists such i ( 1 ≤ i ≤ n) so that we have Ai < Bi and Aj = Bj for each j < i.
Input
The first line contains n. (n ≤ 200000)
The following n lines contain the sequence.
Output
output n lines which is the smallest possible sequence obtained.
Sample Input
5
10
1
2
3
4
Sample Output
1
10
2
4
3
Hint
{10, 1, 2, 3, 4} -> {10, 1 | 2 | 3, 4} -> {1, 10, 2, 4, 3}
タイトル:
n個の数を与えて、この数の列を3段に分けて、更に3段を反転した後につなぎ合わせて1つの新しい列になって、辞書の順序の最小の新しい列を求めます.
考え方:
最初の数は他のすべての数よりも大きいことを保証するので、最初のセグメントを取るときに反転後の辞書順の最小の接尾辞を直接取ればよい.接尾辞配列を用いて求めることができる.
その後、残りの文字列を2つのセグメントに分けて、辞書順を最小にします.まず,反転後の辞書順の最小接尾辞をとるという第1段のような方法を容易に考える.
しかし、この方法では、10 1 2 3という反例のセットを簡単に見つけることができます.
上記の方法では,第1セグメントを10 1,反転,1 10とする.
そして残りの文字列は2 2 2 3となり、この列に対しては反転後3 2 2となり、辞書順が最小2となる.列全体が1 10 2 3 2となる
明らかに私たちが2を取るとき、列全体の辞書順は1 10 2 3で最も小さい.
長さmのシリアルs[1]......s[m]について、s[1]......s[k]とs[k+1]......s[m]に分ける
これを反転するとs[k]......s[1]s[m]......s[k+1]となり、この列がs[m]......s[k+1]s[k]......s[1]s[m]......s[k+1]s[k]......s[k]......s[k]......s[k]......s[1]のサブ列であることがわかり、この列の長さがm辞書順の最小より大きい接尾辞を探すことで答えを得ることができる.
上記の例3 2については、3 2 2 3 2となり、長さがmより大きい辞書順の最小接尾辞が2 2 2 3 2となる.その前のセグメントを求める第2のセグメントとする.
また、本題は単組入力でなければなりません.そうしないとWAになります.これは長い間穴があいていました...
1 #include <iostream>
2 #include <algorithm>
3 #include <cstdio>
4 using namespace std;
5 #define MAXN 400010
6 int n,k;
7 int sa[MAXN],rank[MAXN],a[MAXN],b[MAXN],c[MAXN],tmp[MAXN];
8 bool cmp(int i,int j){
9 if(rank[i]!=rank[j])return rank[i]<rank[j];
10 else {
11 int ri=i+k<=n?rank[i+k]:-1e8;
12 int rj=j+k<=n?rank[j+k]:-1e8;
13 return ri<rj;
14 }
15 }
16 void build(int len,int *s){
17 n=len;
18 for(int i=0;i<=n;i++)sa[i]=i,rank[i]=i<n?s[i]:-1e8;
19 for(k=1;k<=n;k<<=1){
20 sort(sa,sa+n+1,cmp);
21 tmp[sa[0]]=0;
22 for(int i=1;i<=n;i++){
23 tmp[sa[i]]=tmp[sa[i-1]]+(cmp(sa[i-1],sa[i])?1:0);
24 }
25 for(int i=0;i<=n;i++)rank[i]=tmp[i];
26 }
27 }
28 int main()
29 {
30 int N;
31 scanf("%d",&N);
32 //while(scanf("%d",&N)!=EOF){
33 for(int i=0;i<N;i++)scanf("%d",a+i);
34 for(int i=0;i<N;i++)b[i]=a[N-1-i];
35 build(N,b);
36 int p1;
37 for(int i=0;i<=N;i++){
38 p1=N-sa[i]-1;
39 if(p1>=0&&p1+3<=n)break;
40 }
41 int m=N-p1-1;
42 for(int i=0;i<m;i++)c[i]=a[i+p1+1];
43 for(int i=0;i<m;i++)b[i]=b[i+m]=c[m-1-i];
44 build(2*m,b);
45 int p2;
46 for(int i=0;i<=2*m;i++)
47 {
48 p2=m-sa[i]-1;
49 if(p2>=0&&p2<=m-2)break;
50 }
51 p2+=p1+1;
52 for(int i=p1;i>=0;i--)printf("%d
",a[i]);
53 for(int i=p2;i>p1;i--)printf("%d
",a[i]);
54 for(int i=N-1;i>p2;i--)printf("%d
",a[i]);
55 //}
56 return 0;
57 }コード君