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

A. Make Even

题解

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

代码

Java

Submission #137102014 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #137102216 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Team Composition: Programmers and Mathematicians

题解

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

代码

Java

Submission #137104249 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #137104347 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #137105135 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #137105231 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. Weights Assignment For Tree Edges

题解

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

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

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

代码

Java

Submission #137107717 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #137107898 - Codeforces
Codeforces. Programming competitions and contests, programming community

E. Escape The Maze (Easy/Hard)

题解

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

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

代码

Java

Submission #137110625 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #137110858 - Codeforces
Codeforces. Programming competitions and contests, programming community

F. ATM and Students

题解

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

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

代码

Java

Submission #137115140 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #137115404 - Codeforces
Codeforces. Programming competitions and contests, programming community

G. Robot and Candies

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

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

Codeforces Round #756 Robot and Candies 题解 (Java/C++)
题解首先,我们可以立刻发现,对于格子(x,y),不论机器人怎么移动,其格子x+y的奇偶性始终不变。于是很自然的,我们讲奇数和偶数分开求解。
点击上面连接查看详细题解