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

· · 题解

前置知识

Manacher 算法，模板 P3805。

题意

给定目标 01 串 T，可以从空串出发，在两端任意添加 0 或 1，并最多进行一次反异或操作 s' = s \oplus rev(s)，求得到 T 所需的最少 1 的数量。

思路

每次只能在两端添加 0 或 1，那么题目可以转化为：存在一个与目标串 T 等长的串 S，对 S 的某一子串执行反异或得到 T，求 S 中 1 的最少个数。

核心结论

反异或后的字符串必为回文串。

:::info[证明]{close} 设串 s 长度为 n。

对任意位置 i，有：

s'_{n-1-i} = s_{n-1-i} \oplus \text{rev}(s)_{n-1-i} = s_{n-1-i} \oplus s_i = s_i \oplus s_{n-1-i} = s'_i

故 \forall i, s'_i = s'_{n-1-i}，即反异或后的字符串是回文串。 :::

要让 S 中的 1 尽可能少，需遵循：

找到 T 中最长回文子串，统计其中 1 的数量 cnt，这部分 1 可由 \frac{cnt}{2} 个 1 得到。

最终答案为 T 中 1 的总数 - \frac{cnt}{2}。

需注意反异或后回文中心必为 0，所以回文中心不能是 1。

快速统计子串中 1 的数量可用前缀和预处理优化。

代码实现

#include <iostream>
#include <vector>
using namespace std;
string s,str="#";
int cnt=0,pre[2000005];
int manacher(string s)
{
    int n=s.size();
    vector<int> p(n,0);
    int mx=0,id=0,ans=0;
    for(int i=0;i<n;i++)
    {
        if(i<mx) p[i]=min(p[2*id-i],mx-i);
        else p[i]=1;
        while(i-p[i]>=0&&i+p[i]<n&&s[i-p[i]]==s[i+p[i]]) p[i]++;
        if(i+p[i]>mx)
        {
            mx=i+p[i];
            id=i;
        }
        if(s[i]=='1') continue;//回文中心只能是0或#
        ans=max(ans,pre[i+p[i]]-pre[i-p[i]]);//前缀数组差分计算子串内1的数量
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>s;
    for(char c:s)//预处理
    {
        str.push_back(c);
        str.push_back('#');
        cnt+=(c=='1');
    }
    if(cnt==0)//特判：T内无1，加0即可
    {
        cout<<0<<endl;
        return 0;
    }
    for(int i=0;i<str.size();i++)//预处理前缀数组
    {
        pre[i+1]=pre[i]+(str[i]=='1');
    }
    cout<<cnt-manacher(str)/2<<'\n';
    return 0;
}