首页 > 代码库 > BZOJ 1717: [Usaco2006 Dec]Milk Patterns 产奶的模式 [后缀数组]
BZOJ 1717: [Usaco2006 Dec]Milk Patterns 产奶的模式 [后缀数组]
1717: [Usaco2006 Dec]Milk Patterns 产奶的模式
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1017 Solved: 561
[Submit][Status][Discuss]
Description
农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。
Input
* Line 1: 两个整数 N,K。
* Lines 2..N+1: 每行一个整数表示当天的质量值。
Output
* Line 1: 一个整数：N天中最长的出现了至少K次的模式的长度
Sample Input
8 2
1
2
3
2
3
2
3
1
1
2
3
2
3
2
3
1
Sample Output
4
Source
Gold
可重叠的k次最长重复子串
二分最长的程度mid，然后把后缀排序结果sa分组，一组中height>=mid，如果有一组中的个数>=k那么长度mid可行
这是一个常用的技巧：按照排序后后缀的LCP(height)分组
本题数组中元素可以为0，所以那个getHeight总感觉有bug，需要判断i+k<=n等等
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int N=2e4+5,M=1e6+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,m,k;int s[N];int sa[N],c[M],t1[N],t2[N];inline bool cmp(int *r,int a,int b,int j){ return a+j<=n&&b+j<=n&&r[a]==r[b]&&r[a+j]==r[b+j];}int rnk[N],height[N];void getHeight(){ int k=0; for(int i=1;i<=n;i++) rnk[sa[i]]=i; for(int i=1;i<=n;i++){ //if(rnk[i]==1) continue; if(k) k--; int j=sa[rnk[i]-1]; while(s[i+k]==s[j+k]) k++; height[rnk[i]]=k; }}void buildSA(){ int *r=t1,*k=t2; for(int i=1;i<=n;i++) c[r[i]=s[i]]++; for(int i=1;i<=m;i++) c[i]+=c[i-1]; for(int i=n;i>=1;i--) sa[c[r[i]]--]=i; for(int j=1;j<=n;j<<=1){//printf("hij %d\n",j); int p=0; for(int i=n-j+1;i<=n;i++) k[++p]=i; for(int i=1;i<=n;i++) if(sa[i]>j) k[++p]=sa[i]-j; for(int i=0;i<=m;i++) c[i]=0; for(int i=1;i<=n;i++) c[r[k[i]]]++; for(int i=1;i<=m;i++) c[i]+=c[i-1]; for(int i=n;i>=1;i--) sa[c[r[k[i]]]--]=k[i]; swap(r,k);p=0;r[sa[1]]=++p; for(int i=2;i<=n;i++) r[sa[i]]=cmp(k,sa[i],sa[i-1],j)?p:++p; if(p>=n) break;m=p; } getHeight();}bool check(int mid){ int cnt=1; for(int i=2;i<=n;i++){ if(height[i]>=mid){ cnt++; if(cnt>=k) return true; }else cnt=1; } return false;}void solve(){ int l=1,r=n,ans=0; while(l<=r){ int mid=(l+r)>>1; if(check(mid)) l=mid+1,ans=mid; else r=mid-1; } printf("%d",ans);}int main(){ //freopen("in.txt","r",stdin); n=read();k=read(); for(int i=1;i<=n;i++) s[i]=read(),m=max(m,(int)s[i]); buildSA(); solve();}
BZOJ 1717: [Usaco2006 Dec]Milk Patterns 产奶的模式 [后缀数组]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。