https://codeforces.ml/contest/1333/problem/C
大概題意是規定和為0的陣列為不合格陣列，詢問給定陣列中共有多少個合格子陣列，
解題
子陣列的數量
一個長度為 \(n\) 的陣列 \(a[0,n-1]\)，選取 \(i\) 作為子陣列的終點，那么我們可以選取 \([0,i]\) 中的任何一個 \(j\) 作為起點，這樣可以得到子陣列 \(a[j,i]\) ，所以以 \(i\) 為終點的子陣列有 \(i+1\) 種，以此類推，最終子陣列的總個數為 \(count=\sum_{i=0}^{n-1}(i+1)= (n+1)*n/2\) ，
合格子陣列的數量
根據題意可得，如果一個陣列是不合格的（存在子陣列和為0），則含有這個陣列的所有父親陣列都是不合格的，
當我們以 \(i\) 為子陣列終點時，
如果子陣列 \(a[p_1,p_2](p_2\le i)\) 是不合格陣列，那么我們只能在 \((p_1,i]\) 區間內選取起點 \(j\) （共 \(i-p_1\) 種），否者新陣列會成為不合格部分的父親陣列，
如果 \(p_2 \gt i\) 的話，則可以在 \([0,i]\) 區間內選取起點 \(j\)，共計 \(i+1\) 種，
我們設 \(s\) 為所有出現在位置 \(i\) 之前的不合格子陣列的起點位置的集合，設 \(f(i)\) 為以 \(a_i\) 為結尾的合格子陣列個數，\(f(i) = i-max\{p|p<i,p\in s\}\)，如果 \(p\) 不存在，那么 \(f(i) = i+1\)，
全部合格子陣列的數量 \(ans = \sum_{all}f(i)\)，不會重復計算，
代碼
#include<bits/stdc++.h>
#define ll long long
#define fr(i,n) for(int i=0;i<n;i++)
#define frs(i,n,flag) for(int i=0;i<n&&flag;i++)
#define frr(i,j,n) for(int i=j;i<n;i++)
#define r_frr(i,j,n) for(int i=n-1;i>=j;i--)
#define frrs(i,j,n,flag) for(int i=j;i<n&&flag;i++)
#define r_frrs(i,j,n,flag) for(int i=n-1;i>=j&&flag;i--)
#define arend(i,n) ((i!=n-1)?" ":"\n")
#define memset0(dp) memset(dp,0,sizeof(dp))
#define print_arr(begin,end) for(auto it = begin;it!=end;it++) cout<<*it<<arend(it,end);
#define log_this(name,value) cout<<name<<": "<<value<<endl;
#define e4 10004#define e5 100005#define e6 1000006#define e7 10000007#define e9 1000000000#define INF 9999999
using namespace std;
int to_int(string s) {stringstream ss;ss<<s;int a;ss>>a;return a;}
string to_str(double a) {stringstream ss;ss<<a;return ss.str();}
int main(){
cin.tie(0);
//ios::sync_with_stdio(false);
//cout<<setiosflags(ios::fixed)<<setprecision(0);
//freopen("1.out","w",stdout);
int n;
while(cin>>n){
ll sum=0,p=-1,ans=0,inp;
map<ll,ll>loc;loc[0] = 0;
fr(i,n){
cin>>inp;
sum += inp;
auto it = loc.find(sum);
if(it!=loc.end()){
p = max(p,loc[sum]);
}
loc[sum] = i+1;
ans += i - p;
}
cout<<ans<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/63650.html
標籤：其他
下一篇：資料結構-排序法