题解：CF2048C Kevin and Binary Strings

原题链接

• 洛谷 CF2048C Kevin and Binary Strings

题意简述

给定一个以 $\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;
}