这题调得我心疲力竭...Educational Round 5就过一段时间再发了_(:з」∠)_
先后找了三份AC代码对拍，结果有两份都会在某些数据上出点问题...这场的数据有点水啊_(:з」∠)_【然而卡掉本弱还是轻轻松松的】
题目大意：给出(n)个字符串(t_i)以及(n)个数(c_i)，定义(p_{s,i})为字符串(s)在(t_i)中出现的次数，(f(s)=sum_{i=1}^{n}c_icdot p_{s,i}cdot |s|)，求(f(s))的最大值
题解：考虑将(n)个字符串用互不相同的字符串连接起来，并求出新串的后缀数组。对于一段连续且合法（对任意i，有sa[i]对应的字符不为连接符）的区间([l,r])，其对应的答案就为(minleft { height_i ight }cdot sum c_j)，(j)为sa[i]所属原字符串的编号，对应所取的字符串就是这连续几个后缀的最长公共子串。因此若考虑暴力枚举所有的合法区间，会有下面的代码
for(int l=1;l<=len_sum;l++)if(s[sa[l]-1]>N) for(int r=l;r<=len_sum;r++)if(s[sa[r]-1]<N)break;else { LL k=0; int mi=N; for(int i=l+1;i<=r;i++)mi=min(mi,height[i]); if(mi==0)break; if(mi==N) { mi=0; for(int i=sa[l]-1;s[i]>N;i++) mi++; } for(int i=l;i<=r;i++)k+=1ll*mi*c[belong[sa[i]-1]]; ans=max(ans,k); }
但是这样是显然会TLE的，所以需要进一步优化
考虑每一个height[i]的影响范围，即在该范围内，所有包含i的区间都以height[i]为最小值，此时原式的式子就为(height_icdot sum_{i=l}^{r}c_j)，这里(l)，(r)表示的就是height[i]的影响范围，(j)依然为sa[i]所属原字符串的编号。预处理每个height[i]的影响范围以及(c_j)的前缀和就好了
#include<bits/stdc++.h> using namespace std; #define N 600001 #define LL long long int wa[N+1001],wb[N+1001],wv[N+1001],Ws[N+1001]; int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];} void da(const int r[],int sa[],int n,int m) { 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(j=1,p=1; p<n; j*=2,m=p) { for(p=0,i=n-j; i<n; i++) y[p++]=i; for(i=0; i<n; i++) if(sa[i]>=j) 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,p=1,x[sa[0]]=0,i=1; i<n; i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; } return; } int sa[N],Rank[N],height[N]; void calheight(const int *r,int *sa,int n) { int i,j,k=0; for(i=1; i<=n; i++) Rank[sa[i]]=i; for(i=0; i<n; height[Rank[i++]]=k) for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++); for(int i=n;i>=1;--i) ++sa[i],Rank[i]=Rank[i-1]; } char str[N]; LL ans,sum[N]; int n,c[N],s[N],leng[N],belong[N],_l[N],_r[N],len_sum; void rua(int L,int R) { LL res=0,x,le; for(int i=L;i<=R;i++) { x=belong[sa[i]-1]; le=leng[x]-sa[i]+1; if((i==R || height[i+1]<le) && (i==L || height[i]<le)) res=max(res,1ll*le*c[x]); } for(int i=L;i<=R;i++) res=max(res,1ll*height[i]*(sum[min(R,_r[i])]-sum[max(L,_l[i]-1)-1])); ans=max(ans,res); } int main() { scanf("%d",&n); scanf("%s",str); int len=strlen(str); for(int i=0;i<len;i++) belong[len_sum]=1,s[len_sum++]=str[i]+N; leng[1]=len_sum; for(int i=2;i<=n;i++) { s[len_sum++]=i; scanf("%s",str); len=strlen(str); for(int j=0;j<len;j++) belong[len_sum]=i,s[len_sum++]=str[j]+N; leng[i]=len_sum; } da(s,sa,len_sum+1,N+1000); calheight(s,sa,len_sum); for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=len_sum;i++) sum[i]=sum[i-1]+c[belong[sa[i]-1]]; _l[1]=1,_r[len_sum]=len_sum; for(int i=2;i<=len_sum;i++) { int _=i; while(_>1 && height[i]<=height[_-1]) _=_l[_-1]; _l[i]=_; } for(int i=len_sum-1;i>=1;i--) { int _=i; while(_<len_sum && height[i]<=height[_+1]) _=_r[_+1]; _r[i]=_; } for(int l=1;l<=len_sum;l++)if(s[sa[l]-1]>N) { int r=l; while(r<=len_sum && s[sa[r]-1]>N)r++; rua(l,r-1); l=r; } printf("%I64d ",ans); }