比赛链接

A. Make Even

分类讨论一下：

1. 结尾是偶数，不需要操作
2. 否则，开头是偶数，1次操作
3. 否则，存在偶数，2次操作
4. 否则，无解

B. Team Composition: Programmers and Mathematicians

首先，每一个队伍至少要有一个主程和数学选手，所以至多能组\(\min(a, b)\)个队。

其次，每个队伍要有4个人，所以至多能组\(\lfloor \dfrac{a + b}{4} \rfloor\)个队。

二者取较小者即为答案。

C. Polycarp Recovers the Permutation

首先，每次都是取最较小的，所以最大值一定要在开头或结尾，否则无解。

然后就是构造了，一个显而易见的构造方法：若最大值在开头，就把后\(n-1\)个元素翻转一下；否则，把前\(n-1\)个元素翻转一下。

D. Weights Assignment For Tree Edges

对于一条从根开始的链，越往下走dist越大。所以，\(p_1\)必须是根，否则无解。

然后，从\(p_2\)开始向后枚举，枚举到节点\(u\)时，记前一个节点为\(prev\)，u的父节点为\(fa\)。

此时\(fa\)必须已经枚举过了，否则无解。

然后，为了满足递增的条件，\(weight_{i} = dist_{prev} - dist_{fa} + 1\)。

E1. Escape The Maze (easy version)

首先，如果一个朋友在Vlad之前占据了节点\(u\)，那么以\(u\)为根的子树就不需要考虑了，因为要走到子树中就必须跨过这个朋友，而这是不允许的操作。

所以，所有朋友的最优策略就是不断向父节点走，尽可能占据更多的节点。

对于每一个节点，记录一个时间限制，表示某个朋友占据这个节点的最小时间。对于每一个朋友，让他不断向上跳，跑出所有时间限制。

然后对于Vlad，跑DFS，如果到达某个节点的时间超过时间限制，表示这个节点已经被占据了，不可行。如果能跑到任一叶子节点，就有解。

这样最差的时间复杂度是\(O(n^2)\)，一个Case就是一条链然后有\(n-1\)个朋友。为了防止超时，先将朋友按初始节点的深度从小到大排序，然后依次跑朋友向上跳的流程。朋友向上跳的时候，如果遇到已经被占据的点就可以停止了。

E2. Escape The Maze (hard version)

在E1的基础上，对于每一个节点多记录一个这个节点是被哪一个朋友占据的，然后维护一个需要保留的朋友的集合。

在DFS的时候，如果遇到一个已经被占据的节点，就将占据这个节点的朋友加入集合。

F. ATM and Students

二分+线段树。

枚举起点，然后看满足条件的最大的终点在哪，然后再取一个最大值。

先整个前缀和，那么从\(l\)开始，在\(r\)结束时，ATM中剩余的钱就是\(s_{r} - s_{l - 1}\)，其中\(s\)表示\(a\)的前缀和。

然后找最大的终点可以用二分来找，假设起点为\(st\)，二分到的\(mid\)可行的话需要\(s + \min_{st}^{mid} s_i - s_{st-1} \ge 0\)，这需要一个搞区间最小值的数据结构，线段树整上完事。

G. Robot and Candies

待补。