题解：AT_arc137_b [ARC137B] Count 1's

Ray_yi · 2025-02-11 15:40:25 · 题解

思路：

容易发现，得分的可能数就是能得到分数的最大值和最小值之间的数的总数。为什么呢？因为这个数列只由 0 和 1 组成，最大值和最小值之间的每个数总是能得到的。

所以，我们只需要求这段数列的最大值和最小值就可以了。

我们用一个 b 数组记录当前改变对分数产生的影响，再对于每个 a_i 做以下操作：

• 当 a_i 为 1 时，我们把 b_i 设为 -1，因为把 1 变为 0 减去了 1。
• 当 a_i 为 0 时，我们把 b_i 设为 1，因为把 0 变为 1 加上了 1。

此时，我们再给 b 数组做一个前缀和，这时的 b 数组即为从开头到当前数的所有改变所受到的影响。

枚举以当前数为结尾所产生的最大值与最小值即可。

就不给代码了。