首页 > 代码库 > BZOJ 1717: [Usaco2006 Dec]Milk Patterns 产奶的模式
BZOJ 1717: [Usaco2006 Dec]Milk Patterns 产奶的模式
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次的模式的长度
题解：
至少K次可以理解为出现K次，更好满足。
离散化后求这个串的后缀数组，rank数组及height数组。
答案应该是height数组中连续K-1个值的最小值的最大值。
可以用一个单调队列维护。
代码：
#include<cstdio>#include<cstring>#include<algorithm>//by zrt//problem:using namespace std;int n,K;const int MAXN=20005;int s[MAXN];int sa[MAXN],t[MAXN],t2[MAXN],c[MAXN],rank[MAXN],height[MAXN];void build_sa(int m){ memset(t,-1,sizeof t); memset(t2,-1,sizeof t2); int *x=t,*y=t2; for(int i=0;i<m;i++) c[i]=0; for(int i=0;i<n;i++) c[x[i]=s[i]]++; for(int i=1;i<m;i++) c[i]+=c[i-1]; for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i; for(int k=1;k<=n;k<<=1){ int p=0; for(int i=n-k;i<n;i++) y[p++]=i; for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k; for(int i=0;i<m;i++) c[i]=0; for(int i=0;i<n;i++) c[x[y[i]]]++; for(int i=0;i<m;i++) c[i]+=c[i-1]; for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1;x[sa[0]]=0; for(int i=1;i<n;i++){ x[sa[i]]= y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++; } if(p>=n) break; m=p; }} int tot;struct N{ int x,w; N(int a=0,int b=0){ x=a,w=b; }};struct dddl{ N q[MAXN]; int h,t; void insert(N a){ while(h!=t&&q[t-1].w>=a.w) t--; q[t++]=a; } void pop(int pos){ if(q[h].x==pos) h++; } int ask(){ return q[h].w; }}dddl;int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%d%d",&n,&K); for(int i=0;i<n;i++){ scanf("%d",&s[i]); c[i+1]=s[i]; } sort(c+1,c+n+1); tot=unique(c+1,c+n+1)-(c+1); for(int i=0;i<n;i++){ s[i]=lower_bound(c+1,c+tot+1,s[i])-c; } s[n]=-1; build_sa(tot+1); for(int i=0;i<n;i++) rank[sa[i]]=i; int k=0; for(int i=0;i<n;i++){ if(k) k--; if(!rank[i]) continue; int j=sa[rank[i]-1]; while(s[i+k]==s[j+k]) k++; height[rank[i]]=k; } int ans=0; for(int i=0;i<n;i++){ dddl.insert(N(i,height[i])); dddl.pop(i-K+1); ans=max(ans,dddl.ask()); } printf("%d\n",ans); return 0;}
BZOJ 1717: [Usaco2006 Dec]Milk Patterns 产奶的模式
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。