当前位置:网站首页>D. Non-zero Segments
D. Non-zero Segments
2022-08-08 16:37:00 【秦小咩】
D. Non-zero Segments
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Kolya got an integer array a1,a2,…,ana1,a2,…,an. The array can contain both positive and negative integers, but Kolya doesn't like 00, so the array doesn't contain any zeros.
Kolya doesn't like that the sum of some subsegments of his array can be 00. The subsegment is some consecutive segment of elements of the array.
You have to help Kolya and change his array in such a way that it doesn't contain any subsegments with the sum 00. To reach this goal, you can insert any integers between any pair of adjacent elements of the array (integers can be really any: positive, negative, 00, any by absolute value, even such a huge that they can't be represented in most standard programming languages).
Your task is to find the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum 00.
Input
The first line of the input contains one integer nn (2≤n≤2000002≤n≤200000) — the number of elements in Kolya's array.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109,ai≠0−109≤ai≤109,ai≠0) — the description of Kolya's array.
Output
Print the minimum number of integers you have to insert into Kolya's array in such a way that the resulting array doesn't contain any subsegments with the sum 00.
Examples
input
Copy
4 1 -5 3 2
output
Copy
1
input
Copy
5 4 -2 3 -9 2
output
Copy
0
input
Copy
9 -1 1 -1 1 -1 1 1 -1 -1
output
Copy
6
input
Copy
8 16 -5 -11 -15 10 5 4 -4
output
Copy
3
Note
Consider the first example. There is only one subsegment with the sum 00. It starts in the second element and ends in the fourth element. It's enough to insert one element so the array doesn't contain any subsegments with the sum equal to zero. For example, it is possible to insert the integer 11 between second and third elements of the array.
There are no subsegments having sum 00 in the second example so you don't need to do anything.
连续子段和为0无非两种情况,一种是1个或多个小区间不交叉,各自和为0,此时答案就是这些区间的个数。第二种就是交叉,包含的和为0的区间,此时我们可以发现,我们只需要从前往后扫,发现一个和为0的,就把答案加1,再从该位置重新计数。这样即使有包含情况存在,我们把被包含的改成巨大的数字,那么大区间也就不用修改了,即使有交叉的,我们把交叉的那部分修改成巨大数,再从新起点开始,那么这个交叉的也被瓦解了。这里体现的是一种贪心的思想,及能修改就修改,先修改一定最优。
判断区间和是0的快速方法是,哈希表存前缀,重复出现说明出现了当前第一个和是0的区间
#include<iostream>
# include<algorithm>
# include<unordered_map>
using namespace std;
typedef long long int ll;
unordered_map<ll,bool>mp;
int main ()
{
ll n,ans=0,x,nowsum=0;
cin>>n;
mp[0]=1;
for(int i=1;i<=n;i++)
{
cin>>x;
nowsum+=x;
if(mp.find(nowsum)==mp.end())
{
mp[nowsum]=1;
}
else
{
ans++;
mp.clear();
nowsum=x;
mp[x]=1;
mp[0]=1;
}
}
cout<<ans;
return 0;
}
边栏推荐
猜你喜欢
随机推荐
基于FTP协议的Excel文件上传与下载
VISTA无人驾驶模拟器;FinRL量化金融深度强化学习库;『深度神经网络应用』电子书;CUDA/TensorRT案例集锦;前沿论文 | ShowMeAI资讯日报
二、junit接口自动化框架之二次开发
元宇宙医疗或将改变医疗格局
字节一面:TCP 和 UDP 可以使用同一个端口吗?
非常菜的一个批量布置waf脚本
Building and Visualizing Sudoku Games with Pygame
Grid 布局介绍
最新30系显卡搭建paddle飞浆环境|含CUDA下载安装
垃圾账号不胜其烦,设备指纹快速发现
OpenAI怎么写作「谷歌小发猫写作」
Es的索引操作(代码中的基本操作)
Is it safe to open an account with CICC Wealth?How does it work?
redis设计与实现 笔记(一)
MySQL数据库的简介及select语句的执行流程
[uniapp applet] view container cover-view
3dsmax2021软件安装教程
QCon 回顾 | Data Fabric:逻辑统一、物理分散
【MySQL哪些字段适合建索引,哪些查询条件会导致索引失效】
谈谈怎么可以得到显著性图 特征图 featuremap