题目传送门

旅行(trip)

解题思路

首先先求出 A 的前缀和序列 C 即

c_{1 \sim n}

。
若对于 l 和 r (

l,r\in[1,n]

且 x < y ) ，显然的，当

c_{r}

c_{l-1}

= 0 即

c_{r}

c_{l-1}

时，便会对左端点为 l ，右端点大于或等于 r 的区间做出一次贡献，楼上也已经说了当选择的区间左端点 l 固定时，选择越大的 r 一定不劣，所以我们便可以将前缀和数组排序，统计其中值相等的前缀和的个数，这些值相等的前缀和中天数最早的一个的后一天作为左端点，它所能产生的最多的0的数量一定为这些值相等的前缀和的个数减一，即去除它本身，但如果它本身为零，就不用去除，所以得特判。最后求最大值输出。
时间复杂度

O(nlogn+2n)

。

参考代码

CPP

#include<bits/stdc++.h>//万能头
using namespace std;
#define ll long long int
int main(){
	ll T;
	cin>>T;
	while(T--){
		ll n;
        cin>>n;
		ll a[1000005],sum[1000005],ans=0;
		sum[0]=0;
		for(ll i=1;i<=n;i++){
			cin>>a[i];
			sum[i]=sum[i-1]+a[i];
		}//求前缀和数组
		sort(sum+1,sum+n+1);//sort排序
		ll nt=1;
		for(ll i=1;i<=n;i++){
			if(sum[i]==sum[i-1])nt++;
			else {
				if(sum[i-1]==0)nt++;
				ans=max(ans,nt-1);
				nt=1;
			}
		}
		if(nt^1){
			if(sum[n]==0)nt++;
			ans=max(ans,nt-1);
		}//计数找最大值
		cout<<ans<<endl;
	}
	return 0;
}

题解：P14253 旅行（trip）

文章操作