2019多校训练营B-Crazy Binary String

题目描述

ZYB喜欢二进制字符串（只包含'0'和'1'的字符串）。他喜欢equal binary string（其中字符串中的“0”数和“1”数相等）
ZYB想要从原始字符串中选择一个尽可能长的子字符串T（equal binary string），他还想选择一个相同要求的子序列T
为简单起见，您只需输出最大可能的长度。请注意，空字符串既是子字符串又是任何字符串的子序列。

输入描述：
输入的第一行包含一个整数 N（1≤N≤100000），是T字符串的长度。第二行为T（二进制字符串）

输出描述：
打印两个整数 A和B，分别表示子串和子序列的长度。

示例1
输入

8
01001001

输出

4 6

分析

一开始用常规方法写的T了，所以就用了前缀和。
子串
: 字符串中取一段区间，区间中连续的一段字符即为子串。
子序列
: 字符串中取不连续的一些字符
子序列长度很好求，只要计算“0”和“1”的个数，选其中较小个数*2即可。
这道题求子串要连续一段区间，且原字符串中只有两个元素，可以把“1”设为1，“0”设为-1。
1.若a[i]时“0”和“1”个数相等时，前缀和为0，将i记录下来，为区间长度。
2.若a[i],a[j]的前缀和相等，则区间（a[i]，a[j]）之间的“0”“1”数量也相等，用两个位置相减得出的结果为子串的区间长度。
上述两种方法都可以求子串长度，比出子串的最大长度即为最终结果。

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
char s[100005];
int a[100005], b[2];
int main() {
  fio
  int n;
  cin >> n;
  a[0] = 0;
  //a[]用来前缀和，b[]记录0和1的个数 
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    if (s[i] == '0') {
      a[i] = 1;
      b[0]++;
    } else {
      a[i] = -1;
      b[1]++;
    }
    a[i] += a[i-1];
  }
  int pos = 0;
  map mp;
  //算两个相同a[i]之间的距离，或者a[i]直接为0的长度，比较max值
  //01001001
  //算两个相同a[i]之间的距离，或者a[i]直接为0的长度，比较max值
  /*
  a[1]=-1:mp[-1]=0:mp[-1]=1;
  a[2]=0: i = 2;pos=i=2; mp[0]=0: mp[0]=2;
  a[3]=-1:pos=max(2,3-1)=2 
  a[4]=-2:mp[-2]=0:mp[-2]=4;
  a[5]=-1:pos=max(2,5-1)=4;
  */
  for (int i = 1; i <= n; i++) {
    if (a[i] == 0) pos = i;
    if (mp[a[i]] == 0) mp[a[i]] = i;
    else {
      if (pos <= i-mp[a[i]]) {
        pos = i-mp[a[i]];
      }
    }
  }
  int sum;
  cout << pos << " ";
  sum = b[0] >= b[1]?b[1]*2:b[0]*2;
  cout << sum;
}