首页 > 代码库 > poj 3581

poj 3581

2024-07-27 23:59:54   223人阅读

题意：给你一个长度为n的数组A，第一个最大，要求你把它切成三段然后分别翻转，问你翻转完后的字典序最小的数组

分析：切成三段需要确定两个分割点，对于第一个分割点由于第一个数是最大的，那么只要求一下第一段翻转后字典序最小的就是答案，

求这个字典序最小第一段的方法就是对翻转后的A建立后缀数组，取第一个符合要求的就是第一个分割点（第一段长度至少1，后两段至少为2）

对于第二个分割点，不能简单的直接去最小的字典序，第二段会影响到第三段。将一个序列分两段然后分别翻转的结果可以看做，

将原序列拼接在一起后在翻转的字串。

这样就可以继续像前面一样用后缀数组搞了。

但是这题有两个坑点：

1、有多余数据，不能使用while(scanf("%d",&N))多case读入，而是直接scanf("%d",&N) 单case

2、A的数据范围没有给，是由负数的，所以在计算后缀数组时，要进行一定的修改，在找rank值的时候。

我的做法是在初始化rank的时候对A做一次离散化的处理，然后初始化rank。计算后缀数组的算法是倍增。具体的可以看代码。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <string> 7 #include <vector> 8 #include <set> 9 #define maxn 200000*2+1010 #define maxm 201011 #define maxt 11012 #define INF 0x3f3f3f3f13 #define mod 100914 #define MAX_STATE 250015 using namespace std;16 int n,N,k;17 int  Rank[maxn];18 int  A[maxn];19 int  B[maxn];20 int SS[maxn];21 int temp[maxn];22 int SA[maxn];23 //比较(rank[k,i],rank[k,i+k])与(rank[k,j],rank[k,j+k])24 bool cmp_sa(int i,int j){25     if(Rank[i]!=Rank[j])return Rank[i]<Rank[j];26     else{27         int ri = i+k<=n?Rank[i+k]:-1;28         int rj = j+k<=n?Rank[j+k]:-1;29         return ri<rj;30     }31 }32 void construct_sa(int *S,int len, int *sa){33     n = len ;34     //长度为1的字符串,Rank直接取字符的编码35     vector<int>v;36     for(int i=0;i<=n;++i)v.push_back(S[i]);37     sort(v.begin(),v.end());38     v.erase(unique(v.begin(),v.end()),v.end());39     for(int i=0;i<=n;++i){40         sa[i]=i;41         int pos = lower_bound(v.begin(),v.end(),S[i])-v.begin();42         Rank[i]=i<n?pos:-1;43     }44     //利用对长度为k的字符串排序计算长度位2k的顺序45     for(k=1;k<=n;k*=2){//注意这里不是 int k46         sort(sa,sa+n+1,cmp_sa);47         //计算新的rank，暂存到temp中48         temp[sa[0]]=0;49         //调整rank,相同的字符串的rank时一样的50         for(int i=1;i<=n;++i){51             temp[sa[i]] = temp[sa[i-1]]+ (cmp_sa(sa[i-1],sa[i])?1:0);52         }53         //存回rank54         for(int i=0;i<=n;++i){55             Rank[i]=temp[i];56         }57     }58 }59 void solve(){60     reverse_copy(A,A+N,B);61     construct_sa(B,N,SA);62     int p1;63     for(int i=0;i<=N;++i){64         p1 = N-SA[i];65         if(N-p1>=2&&p1>=1)break;    66     }67     int m = N-p1;68     reverse_copy(A+p1,A+N,B);69     reverse_copy(A+p1,A+N,B+m);70     construct_sa(B,m*2,SA);71     int p2;72     for(int i=0;i<=2*m;++i){73         p2 = p1+m-SA[i];74         if(p2-p1>=1&&N-p2>=1)break;75     }76     reverse(A,A+p1);77     reverse(A+p1,A+p2);78     reverse(A+p2,A+N);79     for(int i=0;i<N;++i)printf("%d\n",A[i]);80 }81 82 int main(){83     //freopen("in.txt","r",stdin);84     //freopen("out.txt","w",stdout);85     ios::sync_with_stdio(false);86     scanf("%d",&N);87     for(int i=0;i<N;++i)scanf("%d",&A[i]);88     solve();89 }
View Code

 

poj 3581


联系
我们