1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol AI分析

思路

一个连续子序列(片段)可以由其起始位置 iii 和结束位置 jjj 定义(其中 1≤i≤j≤n1 \le i \le j \le n1≤i≤j≤n)。 根据题意,一个从索引 iii 到 jjj 的片段是“平衡片段”的条件是: ∑k=ijAk=j−i+1\sum_{k=i}^{j} A_k = j - i + 1∑k=ij​Ak​=j−i+1 这里的 ∑k=ijAk\sum_{k=i}^{j} A_k∑k=ij​Ak​ 是片段中所有水晶的能量和,而 j−i+1j - i + 1j−i+1 是该片段的长度。

直接暴力枚举所有的起始位置 iii 和结束位置 jjj,然后计算和并判断,时间复杂度会达到 O(n2)O(n^2)O(n2),对于 n=2×105n=2 \times 10^5n=2×105 的数据规模来说太慢了,会超时。我们需要一个更高效的算法。

P3681.第3题-多多的能量水晶

    1000ms Tried: 122 Accepted: 37 Difficulty: 5 所属公司 : 拼多多
    算法与标签>前缀和

题目内容

多多最近来到了一片神秘的山谷,山谷中散落着一些能量水晶。每一颗水晶拥有一个整数能量值,可能为正,也可能为负。

水晶被排成一条直线,多多决定在其中选择一个连续的水晶序列进行采集。为了保证能量的平衡,他只愿意采集“平衡片段"——即片段中所有水晶的能量值加起来,恰好等于这个片段中水晶的数量。

请你帮多多计算一下,在这条水晶链中,总共有多少个这样的“平衡片段”。

输入描述

第一行包括一个整数 n(1≤n≤2×105)n(1 ≤n≤2×10^5)n(1≤n≤2×105) ,代表山谷中能量水晶的数量。

第二行包括 nnn 个整数 A1,A2,…,An(−109≤Ai≤109)A_1, A_2,…, A_n(-10^9≤A_i≤10^9)A1​,A2​,…,An​(−109≤Ai​≤109) ,代表第 iii 个水晶的能量值。

输出描述

输出一个整数,表示一共有多少个“平衡片段” 。

样例1

输入

3
2 0 1

输出

3

说明

样例中,满足条件的子段共有 333 个:

[1][1][1] :能量和为 111 ,长度为 111

[2,0][2,0][2,0] :能量和为 222 ,长度为 222

[1,2,0][1,2,0][1,2,0] :能量和为 333 ,长度为 333

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 1, 114ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?