注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

USACO 5.1 Musical Themes (theme)  

2009-10-24 11:41:19|  分类: usaco |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这道题将前后两元素相减之后,就是求最长重复子串,于是可以用后缀树组求出
后缀树组有两个有名的构造算法,一个是倍增思想复杂度o(nlogn),另一个是dc3算法,复杂度是o(n)
后缀树组的相关内容可以查看wc2004论文,而dc3算法采用三分支,比较巧妙,具体可以查看论文
http://www.cs.helsinki.fi/u/tpkarkka/publications/jacm05-revised.pdf
作者在文章里说这种算法的基本原理是“Difference Cover”原则,并且在采样(Sample)的时候以3为模,所以这个算法叫DC3(Difference Cover modulo 3)
求出后缀树组之后,用o(n)的时间求出h数组,而height[i]=h[sa[i]],height[i]表示后缀树组中第i个和第i-1个的最长公共前缀,并且h[i]>=h[i-1]-1因而可以很快的求出h数组
h[0]=0;
    for(int i=0;i<n;i++){
     if(r[i]==0)
       h[i]=0;
     else
     while(h[i]+i<n&&h[i]+sa[r[i]-1]<n&&a[h[i]+i]==a[h[i]+sa[r[i]-1]])
       h[i]++;
     h[i+1]=h[i]-1;
     if(h[i+1]<0)
       h[i+1]=0;
    }
然后用二分法枚举长度就可以用o(nlogn)求出答案,由于懒得写二分了,我就写了个RMQ
#include<iostream>
#include <fstream>
#include<cmath>
using namespace std;
    ofstream fout ("theme.out");
    ifstream fin ("theme.in");
    bool compar(int a1,int b1,int a2,int b2){
         return (a1<a2)||(a1==a2&&b1<=b2);
    }
    bool compar(int a1,int b1,int c1,int a2,int b2,int c2){
         return (a1<a2)||(a1==a2&&compar(b1,c1,b2,c2));
    }
    void radix(int n,int k,int a[],int b[],int t[]){
         int c[k+1];
         for(int i=0;i<=k;i++)
           c[i]=0;
         for(int i=0;i<n;i++)
           c[t[a[i]]]++;
         for(int i=0,sum=0;i<=k;i++){
                 int kk=c[i];
                 c[i]=sum;
                 sum+=kk;
         }
         for(int i=0;i<n;i++)
           b[c[t[a[i]]]++]=a[i];
    }
    void aa(int n,int k,int sa[],int t[]){
         int n1=(n+2)/3,n2=n1+n/3,n0=(n+1)/3;
         int sa12[n2+3]; sa12[n2]=sa12[n2+1]=sa12[n2+2]=0;
         int r[n2+3]; r[n2]=r[n2+1]=r[n2+2]=0;
         int sa0[n1];
         int r0[n1];
         for(int i=0,j=0;i<n+n1-n0;i++)
           if(i%3!=0)
             r[j++]=i;
         radix(n2,k,r,sa12,t+2);
         radix(n2,k,sa12,r,t+1);
         radix(n2,k,r,sa12,t);            
         int num=0,c1=-1,c2=-1,c3=-1;
         for(int i=0;i<n2;i++){
           if(t[sa12[i]]!=c1||t[sa12[i]+1]!=c2||t[sa12[i]+2]!=c3){
             c1=t[sa12[i]];
             c2=t[sa12[i]+1];
             c3=t[sa12[i]+2];
             num++;
           }
           if(sa12[i]%3==1) r[sa12[i]/3]=num;
           else r[sa12[i]/3+n1]=num;
         }
         if(num<n2){
           aa(n2,num,sa12,r);
           for(int i=0;i<n2;i++) 
            r[sa12[i]]=i+1;
         }
         else
           for(int i=0;i<n2;i++)
                    sa12[r[i]-1]=i;
         for(int i=0,j=0;i<n2;i++)
           if(sa12[i]<n1)        
              r0[j++]=sa12[i]*3;
         radix(n1,k,r0,sa0,t);
         for(int i=n1-n0,j=0,p=0;p<n;p++){
           #define geti() (sa12[i]<n1? sa12[i]*3+1:(sa12[i]-n1)*3+2)
           int ii=geti();
           int jj=sa0[j];
           if(sa12[i]<n1? compar(t[ii]        ,r[sa12[i]+n1],t[jj]        ,r[jj/3])
                           :compar(t[ii],t[ii+1],r[sa12[i]-n1+1],t[jj],t[jj+1],r[jj/3+n1])){
             i++;
             sa[p]=ii;
             if(i==n2)
               for(p++;j<n1;j++,p++)sa[p]=sa0[j];
           }else{
                 sa[p]=jj;
                 j++;
                 if(j==n1)
                   for(p++;i<n2;i++,p++)sa[p]=geti();
                 }
         }
    }
int po(int a,int b){
    int m=1;
    while(b--)
      m<<=1;
    return m;
}
int main(){
    int n;
    fin>>n;
    n--;
    int a[n+3];
    int k,k1,mi=100,ma=-100;
    fin>>k;
    for(int i=0;i<n;i++){
      fin>>k1;
      a[i]=k1-k;
      k=k1;
      if(a[i]<mi)
        mi=a[i];
      if(a[i]>ma)
        ma=a[i];
    }
    for(int i=0;i<n;i++)
      a[i]+=1-mi;
    int sa[n],r[n],h[n];
    for(int i=0;i<n+3;i++){
            sa[i]=0;
            r[i]=0;
            h[i]=0;
    }
    a[n]=a[n+1]=a[n+2]=0;
    aa(n,ma-mi+1,sa,a);
    for(int i=0;i<n;i++)
      r[sa[i]]=i;
    ma=0;
    h[0]=0;
    for(int i=0;i<n;i++){
     if(r[i]==0)
       h[i]=0;
     else
     while(h[i]+i<n&&h[i]+sa[r[i]-1]<n&&a[h[i]+i]==a[h[i]+sa[r[i]-1]])
       h[i]++;
     h[i+1]=h[i]-1;
     if(h[i+1]<0)
       h[i+1]=0;
    }
    int l=(int)(log10(n)/log10(2)),f[n][l+1];
    for(int i=0;i<n;i++)
      for(int j=0;j<=l;j++)
        f[i][j]=0;
    for(int i=0;i<n;i++)
      f[i][0]=h[sa[i]];
    for(int i=1;i<l;i++)
      for(int j=0;j<n;j++){
              f[j][i]=f[j][i-1];
              if(j+(int)(po(2,i-1))<n&&f[j+(int)(po(2,i-1))][i-1]<f[j][i])
                f[j][i]=f[j+(int)(po(2,i-1))][i-1];
      }
    for(int i=n-1;i>=0;i--)
     if(n-sa[i]>ma)
      for(int j=i+1;j<n;j++)
        if(n-sa[j]>ma&&(int)abs(sa[j]-sa[i])-1>ma){
              int ll=min(f[i+1][(int)(log10(j-i)/log10(2))],
              f[j-po(2,(int)(log10(j-i)/log10(2)))+1][(int)(log10(j-i)/log10(2))]);
              int yy=min((int)abs(sa[j]-sa[i])-1,ll);
              if(ma<yy)
                ma=yy;
              if(ll<ma) break;
      }
    if(ma>=4)
      fout<<ma+1<<endl;
    else fout<<0<<endl;
    return 0;
}

  评论这张
 
阅读(310)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017