【比赛链接】http://59.61.75.5:8018/contest/225
A. 回文
【题解】
PAM裸题. 考虑回文串的一个回文子串，分两类讨论，一类包含最后一个字符即母串后缀，跳回文树即可. 另一类删去首尾两个字符，沿 PAM dfs 一遍即可.
跳回文树时记得打上标记，使子树内节点不再访问，同时保证时间复杂度. 效率 $O(sum n)$. 期望得分：100.
【代码】
1 #include<bits/stdc++.h> 2 const int maxn=5000000+10; 3 char s[maxn];bool vis[maxn]; 4 int T,n,len[maxn],fail[maxn],ch[maxn][26],cnt,last; 5 long long Ans,ans[maxn]; 6 inline void dfs ( int u,int fr ) 7 { 8 int dep=0,x=u;vis[x]=true; 9 while ( fail[x]>1 and !vis[fail[x]] ) x=fail[x],vis[x]=true,dep++; 10 ans[u]=dep+((fr>1)?(ans[fr]+1):0);Ans+=ans[u]; 11 for ( int i=0;i<26;i++ ) if ( ch[u][i] ) dfs(ch[u][i],u); 12 x=u;vis[x]=false; 13 while ( dep-- ) x=fail[x],vis[x]=false; 14 } 15 int main() 16 { 17 for ( scanf("%d",&T);T--; ) 18 { 19 scanf(" %s",s+1);n=strlen(s+1);Ans=0; 20 last=cnt=0;s[0]='#';fail[0]=1;len[++cnt]=-1; 21 for ( int i=1;i<=n;i++ ) 22 { 23 while ( s[i-len[last]-1]!=s[i] ) last=fail[last]; 24 if ( !ch[last][s[i]-97] ) 25 { 26 len[++cnt]=len[last]+2; 27 int j=fail[last]; 28 while ( s[i-len[j]-1]!=s[i] ) j=fail[j]; 29 fail[cnt]=ch[j][s[i]-97];ch[last][s[i]-97]=cnt; 30 } 31 last=ch[last][s[i]-97]; 32 } 33 dfs(0,0);dfs(1,1);printf("%lld ",Ans); 34 for ( int i=0;i<=cnt;i++ ) 35 { 36 for ( int j=0;j<26;j++ ) ch[i][j]=0; 37 fail[i]=ans[i]=len[i]=0; 38 } 39 } 40 return 0; 41 }
B. Sum of Prefix Sums
【题解】
显然考虑点分治. 考虑两条链的答案如何合并.
记 $sum$ 为前缀和，$S$ 为前缀和的和，需要合并的链为 $a,b$，其中 $a$ 长度 $x$，$b$ 长度 $y$. 则有答案为 $S_a+y imes sum_a +S_b$.
显然 $S_b$ 可以单独处理，且 $a$ 一定时 $S_a+y imes sum_a$ 是关于 $y$ 的一次函数. 李超线段树维护即可.
【代码】
1 #include<bits/stdc++.h> 2 const int maxn=150000+10; 3 struct tree { long long a,b; } t[maxn<<2]; 4 struct node { long long val1,val2,sum,l,x; } st[maxn]; 5 int siz[maxn],son[maxn],tp,n,root,dep[maxn],m; 6 long long a[maxn],ans;bool vis[maxn]; 7 std::vector<int> e[maxn]; 8 #define ls (k<<1) 9 #define rs (k<<1|1) 10 #define mid ((l+r)>>1) 11 inline void build ( int k,int l,int r ) 12 { 13 t[k].a=t[k].b=0; 14 if ( l==r ) return; 15 build(ls,l,mid);build(rs,mid+1,r); 16 } 17 inline void update ( int k,int l,int r,long long a,long long b ) 18 { 19 if ( t[k].a*l+t[k].b<=a*l+b and t[k].a*r+t[k].b<=a*r+b ) { t[k].a=a;t[k].b=b;return; } 20 if ( t[k].a*l+t[k].b>=a*l+b and t[k].a*r+t[k].b>=a*r+b ) return; 21 if ( t[k].a*mid+t[k].b<a*mid+b ) std::swap(t[k].a,a),std::swap(t[k].b,b); 22 if ( a<t[k].a ) update(ls,l,mid,a,b); 23 else update(rs,mid+1,r,a,b); 24 } 25 inline long long query ( int k,int l,int r,int x ) 26 { 27 if ( l==r ) return t[k].a*x+t[k].b; 28 if ( x<=mid ) return std::max(t[k].a*x+t[k].b,query(ls,l,mid,x)); 29 else return std::max(t[k].a*x+t[k].b,query(rs,mid+1,r,x)); 30 } 31 #undef ls 32 #undef rs 33 #undef mid 34 inline void getroot ( int u,int fr,int size ) 35 { 36 siz[u]=1;son[u]=0; 37 for ( int v:e[u] ) if ( !vis[v] and v!=fr ) getroot(v,u,size),siz[u]+=siz[v],son[u]=std::max(son[u],siz[v]); 38 son[u]=std::max(son[u],size-son[u]); 39 if ( son[u]<son[root] ) root=u; 40 } 41 inline void dfs ( int u,int fr,long long val1,long long val2,long long sum,int rt ) 42 { 43 dep[u]=dep[fr]+1;m=std::max(m,dep[u]);siz[u]=1; 44 for ( int v:e[u] ) if ( !vis[v] and v!=fr ) dfs(v,u,val1+sum+a[v],val2+a[v]*dep[u],sum+a[v],rt),siz[u]+=siz[v]; 45 if ( siz[u]==1 ) st[++tp]=(node){val1,val2,sum,dep[u],rt}; 46 } 47 inline void solve ( int u ) 48 { 49 vis[u]=true;tp=0;m=dep[u]=1; 50 for ( int v:e[u] ) if ( !vis[v] ) dfs(v,u,2*a[u]+a[v],a[v]*dep[u],a[u]+a[v],v); 51 st[++tp]=(node){a[u],0,a[u],1,0};st[0].x=st[tp+1].x=-1; 52 for ( int i=1;i<=tp;i++ ) st[i].sum-=a[u]; 53 build(1,1,m); 54 for ( int i=1,j;i<=tp;i=j ) 55 { 56 for ( j=i;st[j].x==st[i].x;j++ ) ans=std::max(ans,query(1,1,m,st[j].l)+st[j].val1); 57 for ( j=i;st[j].x==st[i].x;j++ ) update(1,1,m,st[j].sum,st[j].val2); 58 } 59 build(1,1,m); 60 for ( int i=tp,j;i>=1;i=j ) 61 { 62 for ( j=i;st[j].x==st[i].x;j-- ) ans=std::max(ans,query(1,1,m,st[j].l)+st[j].val1); 63 for ( j=i;st[j].x==st[i].x;j-- ) update(1,1,m,st[j].sum,st[j].val2); 64 } 65 for ( int v:e[u] ) if ( !vis[v] ) root=0,getroot(v,u,siz[v]),solve(root); 66 } 67 signed main() 68 { 69 scanf("%d", &n); 70 for ( int i=1,u,v;i<n;i++ ) scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u); 71 for ( int i=1;i<=n;i++ ) scanf("%lld",&a[i]); 72 son[0]=n;getroot(1,0,n);solve(root); 73 return !printf("%lld ",ans); 74 }
C. Tritwise Mex
【题解】
设 $c=a*b$，记 $a_{i}$ 表示数列 $a$ 所有最低位为 $i$ 的项依序组成的数列，显然有 ：
$$c_{0}=a_{1}*b_{1}+a_{1}*b_{2}+a_{2}*b_{1}+a_{2}*b_{2}=(a_{1}+a_{2})*(b_{1}+b_{2})$$
$$c_{1}=a_{0}*b_{0}+a_{0}*b_{2}+a_{2}*b_{0}=(a_{0}+a_{1}+a_{2})*(b_{0}+b_{1}+b_{2})-(a_{1}+a_{2})*(b_{1}+b_{2})-a_{0}*b_{1}-a_{1}*b_{0}$$
$$c_{2}=a_{0}*b_{1}+a_{1}*b_{0}$$
于是可以用 $4$ 次乘法完成一维计算，效率 $O(4^k - 3^k)$.
【代码】
1 #include<bits/stdc++.h> 2 inline std::vector<long long> mul ( const std::vector<int> &A,const std::vector<int> &B,int n ) 3 { 4 if ( n==1 ) 5 { 6 std::vector<long long> C; 7 C.push_back(1LL*A[0]*B[0]); 8 return C; 9 } 10 n/=3; 11 std::vector<int> A0,B0; 12 for ( int i=0;i<n;i++ ) A0.push_back(A[i+n*2]),B0.push_back(B[i+n*2]); 13 std::vector<long long> C1=mul(A0,B0,n); 14 for ( int i=0;i<n;i++ ) A0[i]+=A[i],B0[i]+=B[i]; 15 std::vector<long long> C2=mul(A0,B0,n); 16 for ( int i=0;i<n;i++ ) A0[i]+=A[i+n],B0[i]+=B[i+n]; 17 std::vector<long long> C3=mul(A0,B0,n); 18 for ( int i=0;i<n;i++ ) A0[i]-=A[i],B0[i]-=B[i]; 19 std::vector<long long> C=mul(A0,B0,n); 20 for ( int i=0;i<n;i++ ) C.push_back(C2[i]-C1[i]); 21 for ( int i=0;i<n;i++ ) C.push_back(C3[i]-C[i]-C[i+n]); 22 return C; 23 } 24 inline int read ( void ) 25 { 26 int x=0;char ch; 27 while ( !isdigit(ch=getchar()) ) ; 28 for ( x=ch^48;isdigit(ch=getchar()); ) x=(x<<1)+(x<<3)+(ch^48); 29 return x; 30 } 31 inline void write ( long long x,char ch ) 32 { 33 int st[50]={0},tp=0; 34 while ( x ) st[++tp]=x%10,x/=10; 35 if ( !tp ) st[++tp]=0; 36 for ( int i=tp;i;i-- ) putchar(st[i]^48); 37 putchar(ch); 38 } 39 signed main() 40 { 41 int n=read(),m=1; 42 for ( int i=1;i<=n;i++ ) m*=3; 43 std::vector<int> A,B; 44 for ( int i=0;i<m;i++ ) A.push_back(read()); 45 for ( int i=0;i<m;i++ ) B.push_back(read()); 46 std::vector<long long> C=mul(A,B,m); 47 for ( int i=0;i<m;i++ ) write(C[i]," "[i==m-1]); 48 return 0; 49 }