[51nod 1393] 0和1相等串 前缀和

#include<cstdio>
#include<cstring>
#define maxn 1000050
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int l[maxn<<1];// 即maxn*2
int a[maxn];
char s[maxn];
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    for (int i=1;i<=n;i++)
    a[i]=a[i-1]+(s[i]=='1'?1:-1);
    for (int i=0;i<=n+n;i++)
    l[i]=-1; //初始化为-1
    l[0+n]=0;//a[0]=0  +n是因为所有数都+n以保证为非负数
    int ans=0;
    for (int i=1;i<=n;i++){
        if (l[a[i]+n]<0) l[a[i]+n]=i;//
        ans=max(ans,i-l[a[i]+n]);
    }
    printf("%d\n",ans);
}
/*
记1是+1 0是-1
然后做一次前缀和
a[i]=a[i-1]+(s[i]=='1'?1:-1)
可以发现对于一个区间[l,r]
如果满足0的个数等于1的个数
那么这段区间的和一定是0
即满足a[r]-a[l-1]=0
也就是a[r]=a[l-1]
考虑枚举 r
那么我们希望找到一个最小的l
使得a[l-1]=a[r] ->此时贡献为r-l+1

我们可以利用一个数组l[x]来记录
a[i]=x的最小i
那么枚举r时
ans=max(ans,r-l[a[r]])

考虑到a[i]可能为负数，可以考虑加上n来保证a[i]是正的
这样就可以作为数组下标了

*/