2019牛客多校训练第三场B.Crazy Binary String（思维+前缀和）

题目传送门

大致题意：

输入整数n（1<=n<=100000)，再输入由n个0或1组成的字符串，求该字符串中满足1和0个数相等的最长子串、子序列。

sample input：

8
01001001

sample output：

4 6

题解：

补充一下子串和子序列的区别：字串必须连续，子序列不必连续。

求01个数相等的最长子序列长度：min（0的个数，1的个数）。

下面说求01个数相等的最长子串长度：

可以建一个sum数组求前缀和，因为要使0和1个数相等，所以0可以用-1代替，故当sum[r]-sum[l-1]=0时区间[l,r]则为满足01个数相等的子串，此时求出l-1和r的差值即为满足条件的子串长度，不断更新结果求最大长度。

但是到这一步后起初想到的做法是两重循环枚举更新最大差值，这样会超时。

O(n)做法：建一个flag数组记录不同前缀和第一次出现的下标位置（也可用map记录），后面找到相同前缀和时则更新两者位置的差值，这样扫一遍就可以了。（注意：当前缀和sum[r]=0时，r即为满足条件的子串长度）

官方题解如下：

Code：

 1 /*5ms*/
 2 #include<bits/stdc++.h>
 3 #define IO ios::sync_with_stdio(false);
 4 using namespace std;
 5 const int MAX=1e5+5;
 6 char s[MAX];
 7 int n,sum[MAX],flag[2*MAX],max1;
 8 int main()
 9 {
10     IO;
11     while(!(cin>>n>>s+1).eof())
12     {
13         memset(flag,-1,sizeof(flag));
14         int ans1=0,ans0=0;
15         for(int i=1;i<=n;i++){
16             if(s[i]=='0')ans0++,sum[i]=sum[i-1]-1;
17             else ans1++,sum[i]=sum[i-1]+1;
18             if(flag[MAX+sum[i]]==-1)flag[MAX+sum[i]]=i;
19             else max1=max(i-flag[MAX+sum[i]],max1);
20             if(sum[i]==0)max1=max(max1,i);
21         }
22         cout<<max1<<' '<<2*min(ans1,ans0)<<endl;
23     }
24     return 0;
25 }

或者用STL的map实现，代码如下：

 1 /*52ms*/
 2 #include<bits/stdc++.h>
 3 #define IO ios::sync_with_stdio(false);
 4 using namespace std;
 5 map<int,int>m;
 6 int main()
 7 {
 8     IO;char c;int n;
 9     while(!(cin>>n).eof())
10     {
11         int ret=0,ans1=0,sum=0;
12         m.clear();m[0]=0;
13         for(int i=1;i<=n;++i){
14             cin>>c;
15             if(c=='1')ans1++,sum++;
16             else sum--;
17             if(m.count(sum))ret=max(ret,i-m[sum]);//map.count(Key)返回值为1或者0，1返回存在，0返回不存在
18             else m[sum]=i;
19         }
20         cout<<ret<<' '<<2*min(ans1,n-ans1)<<endl;
21     }
22     return 0;
23 }