7月CF杂题

怎么七月了？六月的只写了一道题捏。

Educational Codeforces Round 151 (Rated for Div. 2)

俺寻思能行。

D. Rating System

为什么大家都切那么快捏。

显然 \(k\) 一定是 \(a\) 数组的一个前缀和。假设 \(k=\sum\limits_{i=1}^x a_i\)，剩下的等价于处理初值为 0 且 \(k=0\) 的子问题。我们需要在 \(O(1)\) 的时间内解决。

先考虑能不能 \(O(n)\)。你枚举它最后一个会把它提到 0 的位置，后面的就是后缀和，所以后面那坨的答案就是 \(\max\limits_{j=x}^n\left\{\sum\limits_{k=j+1}^n a_k \right\}\)。维护后缀和最大值就是 \(O(1)\) 了。

它为什么是对的？首先 rating 在任意时刻都不会小于 0，所以当当前 rating 为 0 时它就是对的；当 rating 大于 0 时，答案会被算小，但这证明我们可以往前找到第一个 rating 等于 0 的位置，且从那到这一段中的变化量为正，在那个点我们就可以得到这个正确答案。