Codeforces Round #756 ABCDEFG 题解 (Java/C++)

A. Make Even

题解

显然，如果没有一个偶数则输出-1。如果最后一位本身就是偶数则输出0。如果第一位是偶数则输出1。否则输出2。

代码

Java

C++

B. Team Composition: Programmers and Mathematicians

题解

我们先按2+2的模式进行分配。然后在根据剩下的人进行调整即可。

代码

Java

C++

C. Polycarp Recovers the Permutation

题解

显然n一定是最后一个被加入到a中的。
所以我们观察n=6，p=[n, 1,2,3,4,5]时的情况。经过变化后得到a=[5,4,3,2,1,n]。

于是我们只需要检查n是不是在两端，然后把剩下的数组反转过来即可。

代码

Java

C++

D. Weights Assignment For Tree Edges

题解

我们记node[p[i]].order=i。也就是说，我们记下每个节点的序号。

于是显然的，假设u是v的父亲节点，那么u和v之间的边长度只需要设置为node[v].order-node[u].order即可。这样一来从根节点到v的长度恰好为其序号。

过程中如果发现负边权则无解。

代码

Java

C++

E. Escape The Maze (Easy/Hard)

题解

我们维护朋友们到达每个节点的最短时间。
于是不难发现，如果一个点的深度+1小于这个最短时间，这个节点就是可以走的。

于是我们从1号节点出发，每遇到一个不可以走的节点，就说明这里需要一个朋友，且这个朋友是以最短时间到达这个节点的。而如果最后能走到叶子节点，则输出-1即可。

代码

Java

C++

F. ATM and Students

题解

首先显然是需要对学生的存取钱的数目做一个前缀和的。
对于任意的区间[l,r]我们只需要保区间的前缀和的最小值+s后大于等于0即可。

于是很自然的，我们使用线段树来对前缀和维护一个区间最小值。然后对于每一个l，根据上一个l留下的r继续往后尝试，直到不满足条件为止。

代码

Java

C++

G. Robot and Candies

Div3里的2500，确实让我想了好久。

这个题目显然是从左往右依次拿取，但关键在于，要根据其斜线的位置来判定左右。