Codeforces Round #741 Two Hundred Twenty One 题解 (Java/C++)

题解

首先,我们令$b[i]=a[i]\cdot (-1)^{(i-1)}$,$sum(l,r)=\sum_{i=l}^r{b[i]}$。

于是对于任意的i,b[i]要么是1要么是-1。因此如果最后的和为0,那么必然有1的数目和-1的数目相同。于是必然有,如果要和为0,那么这个区间的长度必为偶数。

先说结论:当原区间长度为奇数时,只需要删去一个数,就可让区间和为0。当原区间长度为偶数时,需要先删去一个数构成奇数长度,也就是总共需要删去两个数。当然,如果原区间和本身就是0,则不需要删除任何数。


我们考虑证明:

接着我们考虑在[l,r]中,删去下标为x的数。我们发现删去之后,sum(l,x-1)其实不会受到任何影响,而sum(x+1,r)的值正好需要乘以-1。
于是我们得到,如果删去x后,区间的和为0,则必有sum(l,x-1)=sum(x+1,r)。

现在,不妨假设原先sum(l,r)>0,且r-l+1为奇数。
此时,我们令x=r,也就是我们删去最右边的数。此时,如果sum(l,x-1)=0,那这个就是我们要的答案。因此我们只考虑sum(l,x-1)>0的情况。
接着,我们令x=r-1。考虑x左右两侧的区间和,我们发现:sum(l,x-1)-sum(x+1,r)的值随着x的变化而发生相应的变化。而变化的可能只有-2,0,2。
同时,我们注意到,当x移动到l时,sum(l,x-1)=0,sum(x+1,r)>0。
于是,随着x从r变道l,sum(l,x-1)-sum(x+1,r)由一个必然大于0的值,变成了一个必然小于0的值。而每次的变化只能是-2,0,2。因此必然存在这样一个x,使sum(l,x-1)-sum(x+1,r)=0。

于是,我们得到当r-l+1为奇数时,只需要删一个数即可。


现在剩下的问题就是如何找到这样的x,使得sum(l,x-1)-sum(x+1,r)=0。

我们将原等式变形后可以得到:sum(1,r)-sum(1,x)=sum(1, x-1)-sum(1,l-1)。进一步变形可得:sum(1,x)+sum(1, x-1)=sum(1,r)+sum(1,l-1)。

因此我们只需要维护一个前缀和,且在计算前缀和时,通过map记录sum(1,x)+sum(1, x-1)相应的下标。这样每次我们只需要查出所有和为sum(1,r)+sum(1,l-1)的下标,然后二分找出属于[l,r]之间的任意一个即可。

代码

Java

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

C++

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