瘋狂的二進制字元串（牛客多校第三場）

瘋狂的二進制字元串

本題大意：給定一個01組成的字元串，求兩個滿足0和1數量相同的最長長度，一個是最長連續子序列，一個是可以任意删除任何字元的子序列。

第二種很簡單，就是0和1的數量中比較小的那一個乘二就完事了，主要是求第一個，第一個我是用的字首和求的，首先sum0和sum1分别表示到目前為止0和1的數量，然後設立一個數組c，表示某0和1的數量差所在的下标，比如到i=2的時候sum0=1，sum1=1，p=0,c[0]=-1,那就把c[0]設為2，等到下一個p=0的時候可以直接減去目前的c[0],然後求最大就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
using namespace std;
int n,sum0[100005],sum1[100005],c[200005];
char s[100005];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    memset(c,-1,sizeof(c));
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='0')sum0[i]++;
        else sum1[i]++;
        sum0[i]+=sum0[i-1],sum1[i]+=sum1[i-1];
    }
    c[0]=0;
    int maxn=0;
    for(int i=1;i<=n;i++)
    {
        int p=sum0[i]-sum1[i];
        if(p<0)p=(-p)+100000;//設立p為0和1的差，為保證p為正，當p為負的時候加上100000
        if(c[p]==-1)c[p]=i;
        else maxn=max(maxn,i-c[p]);//兩次p相同的坐标差取最大
    }
    cout<<maxn<<" "<<2*min(sum0[n],sum1[n])<<endl;
    return 0;
}