题意

你会得到一个由0到9的数组$a_1,a_2,…,a_n$。

子数组$a_l,a_{l+1},a_{l+2},…,a_{r−1},a_r$。如果子数组的元素之和等于该子数组的长度，$\sum_{i=1}^{n}a_i=r-l+1$

例如，如果a=[1,2,0]，然后3良好的子阵列：a1…1=[1],a2…3=[2,0]和a1…3=[1,2,0].

计算数组的好子数组的数目。

题解

• 首先子数组元素之和等于元素个数，这就意味着我们令每一个子数组元素减去1，就可以等价为子数组元素和为0的数组即为好子数组。
• 那么我们维护一个前缀和，如果当前前缀和为0，那么答案加一，同时我们记录在它之前前缀和同样为0的个数，那么这个前缀和减去前面这些前缀和为0的区间依然是前缀和为0的区间，则这些子数组也符合题意，则答案再加前面已有前缀和为0的子数组的个数。
• 若当前前缀和不为0，为x，则同样记录在这之前前缀和同样为x的个数，那么这个前缀和减去前面那些前缀和为x的区间，剩下的区间是为0的区间。

const int N=1e5+10;
int a[N];
int n;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;

        string s;
        cin>>s;

        for(int i=0;i<n;i++) a[i]=s[i]-'0'-1;

        unordered_map<int,int> mp;

        int sum=0;
        LL ans=0;
        mp[0]=1;//sum[0]=0
        for(int i=0;i<n;i++)
        {
            sum+=a[i];
            if(mp[sum]) ans+=mp[sum];
            mp[sum]++;
        }

        cout<<ans<<endl;
    }
    //system("pause");
}

设 $S_i$ 为前缀和。
那么如果一对 $l,r$ 满足 $S_r-S_{l-1}=r-l+1$ ，那么它们对答案的贡献为 $1$ 。
移项得 $S_r-r=S_{l-1}-l+1$ 。
那么我们可以考虑遍历数组，先将 $i$ 作为 $l$ 时 $b_{S_{i-1}-i+1}$ 加一。然后答案加上当前 $i$ 作为 $r$ 时符合条件的 $l$ 的个数，即 $b_{S_{i}-i}$ 。

const int N=1e5+10;
int a[N];
char s[N];
int sum[N];
int n;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;

        cin>>s+1;

        for(int i=1;i<=n;i++) a[i]=s[i]-'0',sum[i]=sum[i-1]+a[i];

        unordered_map<int,int> mp;
        LL ans=0;

        for(int i=1;i<=n;i++)
        {
            int s=sum[i-1]-i+1;
            mp[s]++;
            ans+=mp[sum[i]-i];
        }

        cout<<ans<<endl;
    }
    //system("pause");
}