【cf639X】VK Cup 2016 – Round 1

2016年3月29日7513

今天早上起来看到挂了两题又掉分QAQ

昨晚赛前几个小时本来想睡个觉结果失眠,只能又起来写了作业,比赛虽然有点累但是最后看C过了pre还是很开心的

没料到在debug的时候删掉了某行代码后来没发现

看了下记录也打了50+场了,还是这样半吊子水平唉,算了大学再抱神犇大腿吧

目前每天刷理综抢救文化课,也没啥时间,好多坑没填,博客留言没回的神犇们对不住了

B. Bear and Forgotten Tree 3

构造深度为h,最长链为d的树

应该大家都会做0。0

C.Bear and Polynomials 多项式

在差绝对值为K范围内修改一个多项式Q的某一系数,使得Q(2)=0

 

先全部进位一下,然后找出最低位的1,不可能改动比它高位的系数

比它低位的系数依次枚举一下

注意超过2K就直接退出

D. Bear and Contribution

如果b > c * 5,就让 b = c * 5

那么可以直接计算出将某个人贡献增加到某个x值的代价

可以容易得知,最终一定存在某个人的贡献,满足最优解的x值与他相差不超过4

那么x的取值有5 * n种情况

发现如果第i个人在X0时比j代价小,则在X+5时i也比j优

对于 mod 5 意义下同余的x,从小到大排列之后,依次计算代价

用堆加标记维护最优的K个人即可