首页 > 代码库 > [bzoj1717][Usaco2006 Dec]Milk Patterns 产奶的模式
[bzoj1717][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次的模式的长度
Sample Input
8 2
1
2
3
2
3
2
3
1
1
2
3
2
3
2
3
1
Sample Output
4
My Solution
打出后缀数组sa及数组height
做height的st表，枚举height长度为k的区间内的最小值中的最大值
离线最值最爱st表
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 inline int read(){ 7 char ch; 8 int re=0; 9 bool flag=0;10 while((ch=getchar())!=‘-‘&&(ch<‘0‘||ch>‘9‘));11 ch==‘-‘?flag=1:re=ch-‘0‘;12 while((ch=getchar())>=‘0‘&&ch<=‘9‘) re=re*10+ch-‘0‘;13 return flag?-re:re;14 }15 16 const int maxn=20001,maxm=1e6;17 int n,kkk;18 int aa[maxn];19 int sa[maxn],t[maxn],t2[maxn],c[maxm];20 int height[maxn],rk[maxn];21 int m=1e6;22 int stmin[maxn][16],mn[maxn];23 int ans=0;24 25 void init(){26 n=read(),kkk=read();27 for(int i=0;i<n;i++)28 aa[i]=read();29 n++;30 }31 32 void build_sa(){33 int i,*x=t,*y=t2;34 for(i=0;i<m;i++) c[i]=0;35 for(i=0;i<n;i++) c[x[i]=aa[i]]++;36 for(i=0;i<m;i++) c[i]+=c[i-1];37 for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;38 for(int k=1;k<=n;k<<=1){39 int p=0;40 for(i=n-k;i<n;i++) y[p++]=i;41 for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;42 for(i=0;i<m;i++) c[i]=0;43 for(i=0;i<n;i++) c[x[y[i]]]++;44 for(i=0;i<m;i++) c[i]+=c[i-1];45 for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];46 swap(x,y);47 p=1;48 x[sa[0]]=0;49 for(i=1;i<n;i++)50 x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;51 if(p>=n) break;52 m=p;53 }54 }55 56 void getHeight(){57 int i,j,k=0;58 for(i=0;i<n;i++) rk[sa[i]]=i;59 for(i=0;i<n;i++){60 if(k) k--;61 j=sa[rk[i]-1];62 while(aa[i+k]==aa[j+k]) k++;63 height[rk[i]]=k;64 }65 66 n--;67 mn[0]=-1;68 for(i=1;i<=n;i++){69 mn[i]=((i&(i-1))==0)?mn[i-1]+1:mn[i-1];70 stmin[i][0]=height[i];71 }72 for(j=1;j<=mn[n];j++)73 for(i=1;i+(1<<j)-1<=n;i++)74 stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);75 }76 77 int height_min(int left,int right){78 int k=mn[right-left+1];79 return min(stmin[left][k],stmin[right-(1<<k)+1][k]);80 }81 82 void solve(){83 kkk-=2;84 for(int i=2;i<=n-kkk;i++){85 ans=max(ans,height_min(i,i+kkk));86 //printf("%d %d %d\n",i,i+kkk,height_min(i,i+kkk));87 }88 printf("%d\n",ans);89 }90 91 int main(){92 //freopen("temp.in","r",stdin);93 init();94 build_sa();95 getHeight();96 solve();97 return 0;98 }
如果梦想有颜色，那一定是水蓝色
[bzoj1717][Usaco2006 Dec]Milk Patterns 产奶的模式
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。