摘要
Title: 3347. 菊花链
Tag: 队列、哈希表
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

3347. 菊花链

• 题意

  每天，作为她绕农场行走的一部分，奶牛 Bessie 会经过她最喜爱的草地，其中种有 N 朵花（五颜六色的雏菊），编号为 1…N，排列成一行。
  花 i 有 pi 朵花瓣。
  作为一名崭露头角的摄影家，Bessie 决定给这些花拍些照片。
  具体地说，对于每一对满足 1≤i≤j≤N 的花 (i,j)，Bessie 会给从花 i 到花 j 之间的所有花（包括 i 和 j）拍一张照。
  后来 Bessie 查看这些照片时注意到有些照片里存在「平均」的花——一朵恰好有 P 朵花瓣的花，其中 P 等于照片中所有花的花瓣数量的平均值。
  Bessie 的照片中有几张存在平均的花？

• 思路

  枚举区间长度，一直维护一个区间长度的队列，用哈希表判断元素是否存在即可

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-02-18 09:41:02
  FilePath: \ACM\Acwing\3347.py
  LastEditTime: 2022-02-18 09:54:02
  '''
  from collections import Counter, deque
  
  if __name__ == "__main__":
      n = int(input())
      a = list(map(int, input().split()))
      res = 0
      for i in range(1, n + 1):  #枚举区间长度
          q = deque()
          d = Counter()
          cnt = 0
          for j in range(n):  #枚举区间内的数
              if len(q) < i:
                  q.appendleft(a[j])
                  d[a[j]] += 1
                  cnt += a[j]
              if len(q) == i:
                  if cnt % i == 0 and d[cnt // i]:
                      res += 1
                  t = q.pop()
                  d[t] -= 1
                  cnt -= t
      print(res)