首页 > 代码库 > bzoj4650: [Noi2016]优秀的拆分
bzoj4650: [Noi2016]优秀的拆分
考场上没秒的话多拿5分并不划算的样子。
思想其实很简单嘛。
要统计答案，求以每个位置开始和结束的AA串数量就好了。那么枚举AA中A的长度L，每L个字符设一个关键点，这样AA一定经过相邻的两个关键点。计算出相邻关键点的最长公共前后缀，把对应的位置区间加一下。
求lcp和lcs可以用后缀数组，也可以用hash。
#include<bits/stdc++.h>#define N 30005#define M (l+r+1>>1)using std::min;const int m=1000000097;int i,j,n,t,l,r,p,q;int f[N],a[N],u[N],v[N];char s[N];int hash(int i,int j){ return(f[j]-1ll *f[i]*a[j-i]%m+m)%m;}int main(){ for(a[0]=i=1;i<N;++i) a[i]=223ll*a[i-1]%m; scanf("%d",&t); while(t--){ scanf("%s",s+1); n=strlen(s+1); for(i=1;i<=n;++i){ u[i]=v[i]=0; f[i]=(223ll *f[i-1]+s[i])%m; } for(i=1;i*2<=n;++i) for(j=1;j+i<=n;j+=i){ l=0,r=min(i,j); while(l^r) hash(j+i-M,j +i)^hash(j-M, j)?r=M-1:l=M; p=j-l+1; l=0,r=min(i-1,n-j-i); while(l^r) hash(j+i,j+i +M)^hash(j,j +M)?r=M-1:l=M; q=j+l+1; if(p+i<=q){ ++u[p],--v[q+i]; --u[q-i+1]; ++v[p+i*2-1]; } } long long k=0; for(i=1;i<=n;++i){ u[i]+=u[i-1]; v[i]+=v[i-1]; k+=u[i]*v[i-1]; } printf("%lld\n",k); }}
bzoj4650: [Noi2016]优秀的拆分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。