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

· · 题解

Manacher 板子题。

很明显我们可以吧一个 w 拆成两个 v。但是拆完直接跑 Manacher 是肯定不对的。首先因为对于一个 w 而言，它的贡献为一，但是两个 v 直接算贡献为二，所以我们应将 w 拆成的两个 v 的贡献设为 0.5。其次，回文子串中不能只包含 w 拆成的两个 v 中的一个。很显然这是不合法的。可以加个数组进行标记。

然后跑 Manacher 即可。

非常的简单。

::::success[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=4e7+5;
string s,s1;
int len,t,n;
int d[N];
double sum[N];
bool flag[N],f[N];
double b(int x,int y){
    return sum[x+y-1]-sum[x-y];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>s1;
        len=0;
        s=" ";
        for(int i=0;i<n;++i){
            if(s1[i]!='w')s+=s1[i],sum[++len]=1,flag[len]=0;
            else{
                s+="v";
                sum[++len]=0.5;
                flag[len]=1;
                s+='#';
                sum[++len]=0;
                flag[len]=0;
                s+="v";
                sum[++len]=0.5;
                flag[len]=1;
            }
            s+='#';
            flag[++len]=0;
            sum[len]=0;
        }
        for(int i=1;i<=len;++i){
            sum[i]+=sum[i-1];
            f[i]=flag[i];
            flag[i]^=flag[i-1];
        }
        int ans=N-1,mx=1;
        for(int i=1,mid=0,r=0;i<=len;++i){
            d[i]=1;
            if(i<r) d[i]=min(d[2*mid-i],r-i);
            if(flag[i-d[i]]==flag[i+d[i]-1]){
                if(b(ans,mx)<b(i,d[i])){
                    ans=i;
                    mx=d[i];
                }
            }
            while(s[i-d[i]]==s[i+d[i]]){
                d[i]++;
                if(flag[i-d[i]]==flag[i+d[i]-1]){
                    if(b(ans,mx)<b(i,d[i])){
                        ans=i;
                        mx=d[i];
                    }
                }
            }
            if(i+d[i]>r){
                mid=i;
                r=i+d[i];
            }
        }
        for(int i=ans-mx+1;i<=ans+mx-1;){
            if(f[i]){
                i+=3;
                cout<<"w";
            }else{
                if(s[i]!='#')cout<<s[i];
                i++;
            }
        }
        cout<<'\n';
    }
    return 0;
}

::::