题目描述 Description
1．对于给定的一个长度是N的0，1字符串S = s1s2...sn。
2．S的子串S(l,r) = [sl,sl+1,sl+2,...,sr]。
3．若S(l,r)中'0'的个数是'1'个数的2倍，称S(l,r)这个为good串，否则为bad串。
选择一对整数a, b (1 <= a <= b <= N)。
Num1：开始位置l和结束位置r都在闭区间[a,b]上的子串中good串的个数；
Num2：开始位置l和结束位置r都不在闭区间[a,b]上的子串中good串的个数，但可以包含[a,b]子串，即l，r有如下三种情况l<a且r<a，l>b且r>b，l<a且r>b；
求有多少对a, b使得Num1与Num2相等？
输入描述 Input Description
第一行输入一个整数n。
第二行输入一个由’0’和’1’组成的长度为n的字符串。
输出描述 Output Description
输出一个整数，即使Num1和Num2相等的a,b数对。
样例输入 Sample Input
3
010
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
[a,b]=[1,1]时：
开始位置l和结束位置r都在闭区间[a,b]上的子串如下：
"0"(good子串的个数是0个)。
开始位置l和结束位置r都不在闭区间[a,b]上的子串如下：
"1","0","10"(good子串的个数是0个)。
所以[1,1]满足条件。
[a,b]=[1,2]时：
开始位置l和结束位置r都在闭区间[a,b]上的子串如下：
"0","1","01"(good子串的个数是0个)。
开始位置l和结束位置r都不在闭区间[a,b]上的子串如下：
"0"(good子串的个数是0个)。
所以[1,2]满足条件。
[a,b]=[1,3]时：
开始位置l和结束位置r都在闭区间[a,b]上的子串如下：
"0","1","0","01","10","010"(good子串的个数是1个:"010")。
不存在开始位置l和结束位置r都不在闭区间[a,b]上的子串(good子串的个数是0个)。
所以[1,3]不满足条件。
[a,b]=[2,2]时：
开始位置l和结束位置r都在闭区间[a,b]上的子串如下：
"1"(good子串的个数是0个)。
开始位置l和结束位置r都不在闭区间[a,b]上的子串如下：
"0","0","010"(good子串的个数是1个:"010")。
所以[2,2]不满足条件。
[a,b]=[2,3]时：
开始位置l和结束位置r都在闭区间[a,b]上的子串如下：
"1","0","10"(good子串的个数是0个)。
开始位置l和结束位置r都不在闭区间[a,b]上的子串如下：
"0"(good子串的个数是0个)。
所以[2,3]满足条件。
[a,b]=[3,3]时：
开始位置l和结束位置r都在闭区间[a,b]上的子串如下：
"0"(good子串的个数是0个)。
开始位置l和结束位置r都不在闭区间[a,b]上的子串如下：
"0","1","01"(good子串的个数是0个)。
所以[3,3]满足条件。
所以有4对a,b满足题意。
10%的数据中1<=N<=60;
30%的数据中1<=N<=1000;
40%的数据中1<=N<=5000;
100%的数据中1<=N<=100000;
为什么这道题没有人做？
不要任何高级数据结构，，，居然压轴题
不过蒟蒻还是想了很久，方法很巧妙，看看代码就知道了
几次90分，有一组运行错误，数组超内存了
事实证明O(n^2)可以过（没想通），不会写离散化，用了现学的map，O(nlogn)
//#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> #include <map> using namespace std; ////////////////////////////////////////////////// const int maxn=100000+10; int n; int a[maxn]; int sum_lr[maxn];//sum(1,i) int sum_rl[maxn];//sum(i,n) int num[maxn*3];//num(i+maxn) int good_l[maxn]; int good_r[maxn]; /* 令good[l][r]:[l,r]的good串个数 找出所有(l,r):good[1][n]-good[1][r]-good[l][n]+good[l][r]+good[1][l-1]+good[r+1][n]=good[l][r] good[1][n]+good[1][l-1]+good[r+1][n]=good[1][r]+good[l][n] good_l[n]+good_l[l-1]+good_r[r+1]=good_l[r]+good_r[l] 枚举l，算 good_l[n]+good_l[l-1]-good_r[l]=good_l[r]-good_r[r+1] 的个数（预处理） good[1][i]=1<=l<r<=i:sum_lr[l-1]=sum_lr[r]的个数 */ map<int,int> num_good_r; int k=0; ////////////////////////////////////////////////// ////////////////////////////////////////////////// void input() { scanf("%d\n",&n); for(int i=1;i<=n;i++) a[i]=getchar()=='0'?-1:2; } void solve() { //init int ans=0; //calculate for(int i=1;i<=n;i++) sum_lr[i]=sum_lr[i-1]+a[i]; for(int i=n;i>=1;i--) sum_rl[i]=sum_rl[i+1]+a[i]; memset(num,0,sizeof(num)); num[maxn]=1; for(int i=1;i<=n;i++) { good_l[i]=good_l[i-1]+num[sum_lr[i]+maxn]; num[sum_lr[i]+maxn]++; } memset(num,0,sizeof(num)); num[maxn]=1; for(int i=n;i>=1;i--) { good_r[i]=good_r[i+1]+num[sum_rl[i]+maxn]; num[sum_rl[i]+maxn]++; } //暴力O(n^2) /*for(int l=1;l<=n;l++) for(int r=l;r<=n;r++) if(good_l[n]+good_l[l-1]+good_r[r+1]==good_l[r]+good_r[l]) ans++;*/ for(int i=1;i<=n;i++) { num_good_r[good_l[i]-good_r[i+1]]++; } for(int i=1;i<=n;i++) ans+=num_good_r[good_l[n]+good_l[i-1]-good_r[i]]; /*for(int i=1;i<=n;i++) printf("%d ",a[i]);puts(""); for(int i=1;i<=n;i++) printf("%d ",sum_lr[i]);puts(""); for(int i=1;i<=n;i++) printf("%d ",sum_rl[i]);puts(""); for(int i=1;i<=n;i++) printf("good_l[%d]=%d good_r[%d]=%d\n",i,good_l[i],i,good_r[i]);*/ //output printf("%d\n",ans); } ////////////////////////////////////////////////// int main() { #ifndef _TEST freopen("2013.in","r",stdin); freopen("2013.out","w",stdout); #endif input(); solve(); #ifdef _TEST for(;;); #endif return 0; }