[USACODec2020B]DaisyChains

Every day, as part of her walk around the farm, Bessie the cow visits her favorite pasture, which has N flowers (all colorful daisies) labeled 1…N lined up in a row (1≤N≤100). Flower i has pi petals (1≤p_i≤1000).
As a budding photographer, Bessie decides to take several photos of these flowers. In particular, for every pair of flowers (i,j) satisfying 1≤i≤j≤N, Bessie takes a photo of all flowers from flower i to flower j (including i and j).

Bessie later looks at these photos and notices that some of these photos have an "average flower" -- a flower that has P petals, where P is the exact average number of petals among all flowers in the photo.

How many of Bessie's photos have an average flower?

#include <bits/stdc++.h> using namespace std; const int maxn = 110,maxp = 1e3 + 10; int n,sum,ans; int a[maxn],num[maxp]; void solve(){ for(int i = 1;i <= n;i++){ sum = 0; memset(num,0,sizeof(num)); for(int j = i;j <= n;j++){ sum += a[j]; num[a[j]]++; if(sum % (j - i + 1) == 0 && num[sum / (j - i + 1)]) ans++; } } } int main(){ scanf("%d",&n); for(int i = 1;i <= n;i++) scanf("%d",&a[i]); solve(); printf("%d",ans); return 0; }

详情