题解：CF2048C Kevin and Binary Strings

lailai0916 · 2024-12-21 15:32:58 · 题解

题意简述

给定一个以 \texttt{1} 开头的 \texttt{01} 字符串 s，选取两个子串，使得它们的异或和最大。

解题思路

设字符串 s 的长度为 n，并定义字符串 t 为字符串 s 的按位取反。

显然，第一个子串应选取整个字符串 s[0:n-1]，因为只有这样才能保证第一个位置的 \texttt{1} 在异或操作中发挥最大作用。

接下来的目标是让第二个子串的异或结果尽可能大。为了实现这一点，我们需要找到最右边的一个 \texttt{0}，设其位置为 m。为了最大化异或结果，我们要将这个 \texttt{0} 变为 \texttt{1}，因此我们需要选择一个以 \texttt{1} 开头、长度为 n-m+1 的子串。

将第二个子串的选择转化为在字符串 t[0, m-1] 中匹配字符串 s[m, m]。如果能够找到匹配的子串，则继续向右进行匹配，直到无法再找到合适的匹配为止。在每次匹配时，右边的部分也要尽量变为 \texttt{1}，即在 t[0, i-1] 匹配 s[m, i]，依此类推。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=5005;
int nxt[N];
int kmp(string s,string t)
{
    int n=s.size(),m=t.size();
    for(int i=1;i<m;i++)
    {
        int j=nxt[i-1];
        while(j&&t[i]!=t[j])j=nxt[j-1];
        if(t[i]==t[j])j++;
        nxt[i]=j;
    }
    int j=0;
    for(int i=0;i<n;i++)
    {
        while(j&&s[i]!=t[j])j=nxt[j-1];
        if(s[i]==t[j])j++;
        if(j==m)return i-m+1;
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        string s;
        cin>>s;
        int n=s.size(),m=n-1;
        string t=s;
        for(int i=n-1;i>=0;i--)
        {
            t[i]='0'+'1'-t[i];
            if(s[i]=='0')m=i;
        }
        int x=0;
        for(int i=m;i<n;i++)
        {
            int k=kmp(t.substr(0,i),s.substr(m,i-m+1));
            if(k==-1)break;
            x=k;
        }
        cout<<1<<' '<<n<<' '<<x+1<<' '<<x+n-m<<'\n';
    }
    return 0;
}