Codeforces Round #876 (Div. 2) 题解

A The Good Array

考虑从前向后贪心。能不填就不填对前面来说一定合法且不劣，对后面来说一定更优。每隔 k 个填一个即可，可能最后一个位置要额外填，特判一下就好了。

B Lamps

简单贪心。由于 x 小的更容易坏，所以我们一定先使用小的。然后冷静分析一下发现这样操作对于每个 x 是独立的，对每个 x 取前 x 大即可。

C Insert Zero and Invert Prefix

取反这种操作正做反做是本质相同的，所以直接考虑倒过来做。相当于每次从 a 中取一个 0 删掉，把前面取反。冷静分析发现只要最后一个不是 1 一定有解，简单构造方案即可。

D Ball Sorting

考虑我们的操作本质是什么。实际上我们每次取出一个数插入到一个位置就相当于删除这个元素，因为我们可以提前钦定将这个元素放到正确的位置上。然后对于每个 0 相当于删除一个连续段，所以我们相当于对每个 k 求删除 k 个连续段，使剩下序列升序的最小代价。直接 dp 即可。

E Decreasing Game

容易发现后手胜的一个充分条件是原集合可以划分为两个相等的集合，实际上这也是必要的。因为其余情况先手随便选也永远不可能划分为两个相同集合。背包判定即可。