题解：P13885 [蓝桥杯 2023 省 Java/Python A] 反异或 01 串

__EternalLife__ · 2026-08-08 11:56:15 · 题解

容易发现 s' 一定是一个回文串。

然后我们肯定想尽可能的使得 s' 内的 1 数量多（因为这样只用加一半的 1）。

然后就通过马拉车找到 T 的回文子串 S 使得含 1 的数量最多，用前缀和记录 1 的个数，作差比较即可。

注意，这个回文子串的回文中心不能是 1，因为根本不可能通过 s\oplus rev(s) 构造出一个回文中心为 1 的回文串。

设 S 中的 1 数量为 cnt，T 中的 1 数量为 sum，则答案为 sum-\frac{cnt}{2}。 :::success[Code]

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=4e6+10;
string s1,s2;
int p[maxn],id,ans;
int pre[maxn];
int n;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>s1;
    s2.resize(maxn);
    s2[n]='~'; s2[++n]='|';
    for(int i=0;i<s1.size();i++){
        s2[++n]=s1[i];
        if(s1[i]=='1') pre[n]=1;
        s2[++n]='|';
    }
    for(int i=1;i<=n;i++) pre[i]+=pre[i-1];
    for(int i=1,r=0,mid=0;r<=n;i++){
        if(i<r) p[i]=min(p[mid*2-i],r-i+1);
        while(s2[i+p[i]]==s2[i-p[i]]) p[i]++;
        if(i+p[i]>r) r=i+p[i]-1,mid=i;
        if(s2[i]=='1') continue;
        if((pre[i+p[i]-1]-pre[i-p[i]])>(pre[id+ans]-pre[id-ans-1])) id=i,ans=p[i]-1;
    }
    int cnt=0;
    for(int i=id-ans;i<=id+ans;i++){
        if(s2[i]=='1') cnt++;
    }
    cout<<pre[n]-cnt/2;
    return 0;
}

::: 时间复杂度 O(n)。