BZOJ 1717 [USACO06DEC] Milk Patterns (后缀数组+二分)

时间：2021-03-22 07:12:07

题目大意：求可重叠的相同子串数量至少是K的子串最长长度

洛谷传送门

依然是后缀数组+二分，先用后缀数组处理出height

每次二分出一个长度x，然后去验证，在排序的后缀串集合里，有没有连续数量多于K个串的长度>=x，

但据说有一种高端做法是把二分换成单调队列，能减少常数，可惜我并没有看懂......

原题好像是哈希的骚操作，但网上的题解好像都是后缀数组......

比上一道男人八题简单多了，我原来的错代码竟然卡过去了70分..

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N 20010

 #define inf 0x3f3f3f3f

 #define maxn 1000010

 using namespace std;

 int n,len,tot,K;

 int a[N],tr[N],sa[N],rk[N],hs[N],h[N];

 struct node{int id,val,w;}d[N];

 int cmp1(node s1,node s2){return s1.val<s2.val;}

 int cmp2(node s1,node s2){return s1.id<s2.id;}

 int gint()

 {

     int rett=,fh=;char c=getchar();

     while(c<''||c>''){if(c=='-')fh=-;c=getchar();}

     while(c>=''&&c<=''){rett=(rett<<)+(rett<<)+c-'';c=getchar();}

     return rett*fh;

 }

 bool check(int k,int x,int y){

     if(x+k>len||y+k>len) return ;

     else return (rk[x]==rk[y]&&rk[x+k]==rk[y+k])?:;

 }

 void get_sa()

 {

     int cnt=,i;

     for(i=;i<=len;i++) hs[a[i]]++;

     for(i=;i<=tot;i++) if(hs[i]) tr[i]=++cnt;

     for(i=;i<=tot;i++) hs[i]+=hs[i-];

     for(i=;i<=len;i++) rk[i]=tr[a[i]],sa[hs[a[i]]--]=i;

     for(int k=;cnt<len;k<<=)

     {

         for(i=;i<=cnt;i++) hs[i]=;

         for(i=;i<=len;i++) hs[rk[i]]++;

         for(i=;i<=cnt;i++) hs[i]+=hs[i-];

         for(i=len;i>=;i--) if(sa[i]>k) tr[sa[i]-k]=hs[rk[sa[i]-k]]--;

         for(i=;i<=k;i++) tr[len-i+]=hs[rk[len-i+]]--;

         for(i=;i<=len;i++) sa[tr[i]]=i;

         for(i=,cnt=;i<=len;i++) tr[sa[i]]=check(k,sa[i],sa[i-])?cnt:++cnt;

         for(i=;i<=len;i++) rk[i]=tr[i];

     }

 }

 void get_height()

 {

     for(int i=;i<=n;i++){

         if(rk[i]==) continue;

         for(int j=max(,h[rk[i-]]-);;j++)

             if(a[i+j-]==a[sa[rk[i]-]+j-]) h[rk[i]]=j;

             else break;

     }

 }

 void descrete()

 {

     sort(d+,d+n+,cmp1);

     d[].val=-;

     for(int i=;i<=n;i++)

         if(d[i].val==d[i-].val)

             d[i].w=d[i-].w;

         else d[i].w=++tot;

     sort(d+,d+n+,cmp2);

     for(int i=;i<=n;i++)

         a[i]=d[i].w;

 }

 int check(int ans)

 {

     int i,cnt=;

     for(i=;i<=n;)

     {

         if(h[i]<ans) {i++;continue;}

         for(cnt=;h[i]>=ans&&i<=n;i++)

             cnt++;

         if(cnt>=K-) return ;

     }return ;

 }

 int main()

 {

     scanf("%d%d",&n,&K);len=n;

     for(int i=;i<=n;i++)

         d[i].val=gint(),d[i].id=i;

     descrete();

     get_sa();

     get_height();

     int l=,r=n,ans=;

     while(l<=r){

         int mid=(l+r)>>;

         if(check(mid)) ans=mid,l=mid+;

         else r=mid-;

     }printf("%d\n",ans);

     return ;

 }

相关文章