51nod 1393 0和1相等串 （思维+前缀和）

1393 0和1相等串

1. 1.0 秒
2.  
3. 131,072.0 KB
4.  
5. 20 分
6.  
7. 3级题

给定一个0-1串，请找到一个尽可能长的子串，其中包含的0与1的个数相等。

 收起

输入

一个字符串，只包含01，长度不超过1000000。

输出

一行一个整数，最长的0与1的个数相等的子串的长度。

输入样例

1011

输出样例

2

分析：

把1看成1，把0看成-1，然后求sum[i]-sum[j-1]==0的最大的i-j的值，其实就是第一次出现该值的位置和最后一次出现该值位置差值，所以用一个map记录一下一开始出现的值即可

或者

当0和1的差值与上一个0和1的差值相同时，那么他们之间的字符串中0和1的数目是相同的。求出最大的就行了。但麻烦点

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const int N=2000000+7;
int sum[N];
string s;
map<int,int>mp;
int main()
{cin>>s;int n=s.size();int ans=0;for(int i=0;i<s.size();i++){sum[i+1]=sum[i]+(s[i]=='1'?1:-1);if(sum[i+1]==0){ans=i+1;}}for(int i=1;i<=n;i++){if(mp[sum[i]]==0){mp[sum[i]]=i;}if(mp[sum[i]]==1){ans=max(ans,i-mp[sum[i]]);}}printf("%d\n",ans);return 0 ;
}