[题解]Crazy Binary String-前缀和（2019牛客多校第三场B题）

题目链接：https://ac.nowcoder.com/acm/contest/883/B

题意：

给你一段长度为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

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int pos[],cnt[];

 int main()

 {

     int n,m,t,x=,y=,ans1=,ans2;

     cin>>n;

     string a;

     cin>>a;

     cnt[]=;//设初始价值为100000，否则可能出现负数，数组越界

     for(int i=;i<=n;i++){

         if(a[i-]=='')

             cnt[i]=cnt[i-]-,x++;

         else

             cnt[i]=cnt[i-]+,y++;

         if(pos[cnt[i]]==&&cnt[i]!=)//更新pos

             pos[cnt[i]]=i;

         else

             ans1=max(ans1,i-pos[cnt[i]]);//如果pos[cnt[i]]不为0，则可得到一段符合要求的字串

     }

     ans2=min(x,y)*;

     cout<<ans1<<" "<<ans2<<endl;

     return ;

 }

巴特西

[题解]Crazy Binary String-前缀和（2019牛客多校第三场B题）

最新文章

热门文章