网站建设推广的方法,Wordpress双主题,超级外链工具 增加外链中,太原论坛2021C. Good Subarrays一、问题二、分析三、代码一、问题 二、分析
这道题目的意思就是给我们一个数组#xff0c;然后我们从数组中选取一个连续的区间#xff0c;这个区间满足条件#xff1a;区间内的元素和等于区间的长度。
对于区间和问题我们先想到的是前缀和的算法。
那…
C. Good Subarrays一、问题二、分析三、代码一、问题 二、分析
这道题目的意思就是给我们一个数组然后我们从数组中选取一个连续的区间这个区间满足条件区间内的元素和等于区间的长度。
对于区间和问题我们先想到的是前缀和的算法。
那么题目中的要求可以表示为s[r]−s[l−1]r−(l−1)s[r]-s[l-1]r-(l-1)s[r]−s[l−1]r−(l−1)
移向可得 s[r]−rs[l−1]−(l−1)s[r]-rs[l-1]-(l-1) s[r]−rs[l−1]−(l−1)
我们可以构造一个新的数组d[i]s[i]−id[i] s[i] -id[i]s[i]−i
这道题就可以转化为在iii的左侧有多少等于d[i]d[i]d[i]的元素这个个数就是我们以iii为右端点的符合条件的区间数目。
三、代码
#includebits/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_mapll, 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();
}
