首页 > 代码库 > poj 3581
poj 3581
题意:给你一个长度为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 }
poj 3581
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。