专栏文章

P14253 旅行（trip）题解

wwmrqwqal & su
P14253题解参与者 45已保存评论 47

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
47 条
当前快照
1 份
快照标识符
@minl229t
此快照首次捕获于
2025/12/02 04:09
3 个月前
此快照最后确认于
2025/12/02 04:09
3 个月前
查看原文

题目链接

P14253 旅行（trip）

解题思路

首先我们注意到一个显然的性质：当选择的区间左端点 ll 固定时，选择越大的 rr 一定不劣，因此我们只需要统计选取 l∈[1,n]l \in [1,n]，r=nr = n 时的所有区间的答案。
套路地，考虑从后往前做。利用差分思想，我们注意到一个前缀 al∼ia_{l \sim i} 的和为 00 等价于 al∼na_{l \sim n} 的和减去 ai+1∼na_{i+1 \sim n} 的差是否为 00，那么 al∼na_{l \sim n}，ai+1∼na_{i+1 \sim n} 的值都容易计算，因此我们可以直接使用 map 来维护从而计算出答案。
时间复杂度 O(nlog⁡n)O(n \log n)。

参考代码

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

评论

共 47 条评论，欢迎与作者交流。

正在加载评论...