CF1398C. Good Subarrays(思维 前缀和)

简介: 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;
}
目录
打赏
0
0
0
0
108
分享
相关文章
编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)
编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)
538 1
|
8月前
【题解】NowCoder BC149 简写单词
【题解】NowCoder BC149 简写单词
73 15
|
7月前
|
CF 1561 D. Up the Strip(数学+思维)
【7月更文挑战第5天】
59 10
|
8月前
CF 1538 G. Gift Set (贪心+思维)
【6月更文挑战第14天】
52 0
|
8月前
|
C++
【洛谷 B2025】输出字符菱形 题解(raw string literal)
使用`*`构建一个斜置的、对角线长度为5的菱形。无输入要求。输出示例:`*`、`***`、`*****`、`***`、` *`。代码实现使用C++,直接打印预定义字符串完成。
97 0
CF1547B Alphabetical Strings(了解字符串的的一些规律)
CF1547B Alphabetical Strings(了解字符串的的一些规律)
90 0
codeforces292——D. Connected Components(并查集+前缀和优化)
codeforces292——D. Connected Components(并查集+前缀和优化)
112 0
codeforces292——D. Connected Components(并查集+前缀和优化)
PAT (Basic Level) Practice (中文) B1008 数组元素循环右移问题 (20 分)
PAT (Basic Level) Practice (中文) B1008 数组元素循环右移问题 (20 分)
110 0
PAT (Basic Level) Practice (中文) B1008 数组元素循环右移问题 (20 分)
PAT (Basic Level) Practice (中文)1012 数字分类 (20 分)+易错测试点
PAT (Basic Level) Practice (中文)1012 数字分类 (20 分)+易错测试点
149 0
PAT (Basic Level) Practice (中文)1012 数字分类 (20 分)+易错测试点