3th.Mar.2019
今天顺带复习一下马拉车
T1
- 据说是sb模拟题，但蒟蒻我实在是不敢苟同，真心不会。大致思路给一下。
T2
- 与上一题比较起来，本题还算很友好了。
- 首先，很容易想到一个\(n^3\)的算法吧，就是枚举一个左端点，枚举一个右端点，再枚举右边串的右端点，hash预处理然后O（1）判断就行。
- 假如我们确定了一个l数组，l[i]表示以i为左端点的所有回文串的右端点之和。那么我们只需要枚举一个左端点和右端点就好了，求答案时直接i*l[j+1]。这样算法变成\(n^2\)的了，不过因为多组数据的缘故，过不了60（难过）。
- 既然处理了l数组，能不能再处理出一个r数组呢？r[i]表示以i为右端点的所有回文串的左端点之和。那么我们求ans的时候，只需要一个for循环，ans+=r[i]*l[i+1]就好了。这样求答案是O（n）的。
- 关键在于我们如何快速处理出l和r数组呢？一个很好想的思路就hash。但是是\(n^2\)的。
- 考虑马拉车算法的时候，我们求的是一个以i为中点的最长回文串。那么显然对于左端点到i这些点的l数组都可以更新，并且加的值是一个等差数列。同理，右边的点都可以处理r数组，也是等差数列。我们可以同时差分两个数组，一个差分是为了加上一个端点的值，另一个差分是为了维护等差数列。那么本题就可以O（n）求了。
Coding
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
const int mod=1e9+7;
int t,n,p[N];char s[N],ss[N];
ll l[N],r[N],ans,c[N],d[N];
void manacher(){
int mx=0,id=0;
for(int i=1;i<=n;++i){p[i]=0;
if(i<mx) p[i]=min(p[2*id-i],mx-i);
else p[i]=1;
while(s[i+p[i]]==s[i-p[i]]) p[i]++;
if(p[i]+i>mx) mx=p[i]+i,id=i;
}
}
int main(){
freopen("triple.in","r",stdin);
freopen("triple.out","w",stdout);
scanf("%d",&t);
while(t--){
ans=0;
scanf("%s",ss+1);
n=strlen(ss+1);
for(int i=1;i<=n;++i){
s[i*2-1]='#';
s[i*2]=ss[i];
}n=n*2;s[++n]='#';
s[0]='$',s[n+1]='^';
manacher();
for(int i=1;i<=n;++i){
c[i+1]--;c[i+p[i]]++;
d[i]+=i;d[i+p[i]]-=(i-p[i]+1);
}
for(int i=1;i<=n;++i){
c[i]+=c[i-1];
l[i]=l[i-1]+c[i]+d[i];
}
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
for(int i=1;i<=n;++i){
c[i+1]++;c[i-p[i]+2]--;
d[i+1]-=i;d[i-p[i]+1]+=(i+p[i]-1);
}
for(int i=1;i<=n;++i){
c[i]+=c[i-1];
r[i]=r[i-1]+c[i]+d[i];
}
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
for(int i=2;i<=n-2;i+=2){
ans=(ans+l[i]*r[i+2]/4%mod)%mod;
l[i]=0;r[i]=0;
}r[n]=r[n+1]=0;
cout<<ans<<endl;
}
return 0;
} T3
40分挺好些的吧，都是dfs就好。不过考场上有点懵看错题意，就0分了。
版权声明：本文为kgxw0430原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。