前言

康复训练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

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