题目大意：给你一个字符串序列，你需要找到有多少个区间使得其区间内每个元素的和为区间长度。
原题目可以转换成求子区间和为0的区间个数（一开始没看清数据范围，用了个n2的做法TLE了），用mp存一下对于当前位置i之前，前缀和为sub[i]的个数（原因是对于当前位置你可以找到一个前缀sub[j]使得sub[i]-sub[j]==0），那么对于当前位置i的可行解为mp[sub[i]],如果sub[i]==0，还要再额外加1.
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<cstdio> #include<vector> #include<map> #include<set> #include<queue> //#define _for(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long ll; double eps=1e-10; ll mod=1e15+7; const int INF =0x3f3f3f; const int MAXN=2e3+10; const int maxn = 1e5+10; //ll inf=100000000000000; //template<typename T>inline void read(T &x) //{ // x=0; // static int p;p=1; // static char c;c=getchar(); // while(!isdigit(c)){if(c=='-')p=-1;c=getchar();} // while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();} // x*=p; //} typedef unsigned long long ull; int dp[101000]; char a[100010]; int sub[100010]; map<int,int>mp; int main() { int t; scanf("%d",&t); while(t--){ int n; mp.clear(); scanf("%d",&n); scanf("%s",a+1); sub[0]=0; ll ans=0; for(int i=1;i<=n;i++){ sub[i]=sub[i-1]+a[i]-'0'-1; if(sub[i]==0){ ans++; ans+=mp[0]; } else { ans+=mp[sub[i]]; } mp[sub[i]]++; } printf("%lld ",ans); } return 0; }