目录
A 回文串
给定字符串 \(S\)。对 \(S\) 的所有回文子串，求其长度与出现次数之积的最大值。
\(|S| \le 300000\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=3e5+5;
int n,m,a[N<<1],lg2[N],cnt,str[N<<2][2];
int S,x[N],y[N],c[N],sa[N],rk[N],h[N],mn[N][25];
ll ans;char s[N],t[N<<1];
void SA(){
S=300;
for(int i=1;i<=n;i++){x[i]=s[i];++c[x[i]];}
for(int i=2;i<=S;i++)c[i]+=c[i-1];
for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=1;i<=S;i++)c[i]=0;
for(int i=1;i<=n;i++)c[x[i]]++;
for(int i=2;i<=S;i++)c[i]+=c[i-1];
for(int i=n;i>=1;i--){sa[c[x[y[i]]]--]=y[i];y[i]=0;}
for(int i=1;i<=n;i++)swap(x[i],y[i]);
num=1;x[sa[1]]=1;
for(int i=2;i<=n;i++){
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])
x[sa[i]]=num;
else x[sa[i]]=++num;
}
if(num==n)break;S=num;
}
}
void LCP(){
int k=0;
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1;i<=n;i++){
if(rk[i]==1)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
h[rk[i]]=k;
}
}
void build_ST(){
for(int i=1;i<=n;i++)mn[i][0]=h[i];
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i<=n-(1<<j)+1;i++)
mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]);
}
int query(int l,int r){
if(l>r)return 0;
int i=lg2[r-l+1];int j=(1<<i);
return min(mn[l][i],mn[r-j+1][i]);
}
void Manacher(){
int l=1,r=0;
for(int i=1;i<=m;++i){
if(r>=i&&i+a[l+r-i]<=r)a[i]=a[l+r-i];
else{
int k=max(0,r-i);
while(i+k<=m&&i-k>=1&&t[i+k]==t[i-k]){
++k;++cnt;
str[cnt][0]=(i-k+2)/2;str[cnt][1]=(i+k-1)/2;
if(str[cnt][0]>str[cnt][1])--cnt;
}
a[i]=k;l=i-k+1;r=i+k-1;
}
}
}
ll solve(int l,int r){
int L=0,R=0,p1=0,p2=0;
L=2;R=rk[l];p1=rk[l]+1;
while(L<=R){
int mid=L+R>>1;
if(query(mid,rk[l])>=r-l+1)p1=mid,R=mid-1;
else L=mid+1;
}
L=rk[l]+1;R=n;p2=rk[l];
while(L<=R){
int mid=L+R>>1;
if(query(rk[l]+1,mid)>=r-l+1)p2=mid,L=mid+1;
else R=mid-1;
}
return 1ll*(p2-p1+2)*(r-l+1);
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);m=2*n+1;t[1]='#';
for(int i=0;(1<<i)<=n;i++)lg2[1<<i]=i;
for(int i=1,lst=0;i<=n;i++){
if(lg2[i])lst=lg2[i];
else lg2[i]=lst;
}
for(int i=n;i>=1;--i)t[2*i]=s[i],t[2*i+1]='#';
Manacher();SA();LCP();build_ST();
for(int i=1;i<=cnt;i++)ans=max(ans,solve(str[i][0],str[i][1]));
printf("%lld\n",ans);
return 0;
}
B 序列分割
将长为 \(n\) 的数组分 \(k\) 次，每次在某一段内部将其分成两段，得分是分出两段的元素和的乘积。\(k\) 次操作的总得分是每次得分之和。求最大得分并输出方案。
\(n \le 100000\)，\(k \le 200\)，\(k \lt n\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,K=205;
int n,k,lst[K][N];
ll dp[K][N],s[N],b[N],sum;
int q[N],he,ta;
int main(){
scanf("%d%d",&n,&k);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
s[i]=s[i-1]+x;sum+=x;
}
memset(dp,0x3f,sizeof(dp));
for(int j=1;j<=n;j++)dp[1][j]=s[j]*s[j];
for(int i=2;i<=k+1;i++){
he=ta=1;q[1]=i-1;
b[i-1]=s[i-1]*s[i-1]+dp[i-1][i-1];
for(int j=i;j<=n;j++){
while(he<ta&&(b[q[he+1]]-b[q[he]])<=2*s[j]*(s[q[he+1]]-s[q[he]]))++he;
dp[i][j]=s[j]*s[j]-2*s[q[he]]*s[j]+b[q[he]];lst[i][j]=q[he];
b[j]=s[j]*s[j]+dp[i-1][j];
while(ta>he&&(b[j]-b[q[ta-1]])*(s[j]-s[q[ta]])>=
(b[j]-b[q[ta]])*(s[j]-s[q[ta-1]]))--ta;
q[++ta]=j;
}
}
printf("%lld\n",(sum*sum-dp[k+1][n])/2);
for(int i=k,j=lst[k+1][n];i>=1;i--){
printf("%d ",j);
j=lst[i][j];
}
return 0;
}
C 连珠线
初始有一个点，用如下两种操作生成一棵树：
Append(w, v)：一个新的点 \(w\) 和一个已经添加的点 \(v\) 用红边连接起来。
Insert(w, u, v)：一个新的点 \(w\) 插入到用红边连起来的两个点 \(u, v\) 之间。具体过程是删去 \(u, v\) 之间红边，分别用蓝边连接 \(u, w\) 和 \(w, v\)。
给定 \(n\) 个点的最终状态。求蓝边权值之和的最大可能值。
\(n \le 200000\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,INF=1<<29;
int n,dp[N][2],g[N][2],ans;
int head[N],nxt[N<<1],ver[N<<1],val[N<<1],tot;
int max(int a,int b){return a>b?a:b;}
void add(int u,int v,int w){
ver[++tot]=v;
val[tot]=w;
nxt[tot]=head[u];
head[u]=tot;
}
void dfs(int u,int fa){
dp[u][0]=0;g[u][0]=g[u][1]=-INF;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v==fa)continue;
dfs(v,u);
int tmp=max(dp[v][0],dp[v][1]+val[i]);
dp[u][0]+=tmp;
tmp=dp[v][0]+val[i]-tmp;
if(tmp>g[u][0])g[u][1]=g[u][0],g[u][0]=tmp;
else if(tmp>g[u][1])g[u][1]=tmp;
}
dp[u][1]=g[u][0]+dp[u][0];
}
void redfs(int u,int fa,int in){
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v==fa)continue;
int t0=dp[u][0],t1=dp[u][1],t2=dp[v][0],t3=dp[v][1];
int tmp=max(dp[v][0],dp[v][1]+val[i]);
dp[u][0]=dp[u][0]-tmp;
if(g[u][0]==val[i]+dp[v][0]-tmp)dp[u][1]=dp[u][0]+max(in,g[u][1]);
else dp[u][1]=dp[u][0]+max(in,g[u][0]);
tmp=max(dp[u][0],dp[u][1]+val[i]);
dp[v][0]=dp[v][0]+tmp;
dp[v][1]=dp[v][0]+max(g[v][0],val[i]+dp[u][0]-tmp);
ans=max(ans,dp[v][0]);
redfs(v,u,val[i]+dp[u][0]-tmp);
dp[u][0]=t0;dp[u][1]=t1;dp[v][0]=t2;dp[v][1]=t3;
}
}
int main(){
scanf("%d",&n);
for(int i=1,u,v,w;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
dfs(1,-1);ans=dp[1][0];
redfs(1,-1,-INF);
printf("%d\n",ans);
return 0;
}