【题解】CF1426D Non-zero Segments

题目

CF1426D Non-zero Segments

题解

显然,插入的数为无穷大时作用最大。同时,如果两个和为0的子区间有重叠部分,则只需要在重叠部分插入就可以使两个子区间同时满足条件。将所有和为0的子区间抽取出来单独考虑,题意即可简化为:有一些区间,如何插入最少的特殊元素,使得每个区间中都有至少一个特殊元素。

这就成了一个贪心的经典题,策略为:从左往右扫描每个区间的左端点,对于某一个暂时没有特殊元素的区间,将特殊元素插入到区间的最右端。(证明略)

但是,如果先找出这些区间再做处理,复杂度太高,考虑使用前缀和优化。从左往右扫描数组,用STL set维护左侧出现过的前缀和。对于每一个位置,如果当前位置的前缀和在set中存在,则在它们中间有一段需要处理的区间,进行计数。此时,后面的与其有重复部分的区间(即左端点在当前位置左边的区间)可以不用再考虑,于是直接将set清空。但是要注意,子区间有可能在端点处重合,这种情况不属于有重复部分,所以清空set以后还需要插入当前位置左侧一位置的前缀和。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年10月17日 下午5:47

【小白解析】
此题主要操作在14行,其判断对应:

对于每一个位置,如果当前位置的前缀和在set中存在,则在它们中间有一段需要处理的区间,进行计数。

s.find(sum)返回sum在set中的位置;若查找不到sum,指针位于最后一位,返回s.end()(即set当前大小);若查找到sum,if条件成立,此时set中某个位置a存放了sum,与即将存放在set末尾b位置的sum一直:也就是说,原本数列中1-a位之和等于1-b位之和,说明a+1-b位之和为0,需要进行加无限大操作,对应ans++。
需要注意的是,此时的无限大安插在b-1与b位之间,后续的数组仍可能将b位的数字包含在内形成0:

但是要注意,子区间有可能在端点处重合,这种情况不属于有重复部分,所以清空set以后还需要插入当前位置左侧一位置的前缀和。

故需要再次读入b位前的数字和,以防b参与形成和为0的子序列,对应s.insert(sum-x)。
最后每一步中都进行s.insert(sum)操作,用于后续判断。