专栏文章

题解:AT_arc137_b [ARC137B] Count 1's

AT_arc137_b题解参与者 2已保存评论 1

文章操作

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

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

思路:

容易发现,得分的可能数就是能得到分数的最大值和最小值之间的数的总数。为什么呢?因为这个数列只由 0011 组成,最大值和最小值之间的每个数总是能得到的。
所以,我们只需要求这段数列的最大值和最小值就可以了。
我们用一个 bb 数组记录当前改变对分数产生的影响,再对于每个 aia_i 做以下操作:
  • aia_i11 时,我们把 bib_i 设为 1-1,因为把 11 变为 00 减去了 11
  • aia_i00 时,我们把 bib_i 设为 11,因为把 00 变为 11 加上了 11
此时,我们再给 bb 数组做一个前缀和,这时的 bb 数组即为从开头到当前数的所有改变所受到的影响。
枚举以当前数为结尾所产生的最大值与最小值即可。
就不给代码了。

评论

1 条评论,欢迎与作者交流。

正在加载评论...