题解：P15561 [CCPC 2025 哈尔滨站] 幻想乡的裁判长

intabc · 2026-08-07 21:28:31 · 题解

题目传送门

注意到需要求最长回文串，于是使用 manacher。

首先将所有的 w 拆成 vv，通过 w 拆出来的 v 的权值为 0.5，其他的权值为 1。

然后我们跑马拉车，同时计算答案，每一次更新回文半径时判断这一个回文串中的权值之和是否为整数，如果为整数就更新答案。

由于我们是在跑马拉车的同时计算答案的，所以总体的时间复杂度和马拉车是一样的，都是 O(n)。 ::::success[Code]

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
typedef double db;
db vis[40000010];
db sum[40000010];
ll d[40000010];
string s="",s1;
int n,m,ansl,ansr,ans;
void manacher(){
    ll l=0,r=-1;
    for(int i=0;i<m;i++){
        if(i<=r){
            int j=l+r-i;
            d[i]=min(d[j],r-i+1);
        }
        db ss=sum[i+d[i]]-sum[i-d[i]-1];//计算权值
        if(ss>sum[ansr]-sum[ansl-1]&&(int)ss==ss)ansl=i-d[i],ansr=i+d[i];//记录答案
        while(i-d[i]-1>=0&&i+d[i]+1<m&&s[i-d[i]-1]==s[i+d[i]+1]){
            d[i]++;
            ss=sum[i+d[i]]-sum[i-d[i]-1];
            if(ss>sum[ansr]-sum[ansl-1]&&(int)ss==ss)ansl=i-d[i],ansr=i+d[i];
        }
        if(i+d[i]-1>r){
            r=i+d[i]-1;
            l=i-d[i]+1;
        }
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>s1;
        s+='#';
        for(int i=0;i<n;i++){//初始化
            if(s1[i]=='w')s+='v',s+='#',s+='v',vis[m+1]=0.5,vis[m+3]=0.5,m+=4;
            else s+=s1[i],vis[m+1]=1,m+=2;
            s+='#';
        }
        sum[0]=vis[0];
        for(int i=1;i<m;i++)sum[i]=sum[i-1]+vis[i];
        manacher();
        for(int i=ansl;i<=ansr;i++){//合并w来输出答案
            if(s[i]=='#')continue;
            if(vis[i]==0.5){
                cout<<'w';
                i+=3;
            }
            else cout<<s[i];
        }
        cout<<endl;
        for(int i=0;i<m;i++)vis[i]=0,d[i]=0,sum[i]=0;//多测清空
        s="";
        ansl=ansr=ans=0;
        m=0;
    }
    return 0;
}

::::