【VP 记录】EDU136

KSCD_ · 2024-06-06 22:28:55 · 个人记录

情况

场正常切 ABC，D 题想了一半感觉很多漏洞，最终没做出，赛后发现没看的 EF 都紫，不看了。

题解

A. Immobile Knight

基本循环 + 判断，略过不表。

B. Array Recovery

发现不降的序列一定合法，因此只要某一位可以变为减去 d_i 就有多种情况，否则唯一合法的 a 即为 d 的前缀和数组。

C. Card Game

对第 n 和第 n-1 张牌的情况进行分讨：

• 若先手有第 n 张牌，直接打出必胜，先手必胜方案数 \binom{n-1}{\frac{n}{2}-1}
• 若先手没有第 n 张牌且没有第 n-1 张牌，则后手直接打出 n-1 必胜，先手必败方案数 \binom{n-2}{\frac{n}{2}}
• 若先手没有第 n 张牌且有第 n-1 张牌，只能直接打出消耗掉后手的第 n 张牌，然后后手变为先手，n 减小 2

因此记录先后手递归下去累加即可，特判 n=2 时必胜 1 种平局 1 种，其实数据范围还可以再大一点的。

D. Reset K Edges

最大值最小，容易想到二分最大深度 x，考虑怎么判断深度是否合法。二分复杂度为 \log n，所以要在 n 的复杂度内判断。

考虑从哪里断开所用次数最小。发现若从根开始保留到深度为 x，可能会导致需要的次数变多，例如在深度为 x+1 的那一层有多个点有同一父亲，完全可以直接把父亲接到根上。

所以应该用深度尽可能低的祖先节点连，因此从叶节点向上搜索，若某一节点已有 x 级子节点，直接将这一节点改到根节点上即可，并不再用其向上更新祖先节点，这样一定是最优的。

由于每个节点的父节点都比其编号小，直接倒序枚举就能保证子节点全部处理过。由于每一个节点只会被其父节点使用一次，再乘上二分的复杂度 \log n，总复杂度 O(n\log n)