Codeforces Round #835 (Div. 4) :D E题题解


先来说说这一场吧,本来可以写五道的,结果理解错题意+没注意数据范围导致两个题没过,挺可惜的,不然上大分。

D:Challenging Valleys
大概题意:给你一个数组,判断它是否符合我们的要求:某一段区间(可以是一个点)是否是左边下降,右边上升的。
当时读完题目理解成,是否有一个最低点了,但是题目要求的是只能有一个下降的点(或区间),这导致我WA了两发之后放弃去写E,就是说,这段区间处在一个最低点或者下降之后,后面所有的都不能再下降。(理解能力还是有所欠缺)

E:Binary Inversions
题目大意:你最多可以更改一次数组某一位的值,0变1,或者1变0,求你操作或者不操作的最大逆序对的数量。赛后用前缀和写出来了,但是想学一下大佬的推公式,发现我学不会。(太菜了)
操作肯定是第一个0变1或者最后一个1变0。
可以用前缀和数组处理,然后0变1的话,该位置后面的前缀和+1来维护,最后一个1变0同理。
记得开long long!记得开long long ! 记得开long long!
不去操作数组的逆序对数量也要记录。
