D. Non-zero Segments(前缀和)

Problem - 1426D - Codeforces

题意:

科利亚得到一个整数数组a1,a2,...,an。这个数组既可以包含正整数也可以包含负整数，但是Kolya不喜欢0，所以这个数组不包含任何零。

Kolya不喜欢他的数组中某些子段的总和为0，子段是数组中一些连续的元素段。

为了达到这个目标，你可以在数组的任何一对相邻元素之间插入任何整数（整数可以是任何：正数、负数、0，任何绝对值，甚至是巨大到无法用大多数标准编程语言表示的整数）。

你的任务是找出你必须插入Kolya数组中的最小整数，以使产生的数组不包含任何和为0的子段。

输入
输入的第一行包含一个整数n（2≤n≤200000）--Kolya数组中的元素数。

输入的第二行包含n个整数a1,a2,...,an（-109≤ai≤109,ai≠0）--Kolya数组的描述。

输出
打印你必须插入Kolya数组中的最小整数，使产生的数组不包含任何总和为0的子段。

例子
InputCopy
4
1 -5 3 2
outputCopy
1
输入复制
5
4 -2 3 -9 2
输出拷贝
0
输入复制
9
-1 1 -1 1 -1 1 1 -1 -1
输出拷贝
6
输入复制
8
16 -5 -11 -15 10 5 4 -4
输出拷贝
3
注意
考虑第一个例子。只有一个总和为0的子段，它开始于第二个元素，结束于第四个元素。插入一个元素就够了，这样数组就不会包含任何总和等于0的子段了。例如，可以在数组的第二和第三元素之间插入整数1。

在第二个例子中没有总和为0的子段，所以你不需要做什么。

题解:

我们每次记录前缀和出现过的情况,让插入一个数,然后插入的数++,map清空,前缀和从当前开始,

关键是为什么插入的数要++,我看很多题解并没有说明这个问题,或是理解错了

大个比方现在我遇到一个数x加上后,前缀出现过,插入了一个1,然后我们把map清空,让前缀=x,但是后面又遇到一个数加上后前缀和等于x,如果我么还插入1,就会出现一个问题,

1 9........ 1 9

前面的插入的两个1,1区间和会为0,

#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
long long a[300050];
void solve()
{
	int n;
	cin >> n;
	map<long long,int> f;
	long long s = 0;
	f[0] = 1;
	int ans = 0;
	for(int i = 1;i <= n;i++)
	{
		int k;
		cin >> k;
		s+= k;
		if(f[s] == 1)
		{
			ans++;
			s = k;
			f.clear();
			f[0] = 1;
		}
		f[s] = 1;
	}
	cout<<ans;
}
int main()
{
	int t = 1;
//	cin >> t;
	while(t--)
	{
		solve();
	}
}
//
//abcdef
//babcdef
//babcdefedcba