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