题目链接：

 

---

 

题意：

给你一段长度为n，且只有 ‘0’ 和 ‘1’ 组成的字符串 a[0,...,n-1]。求子串中 ‘0’ 和 ‘1’ 数目相等的最大长度，子序列中 ‘0’ 和 ‘1’ 数目相等的最大长度。

 

思路：

子序列的最大长度很容易想到，就是 ‘0’ 和 ‘1’ 的数量中最小的两倍

求子串的最大长度就用前缀和

将 ‘1’ 的价值设为1，‘0’ 的价值设为-1，用数组 cnt[i] 记录从 0 到 i 的前缀和，再用数组 pos[i] 记录前缀和为 i 时的位置

可知当 cnt[j] = cnt[i] （j > i）时，子串 a[i+1,....,j] 中的 ‘0’ 和 ‘1’ 数量相等，则更新 ans=max(ans,j-pos[cnt[j]])

当时想了好久，才明白要用前缀和来求子串的最大长度，自己太菜qaq

 

1 #include 
     
       2 using namespace std; 3 typedef long long ll; 4 int pos[200006],cnt[200006]; 5 int main() 6 { 7     int n,m,t,x=0,y=0,ans1=0,ans2; 8     cin>>n; 9     string a;10     cin>>a;11     cnt[0]=100000;//设初始价值为100000，否则可能出现负数，数组越界 12     for(int i=1;i<=n;i++){13         if(a[i-1]=='0')14             cnt[i]=cnt[i-1]-1,x++;15         else16             cnt[i]=cnt[i-1]+1,y++;17         if(pos[cnt[i]]==0&&cnt[i]!=100000)//更新pos 18             pos[cnt[i]]=i;19         else20             ans1=max(ans1,i-pos[cnt[i]]);//如果pos[cnt[i]]不为0，则可得到一段符合要求的字串 21     }22     ans2=min(x,y)*2;23     cout<
      
       <<" "<
       
        <