C. Good Subarrays（前缀和）

一、问题

二、分析

这道题目的意思就是给我们一个数组，然后我们从数组中选取一个连续的区间，这个区间满足条件：区间内的元素和等于区间的长度。

对于区间和问题我们先想到的是前缀和的算法。

那么题目中的要求可以表示为：$s[r]-s[l-1]=r-(l-1)$

移向可得：
$$s[r]-r=s[l-1]-(l-1)$$

我们可以构造一个新的数组，$d[i]=s[i]-i$

这道题就可以转化为：在$i$的左侧有多少等于$d[i]$的元素，这个个数就是我们以$i$为右端点的符合条件的区间数目。

三、代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N], s[N], d[N];
ll ans;
void solve()
{ans = 0;int n;cin >> n;string str;cin >> str;for(int i = 1; i <= n; i ++ ){a[i] = str[i - 1] - '0';s[i] = a[i] + s[i - 1];d[i] = s[i] - i;}unordered_map<ll, ll> cnt;for(int i = 0; i <= n; i ++ ){ans += cnt[d[i]];cnt[d[i]] ++;}cout << ans << endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t --)solve();
}