[Educational Round 5][Codeforces 616F. Expensive Strings]

這題調得我心疲力竭...Educational Round 5就過一段時間再發了_(:з」∠)_

先后找了三份AC代碼對拍，結果有兩份都會在某些數據上出點問題...這場的數據有點水啊_(:з」∠)_【然而卡掉本弱還是輕輕松松的】

題目鏈接：616F - Expensive Strings

題目大意：給出\(n\)個字符串\(t_i\)以及\(n\)個數\(c_i\)，定義\(p_{s,i}\)為字符串\(s\)在\(t_i\)中出現的次數，\(f(s)=\sum_{i=1}^{n}c_i\cdot p_{s,i}\cdot |s|\)，求\(f(s)\)的最大值

題解：考慮將\(n\)個字符串用互不相同的字符串連接起來，并求出新串的后綴數組。對于一段連續且合法（對任意i，有sa[i]對應的字符不為連接符）的區間\([l,r]\)，其對應的答案就為\(min\left \{ height_i \right \}\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_i\cdot \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\n",ans);
}

?