Codeforces Round #755 (Div. 2) Game with Stones 题解 (Java/C++)

题解

首先我们注意到对于第一堆石头,一定需要和第二堆石头一起操作。而当第一堆石头被拿完了之后,同理第二堆石头一定需要和第三堆石头一起操作。以此类推,我们发现,操作一定是从左到右依次操作。
因此我们维护一个数组after_left来记录左边一堆石头被取完后剩下的石头数(可以为负数)。显然,after_left[i]=a[i]-after_left[i-1]。以a=[1,2,5,1,1]为例,after_left=[1,1,4,-3,4]。

现在我们考虑截取一个子数组的情况。根据上面结论,我们依然从左往右依次考量。显然,此时我们需要将after_left[l]增加a[l]-after_left[l]以抵消其左侧的石头堆的影响。
而after_left[l]增加a[l]-after_left[l]后会导致after_left[l+1]减少a[l]-after_left[l]。after_left[l+1]减少会导致after_left[l+2]增加a[l]-after_left[l]。依次类推。

于是这个思路就非常自然了。我们考虑如何判断从l到r的子数组是否能够胜利。
我们记diff=a[l]-after_left[l]。于是显而易见的如果这个子数组能够胜利,必然有:$$\begin{cases}
\text{after_left[i]}+\text{diff}\geq 0, & i-l \equiv 0 (mod 2)\\
\text{after_left[i]}-\text{diff}\geq 0, & i-l \equiv 1 (mod 2)\\
\text{after_left[r]}\pm \text{diff}= 0\\
\end{cases}$$因为经过变动后,子数组中的每一堆石头都必须不能出现负数。同时,变动后,最后一堆石头剩余的必然为0。

于是实现也就很自然了。我们根据下标的奇偶性用线段树分别维护其区间最小值。
于是我们就能从小到大依次枚举l的值。对于每一个l,我们通过二分搜索找到一个最大的r,使得最小值经过调整后均大于等于0。
同时我们利用两个Map根据下标的奇偶性记录after_left的值与下标的关系。

于是我们依次枚举l,并利用线段树维护的区间最小值二分搜索最大的r。接着在l到r的范围内,根据奇偶性拿到所有$\pm \text{diff}$的下标。最后我们用l和r再通过二分筛选出所有在范围内的下标即可。

代码

Java

Submission #136241155 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #136242334 - Codeforces
Codeforces. Programming competitions and contests, programming community
蜀ICP备19018968号