当前位置:网站首页>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;
}
边栏推荐
猜你喜欢
随机推荐
Nervegrowold: machine advanced learning advice
Kubernetes资源编排系列之四: CRD+Operator篇
毕设-基于SSM学生考试系统
C#/VB.NET 将PDF转为PDF/X-1a:2001
jupyter notebook 隐藏&显示全部输出内容
Patience sorting - specializing in quickly solving the longest increasing subarray
NSSCTF部分复现
Charles MOCK 数据 htpps代理
【入门PCB】立创eda的学习
3 个开源项目,让你感受程序员的浪漫!
使用 Pygame 构建和可视化数独游戏
【uniapp小程序】视图容器cover-view
[uniapp applet] view container cover-view
EMQ畅谈IoT数据基础软件开源版图,引领本土开源走向全球
【论文阅读】RAL 2022: Receding Moving Object Segmentation in 3D LiDAR Data Using Sparse 4D Convolutions
9.cuBLAS开发指南中文版--cuBLAS中的原子模式的配置
基于华为云ModelArts的水表读数识别开发实践【华为云至简致远】
The situation of the solution of the equation system and the correlation transformation of the vector group
ERROR Failed to compile with 1 error
laravel database: query builder