[bzoj4698][Sdoi2008]Sandy的卡片_后缀数组_二分/单调队列_双指针

Sandy的卡片 bzoj-4698 Sdoi-2008

题目大意题目链接

注释:略。


想法

这个题跟一个Usaco的题特别像。我们把这些串差分

现在我们要求的就是公共子串且出现次数不少于$k$的最长长度。

紧接着把这$n$新串拼一起建立后缀数组。

两种做法:

第一种是二分。我们直接二分答案然后暴力扫验证,复杂度为$O(nlogn)$。

第二种就是双指针保证当前指针中间是满足条件的最短区间,顺便用单调队列求区间$ht$最小值即可。

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000050
int r[N],sa[N],wa[N],wb[N],wv[N],rk[N],ht[N],n,Ws[N],cnt,idx[N],H[1050],tot,ans,Q[N],m;
int w[100050];
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
void build_sa()
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++) Ws[i]=0;
for(i=0;i<n;i++) Ws[x[i]=r[i]]++;
for(i=1;i<m;i++) Ws[i]+=Ws[i-1];
for(i=n-1;i>=0;i--) sa[--Ws[x[i]]]=i;
for(p=j=1;p<n;j<<=1,m=p)
{
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]-j>=0) y[p++]=sa[i]-j;
for(i=0;i<n;i++) wv[i]=x[y[i]];
for(i=0;i<m;i++) Ws[i]=0;
for(i=0;i<n;i++) Ws[wv[i]]++;
for(i=1;i<m;i++) Ws[i]+=Ws[i-1];
for(i=n-1;i>=0;i--) sa[--Ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,i=p=1,x[sa[0]]=0;i<n;i++)
{
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]) x[sa[i]]=p-1;
else x[sa[i]]=p++;
}
}
for(i=1;i<n;i++) rk[sa[i]]=i;
for(i=p=0;i<n-1;ht[rk[i++]]=p)
for(p?p--:0,j=sa[rk[i]-1];r[i+p]==r[j+p];p++);
}
int main()
{
int i,j=0;
cnt=rd();
int minn=1<<30,maxx=0;
for(j=1;j<=cnt;j++)
{
int lim;
lim=rd();
for(i=0;i<lim;i++) w[i]=rd();
for(i=1;i<lim;i++) idx[n]=j,r[n++]=w[i]-w[i-1],minn=min(minn,r[n-1]),maxx=max(maxx,r[n-1]);
n++;
}
m=maxx-minn+1;
for(i=0;i<n;i++)
{
if(idx[i]) r[i]-=minn-1;
else r[i]=m+1;
}
r[n++]=0; m+=2;
build_sa();
int ll=0,rr=0; j=0;
for(i=0;i<n;i++)
{
H[idx[sa[i]]]++; if(H[idx[sa[i]]]==1&&idx[sa[i]]) tot++;
while(ll<rr&&ht[Q[rr-1]]>ht[i]) rr--;
Q[rr++]=i;
if(tot!=cnt) continue;
while(j<i&&tot==cnt)
{
H[idx[sa[j]]]--;
if(H[idx[sa[j]]]==0&&idx[sa[j]]) tot--;
j++;
}
j--; H[idx[sa[j]]]++;
if(H[idx[sa[j]]]==1&&idx[sa[j]]) tot++;
while(ll<rr&&Q[ll]<=j) ll++;
if(tot==cnt)
{
ans=max(ans,ht[Q[ll]]);
}
}
printf("%d\n",ans+1);
return 0;
}

小结:好题好题。一般情况下后缀数组的考点就是在$ht$上搞事情,多注意点儿即可。

上一篇:11个优秀的Android开发开源项目


下一篇:[BZOJ4698][SDOI2008]Sandy的卡片(后缀自动机)