CF904.Div2


CF904.Div2


A

暴力。

签到,发现 $k$ 很小只有 $10$ ,所以直接暴力往后加直到是 $k$ 的倍数即可。


B

双指针。

记录最后一个 $1$ 的位置和这个位置之前的第一个 $0$ 的位置,那么每次对答案的贡献就是这两个位置之差,用双指针来维护这两个位置即可。

时间复杂度 $O(n)$ 。


C

差分+贪心。

容易想到,只需要关注 $1$ 和 $m$ 这两个特殊位置即可。

两个集合,一个是左端点大于 $1$ 的区间,另一个是右端点小于 $m$ 的区间,对两个集合内的区间进行操作(用差分)取最大值即可。

需要离散化,时间复杂度 $O(n\log n)$ 。


文章作者: HoshiuZ
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 HoshiuZ !
  目录