题解 CF873B 【Balanced Substring】

题意：给出一个$n$长度的01串，其中含有相同0，1个数的子串被称为“平衡串”，问最长的平衡串的长度。

我们可以先将0改变成-1，这样的话，新串中和为0的子串即为原串中“平衡串”。

考虑枚举某一个端点，并判断是否存在可行的另一个端点。在这道题中，我们枚举右端点。

让我们维护一个前缀和数组$sum[i]$。对于某一个右端点$k$，如果存在一个$j\in[1,k-1]$，使得$sum[j]=sum[k]$，那么$\sum_{i=j+1}^ka_i$就一定等于0。这样的话，就形成了一个平衡串。我们可以用一个桶来记录前缀和数组之前是否存在过某个值，就可以$O(1)$判断一个右端点是否对应一个左端点，即可通过本题。

#include<iostream>
using namespace std;
int book[200005];//桶
int main(){
	int n,sum=0,ans=0;
	cin>>n;
	string s;
	cin>>s;
	for(int i=1;i<=n;i++){
		if(s[i-1]=='1')sum++;
		else sum--;//sum记录前缀和
		if(sum==0)ans=max(ans,i); //有可能平衡串出现在最开始的某一个串
		if(book[sum+100000]==0)book[sum+100000]=i;
		else ans=max(ans,i-book[sum+100000]);
        //注意：1.桶内如果已经有了元素，那么不要改变它，因为左端点越靠左越好
        //2.因为前缀和有可能<0，那么我们需要整体移动桶的下标
	}
	cout<<ans;
	return 0;
}