开发者社区大数据文章正文

CF1398C. Good Subarrays（思维前缀和）

2022-12-01 129 发布于山东

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： CF1398C. Good Subarrays（思维前缀和）

linkkkk

题意：

求满足∑ i = l r a i = r − l + 1的子区间个数。

思路：

开始写了个降智代码；

实际上令b i = a i − 1，那么式子就变成了∑ i = l r b i = 0

经典题

记录一下这个小思维

代码：

// Problem: C. Good Subarrays
// Contest: Codeforces - Educational Codeforces Round 93 (Rated for Div. 2)
// URL: https://codeforces.com/problemset/problem/1398/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
int n,a[maxn];
map<ll,ll>mp;
int main(){
  int _;cin>>_;
  while(_--){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%1d",&a[i]),a[i]--;
    ll ans=0,sum=0;
    mp.clear();
    mp[0]=1;
    for(int i=1;i<=n;i++){
      sum+=a[i];
      ans=ans+mp[sum];
      mp[sum]++;
    }
    cout<<ans<<endl;
  }
  return 0;
}