Codeforces Round #833 (Div. 2) C. Zero-Sum Prefixes

 题目链接：Problem - C - Codeforces

题目大意：

t(1≤t≤10^4)组测试数据，每组给定数组长度n(1≤n≤2⋅10^5)，和a1,a2,…,an(−10^9≤ai≤10^9)。

可以做如下操作：

选择一个ai=0的值，将其改为任意值。

对于原数组的前缀和数组，定义score为前缀数组中为0的元素个数。

问通过上述操作使得score最大为多少。

样例：

input:

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

output:

3
1
4
4
5

思路：

先求出初始前缀和数组s。

抓住一个重要性质：对于一个可以修改的值，若ai等于0，它的修改只会影响前缀和数组中i及其以后的值。可以修改的点将s数组分为若干段，贪心的将每一段的score最大化即可。

1.假设只有一个ai=0，设前缀和数组s[i~n]中出现次数最多的数为x，把它修改为-x即可保证最大化。

2.如果有2个，ai=0,aj=0(i说明贪心策略并不影响j的决策。对于ai，只需要保证修改成s[i~j)中出现次数最多的数的相反数。

3.对于多个，记录每个ai=0出现的位置，考虑相邻的两个i,j，对于第i个同理，只需要保证最大化s[i~j)即可。前面已经证明贪心策略并不会影响j之后的决策。

 代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define pii pair
#define pll pair
#define pil pair
#define pli pair
#define pdd pair
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (int i=a;i
#define per(i,a,b) for (int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const LL MOD=1004535809;
const int N=2e5+10;
int a[N];
LL s[N];
void solve()
{
	int ans=0;
	int n;
	cin>>n;
	vector<int>v;
	rep(i,1,n+1){
		cin>>a[i],s[i]=s[i-1]+a[i];
		if(a[i]==0) v.push_back(i);
	}
	rep(i,0,v.size()){
		int ne;
		if(isize()-1) ne=v[i+1];
		else ne=n+1;
		int mx=0,val=0;
		mapint>mp;
		rep(j,v[i],ne){
			++mp[s[j]];
			if(mp[s[j]]>mx) mx=mp[s[j]];
		}
		ans+=mx;
	}
	if(v.size()){
		rep(i,1,v[0]) if(s[i]==0) ++ans;
	}else  rep(i,1,n+1) if(s[i]==0) ++ans;
	cout<
}
int main()
{
//	#ifndef ONLINE_JUDGE
//    freopen("title.in","r",stdin);
//    freopen("title.out","w",stdout);
//    #endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
//	rep(i,1,_+1){
//		cout<<"Case "<
//		solve();
//	}
	return 0;
}