Codeforces Round #602 (Div. 1)

前言

康复训练Day3
掉分辣，心疼死辣，区间翻转一生之敌。

题解

A - Messy

我的做法太憨了就8说了。
赛后学长说次操作可以构造任意一个括号序列，每次操作一定可以在一个位置上放上你想放的左/右括号，所以就构造就完事了。

B - Optimal Subsequences

优先选值大的，如果值相等则优先选下标小的，按这个标准排序后前个就是长度为的目标序列，每次询问要求前个数中下标第小的，可以离线下来平衡树也可以直接上主席树。

C - Arson In Berland Forest

发现这个T具有二分性，如果T可行，对于任意t<T一定也可行。那么就二分这个T，把能点的树（指影响范围内的全是的位置）全部点了，做一次差分看看最后损坏的树与实际损坏的树是否一致。

D - Wrong Answer on test 233

若，则无论填什么都不影响前后的分数差，如果，则有一种填法能使分数，有一种填法能使分数，剩下的填法能使分数保持不变。
假设有个位置满足，那么我们要求从这位置里选出若干个位置贡献，若干个位置贡献，剩余一些数为种贡献为填法，且数大于数的方案数。
显然答案满足对称性，于是我们考虑用总方案数减去保持不变的方案数再折半。
枚举贡献与的位置数，答案显然为。

E - Not Same

考虑从大到小排序后一列一列去构造，设第多的是，从这个位置往上填，有多余的就从最底下，即往上填，实际操作次数也从次变为次。