题解：P14253 旅行（trip）

zeyzle · 2025-10-22 17:54:20 · 题解

题目传送门

旅行(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) 。

参考代码

#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;
}