SP2150 题解 | MingDynasty

SP2150 CIRU - The area of the union of circles

题目链接

橙到黄难度。

C++ 解决方案

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e7+1;
int a[MAXN];
int main(){
  int T;
  cin>>T;
  while(T--){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    map<long long,int>m;
    m[0]=1;
    long long p=0,a=0;
    for(int i=0;i<n;i++){
      p+=a[i];
      if(m.find(p-47)!=m.end()) a+=m[p-47];
      m[p]++;
    }
    cout<<a<<'\n';
  }
  return 0;
}

题目思路解析

建议食用 STL。

求子段和，用前缀和记录，再用 STL 的 map 开一个桶记录数量，查询子段和为 47 时用函数很方便。

附：免费快读模板！