首页 > 代码库 > BZOJ3238: [Ahoi2013]差异
BZOJ3238: [Ahoi2013]差异
3238: [Ahoi2013]差异
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 437 Solved: 213
[Submit][Status]
Description
Input
一行,一个字符串S
Output
一行,一个整数,表示所求值
Sample Input
cacao
Sample Output
54
HINT
2<=N<=500000,S由小写英文字母组成
题解:
刚看到题目,想着求出height然后搞出每个点作为最小值向右向左拓展的最远距离,然后这段里面随便取两个lcp都是这个height[i],然后就行了吧。
写完发现不对,两个点必须跨越这个i,发现还是过不了样例。。。
然后想到如果跨越了两个最小值怎么办!!!按照上面的算法我们就计算了两次!!!
然后想不到什么好的解决方法。。。那就乱搞吧
for1(i,n)l[i]=max(last[h[i]],l[i]),last[h[i]]=i;
总算过了样例,抱着必WA的心态交了居然A了!!!
然后想了想发现这样做是正确的?跨越两次的左端点一定在last[h[i]]左边,那么我们下一次计算的时候把这部分直接去掉就OK了。
代码:
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 60000014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 int n,m,last[maxn],a[maxn],c[maxn],t1[maxn],t2[maxn],sa[maxn],rk[maxn],h[maxn],sta[maxn],l[maxn],r[maxn];32 char s[maxn];33 ll sum[maxn];34 void getsa(int m)35 {36 int *x=t1,*y=t2;37 for0(i,m)c[i]=0;38 for0(i,n)c[x[i]=a[i]]++;39 for1(i,m)c[i]+=c[i-1];40 for3(i,n,0)sa[--c[x[i]]]=i;41 for(int k=1;k<n+1;k<<=1)42 {43 int p=0;44 for2(i,n-k+1,n)y[p++]=i;45 for0(i,n)if(sa[i]>=k)y[p++]=sa[i]-k;46 for0(i,m)c[i]=0;47 for0(i,n)c[x[y[i]]]++;48 for1(i,m)c[i]+=c[i-1];49 for3(i,n,0)sa[--c[x[y[i]]]]=y[i];50 swap(x,y);p=0;x[sa[0]]=0;51 for1(i,n)x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p;52 if(p>n)break;53 m=p;54 }55 for1(i,n)rk[sa[i]]=i;56 for(int i=0,k=0,j;i<n;h[rk[i++]]=k)57 for(k?k--:0,j=sa[rk[i]-1];a[i+k]==a[j+k];k++);58 }59 int main()60 {61 freopen("input.txt","r",stdin);62 freopen("output.txt","w",stdout);63 scanf("%s",s);n=strlen(s);64 for0(i,n-1)a[i]=s[i]-‘a‘+1;a[n]=0;65 getsa(26);66 h[0]=h[n+1]=-1;67 int top=0;68 for1(i,n+1)69 {70 while(top&&h[sta[top]]>h[i])r[sta[top--]]=i-1;71 sta[++top]=i;72 }73 top=0;74 for3(i,n,0)75 {76 while(top&&h[sta[top]]>h[i])l[sta[top--]]=i+1;77 sta[++top]=i;78 }79 for1(i,n)l[i]=max(l[i]-1,1);80 for1(i,n)l[i]=max(last[h[i]],l[i]),last[h[i]]=i;81 for1(i,n)sum[i]=sum[i-1]+n-sa[i];82 //for1(i,n)cout<<i<<‘ ‘<<sa[i]<<‘ ‘<<h[i]<<‘ ‘<<l[i]<<‘ ‘<<r[i]<<endl;83 ll ans=0;84 for1(i,n)85 {86 //cout<<sum[i-1]-sum[l[i]-1]<<‘ ‘<<sum[r[i]]-sum[i-1]<<endl;87 /*for2(j,l[i],i-1)88 for2(k,i,r[i])89 cout<<j<<‘ ‘<<k<<endl;*/90 ans+=(sum[i-1]-sum[l[i]-1])*(ll)(r[i]-i+1)+(sum[r[i]]-sum[i-1])*(ll)(i-l[i])-(ll)2*(ll)(r[i]-i+1)*(ll)(i-l[i])*(ll)h[i];91 // cout<<i<<‘ ‘<<ans<<endl;92 }93 printf("%lld\n",ans);94 return 0;95 }
UPD:看了题解简直吓尿,什么笛卡尔树,后缀树,分治,SAM一个都不会 QAQ
BZOJ3238: [Ahoi2013]差异
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。