正文

解题：USACO06DEC Milk Patterns

IP云
IP云V管理员/0 阅读
09/10
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题面

初见SA

用了一个常见的按$height$分组的操作：二分答案，然后按$height$分组，遇到一个$height$小于$mid$的就丢进下一组并更新答案，如果最多的那组不少于$k$个说明可行

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int uni[N],num[N],sec[N],bkt[N];
int SA[N],rnk[N],hgt[N];
int n,k,l,r,ans,siz;
void Basenum_Sort()
{
register int i;
for(i=;i<=siz;i++) bkt[i]=;
for(i=;i<=n;i++) bkt[rnk[i]]++;
for(i=;i<=siz;i++) bkt[i]+=bkt[i-];
for(i=n;i;i--) SA[bkt[rnk[sec[i]]]--]=sec[i];
}
void Suffix_Sort()
{
register int i;
int pw=,cnt=;
Basenum_Sort();
while(cnt<n)
{
cnt=;
for(i=;i<=pw;i++) sec[++cnt]=n-pw+i;
for(i=;i<=n;i++) if(SA[i]>pw) sec[++cnt]=SA[i]-pw;
Basenum_Sort(); swap(rnk,sec); rnk[SA[]]=cnt=;
for(i=;i<=n;i++) cnt+=(sec[SA[i-]]!=sec[SA[i]]||sec[SA[i-]+pw]!=sec[SA[i]+pw]),rnk[SA[i]]=cnt;
pw<<=,siz=cnt;
}
}
void Getting_Height()
{
int p=;
for(int i=;i<=n;i++)
if(rnk[i]!=)
{
int r=SA[rnk[i]-];
while(num[r+p]==num[i+p]) p++;
hgt[rnk[i]]=p; if(p>) p--;
}
hgt[]=;
}
bool check(int x)
{
register int i;
int len=,lst=;
for(i=;i<=n;i++)
if(hgt[i]<x)
len=max(i-lst,len),lst=i;
len=max(n-lst+,len);
return len>=k;
}
int main()
{
register int i;
scanf("%d%d",&n,&k);
for(i=;i<=n;i++)
scanf("%d",&num[i]),uni[i]=num[i];
sort(uni+,uni++n),siz=unique(uni+,uni++n)-uni-;
for(i=;i<=n;i++)
rnk[i]=lower_bound(uni+,uni++siz,num[i])-uni,sec[i]=i;
Suffix_Sort(); Getting_Height(); l=,r=n;
while(l<=r)
{
int mid=(l+r)/;
if(check(mid)) ans=mid,l=mid+;
else r=mid-;
}
printf("%d",ans);
return ;
}

Upd：SAM对SA的全面替换已完成

这题丢给SAM就没啥可说的了，直接按定义来就行

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#define umap unordered_map
using namespace std;
const int N=;
umap<int,int> trs[N];
int p[N],noww[N],goal[N];
int fth[N],len[N],siz[N];
int rd,lth,kth,cnt,tot,lst,ans;
void Link(int f,int t)
{
noww[++cnt]=p[f];
goal[cnt]=t,p[f]=cnt;
}
void Insert(int ch)
{
int nde=lst,newn=++tot; lst=newn;
siz[newn]=,len[newn]=len[nde]+;
while(nde&&!trs[nde].count(ch))
trs[nde][ch]=newn,nde=fth[nde];
if(!nde) fth[newn]=;
else
{
int tran=trs[nde][ch];
if(len[tran]==len[nde]+)
fth[newn]=tran;
else
{
int rnde=++tot;
len[rnde]=len[nde]+,trs[rnde]=trs[tran];
fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde;
while(nde&&trs[nde][ch]==tran)
trs[nde][ch]=rnde,nde=fth[nde];
}
}
}
void DFS(int nde)
{
for(int i=p[nde];i;i=noww[i])
DFS(goal[i]),siz[nde]+=siz[goal[i]];
}
int main()
{
register int i;
scanf("%d%d",&lth,&kth),lst=tot=;
for(i=;i<=lth;i++) scanf("%d",&rd),Insert(rd);
for(i=;i<=tot;i++) Link(fth[i],i); DFS();
for(i=;i<=tot;i++)
if(siz[i]>=kth) ans=max(ans,len[i]);
printf("%d",ans);
return ;
}