VP CF975 div2
前言
别人说这场好,我就打打
A
简单模拟,分奇偶位置即可。
B
一开始没注意到端点的边界问题,后来分讨了一下,把端点和中间的点分开考虑即可
C
卡了 1h 的唐题,首先由于每堆中不能出现同种卡牌,所以答案一定<=n。当时想到这就开二分答案了,发现 k=0 的情况过不了,以为是特殊边界问题,直接特判,WA了两发后才意识到事情的严重性。发现可以 O(1) 判断某一大小 s 是否满足,具体是:1.若 sum<=max{a[i]}*s 则判断能不能补到 max{a[i]}*s.2.若 sum>max{a[i]}*s,则判断能不能补到 s 的倍数即可。复杂度O(n)
D
赛时看到过E的更多,就转战E了,这题没看,所以咕咕咕。
E
感觉很好想,先考虑如果确定了最后的深度 d ,有哪些点是满足条件的,无非就两种。一是其自身深度<=d,二是其最远儿子的深度>=d,这两需要同时满足,就可以简单查分把 d 求出来,在跑个 dfs 求答案即可。
F
感觉第一步不难,第二步有点难。首先选最大的一定是不劣的,因为选最大值会使答案中最大值的那部分至少增加 1,但是个数那部分只会减少 1,所以不劣。
woc第二步没看懂,那就咕咕咕。