本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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)$