P14253 旅行（trip）题解

· · 题解

题目链接

P14253 旅行（trip）

解题思路

首先我们注意到一个显然的性质：当选择的区间左端点 l 固定时，选择越大的 r 一定不劣，因此我们只需要统计选取 l \in [1,n]，r = n 时的所有区间的答案。

套路地，考虑从后往前做。利用差分思想，我们注意到一个前缀 a_{l \sim i} 的和为 0 等价于 a_{l \sim n} 的和减去 a_{i+1 \sim n} 的差是否为 0，那么 a_{l \sim n}，a_{i+1 \sim n} 的值都容易计算，因此我们可以直接使用 map 来维护从而计算出答案。

时间复杂度 O(n \log n)。

参考代码

ll n,ans;
ll a[1000010];
void solve()
{
    cin>>n;
    forl(i,1,n)
        cin>>a[i];
    ll S=0;
    map<ll,ll>mp;
    mp[0]=1;
    forr(i,n,1)
        S+=a[i],Max(ans,mp[S]++);
    cout<<ans<<endl;
    ans=0;
}