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

zpy12345 · 2026-08-07 10:48:03 · 题解

Link

我们可以将一个w拆成两个v，直接做 Manacher 即可。但是如果一个区间只包含了一个w拆出的两个v中的其中一个，且没有包含另外一个，这样是不合法的。我们可以将一个w拆出来的两个v都赋上 1，这样求一下区间异或和，如果是 0 即为合法区间。

注意答案需要在 Manacher 动态扩展的过程中同步更新。

#include<bits/stdc++.h>
using namespace std;
const int N=5e7+5;
int t,n,r[N],b[N],s[N];
char a[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        int cnt=0;
        a[++cnt]='*';
        a[++cnt]='#';   
        string str;
        cin>>str;
        for(int i=1;i<=n;i++)
        {
            a[++cnt]=str[i-1];

            if(a[cnt]=='w')
            {
                a[cnt]='v';
                b[cnt]=1;
                a[++cnt]='#';
                b[cnt]=0;
                a[++cnt]='v';
                b[cnt]=1;
                a[++cnt]='#';
                b[cnt]=0;
            }
            else b[cnt]=2,a[++cnt]='#',b[cnt]=0;

        }
        a[++cnt]='&';
        n=cnt;
        int mxl=1,mxr=1,p=1;
        for(int i=1;i<=n;i++) s[i]=s[i-1]+b[i];
    //  for(int i=2;i<n;i++) cout<<a[i]<<" ";
    //  cout<<"\n";
        int ans=0,la=0,ra=0;
        for(int i=2;i<n;i++)
        {
            if(i>mxr) r[i]=1;
            else
            {
                int j=p*2-i;
                r[i]=min(r[j],mxr-i+1);
            }
            if((s[i+r[i]-1]-s[i-r[i]])%2==0&&(s[i+r[i]-1]-s[i-r[i]])/2>ans) 
            {
                ans=(s[i+r[i]-1]-s[i-r[i]])/2;
                la=i-r[i]+1,ra=i+r[i]-1;
            }
            while(i+r[i]<=n&&i-r[i]>=1&&a[i+r[i]]==a[i-r[i]]) 
            {
                r[i]++; 
                    if((s[i+r[i]-1]-s[i-r[i]])%2==0&&(s[i+r[i]-1]-s[i-r[i]])/2>ans) 
            {
                ans=(s[i+r[i]-1]-s[i-r[i]])/2;
                la=i-r[i]+1,ra=i+r[i]-1;
            }
            }
            if(mxr<=i+r[i]-1) mxl=i-r[i]+1,mxr=i+r[i]-1,p=i;
        //  cout<<r[i]<<" ";
        }

    /*  for(int i=2;i<n;i++)
        {
            int l=i-r[i]+1,rr=i+r[i]-1;
            int sum=s[rr]-s[l-1];
            if(sum%2) r[i]--;
            if(!r[i]) continue ;
            l=i-r[i]+1,rr=i+r[i]-1;
            sum=s[rr]-s[l-1];
            if(sum%2) continue ;
            if(sum/2>ans) ans=sum/2,la=i-r[i]+1,ra=i+r[i]-1;
        }*/
        for(int i=la;i<=ra;i++)
        {
            if(a[i]=='#') continue ;
            if(a[i]=='o') cout<<a[i];
            else if(a[i]=='v')
            {
                if(b[i]==1) 
                {
                    cout<<"w";
                    i+=2;
                }
                else cout<<a[i];
            }
            else continue ;
        }
        cout<<"\n";
    }
    return 0;
}