C. Zero-Sum Prefixes(前缀和)

Problem - C - Codeforces

 

一个数组v1,v2,...,vn的得分被定义为索引i的数量（1≤i≤n），使v1+v2+...+vi=0。

给你一个长度为n的数组a1,a2,...,an，你可以多次执行以下操作。

选择一个索引i（1≤i≤n），使ai=0。
然后用一个任意的整数替换ai。
通过执行一系列这样的操作，可以得到的a的最大可能分数是多少？

输入
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤104）--测试案例的数量。

每个测试用例的第一行包含一个整数n（1≤n≤2⋅105）--数组a的长度。

每个测试用例的第二行包含n个整数a1,a2,...,an (-109≤ai≤109) - 数组a。

保证所有测试用例的n之和不超过2⋅105。

输出
对于每个测试用例，在执行一系列操作后，打印出数组a的最大可能得分。

例子
InputCopy
5
5
2 0 1 -1 0
3
1000000000 1000000000 0
4
0 0 0 0
8
3 0 2 -10 10 -30 30 0
9
1 0 0 1 -1 0 1 0 -1
输出拷贝
3
1
4
4
5
注意
在第一个测试案例中，在一次操作中把a2的值改为-2是最好的。

结果数组a将是[2,-2,1,-1,0]，得分是3。

a1+a2=2-2=0。
a1+a2+a3+a4=2−2+1−1=0;
a1+a2+a3+a4+a5=2−2+1−1+0=0.
在第二个测试案例中，将a3的值改为-2000000000是最理想的，给我们一个分数为1的阵列。

在第三个测试案例中，没有必要进行任何操作。

题解:

无论如何答案最大为n,

首先我们得到该数组的前缀和,

这题，首先特别考虑第一个0之前的，前缀和为0符合题意。

然后，第一个0之后，每两个0的区间，取前缀和相同的数量最大的作为答案。

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
long long b[200050];
long long c[200050];
void solve()
{
	int n;
	cin >> n;
	int len = 0;
	for(int i = 1;i <= n;i++)
	{
		cin >> b[i];
		if(b[i] == 0)
		{
			c[len++] = i;
		}
		b[i] = b[i-1] + b[i];
	}
	c[len] = n+1;
	int ans = 0;
	for(int i = 1;i < c[0];i++)
	{
		if(b[i] == 0)
		{
			ans++;
		}
	}
	for(int i = 0;i < len;i++)
	{
		map<long long,int> f;
		int ma = 0;
		for(int j = c[i];j < c[i+1];j++)
		{
			f[b[j]]++;
			ma = max(ma,f[b[j]]);
		}
		ans += ma;
	}
	cout<<ans<<"\n";
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
}