Codeforces Round #756 ABCDEFG Solutions (Java/C++)

A. Make Even

Solution:

Obviously, if there is no even number, -1 is output. If the last digit itself is an even number, 0 is output. If the first digit is an even number, 1 is output. Otherwise, output 2.

Code:

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

Solution:

We first allocate according to the 2+2 model. Then adjust according to the rest of the people.

Code:

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

Solution:

Obviously n must be the last one to be added to a.
So we observe the situation when n=6 and p=[n, 1,2,3,4,5]. After the change, a=[5,4,3,2,1,n] is obtained.

So we only need to check whether n is at both ends, and then reverse the remaining array.

Code:

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

Solution:

We let node[p[i]].order=i. In other words, we write down the order number of each node.

So obviously, assuming u is the parent node of v, then the length of the edge between u and v only needs to be set to node[v].order-node[u].order. In this way, the length from the root node to v is exactly its order number.

If negative edge weights are found in the process, there is no solution.

Code:

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)

Solution:

We maintain the minimum time for friends to reach each node.
So it is not difficult to find that if the depth of a node +1 is less than the shortest time, then the node can be walked.

So we start from node 1, and every time we encounter a node that cannot be walked, it means that we need a friend here, and this friend arrived at this node in the shortest time. And if you can reach the leaf node in the end, just output -1.

Code:

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

题解

First of all, obviously it is necessary to make a prefix sum array for the amount of deposits and withdrawals of students.
For any interval [l,r], we only need to ensure that the minimum value of the prefix sum array of the interval + s is greater than or equal to 0.

So naturally, we use the segment tree to maintain an interval minimum value for the prefix sum. Then for each l, continue to try backwards the r according to the r left by the previous l until the condition is not met.

代码

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

The 2500 in Div3 really made me think about it for a long time.

This problem is obviously taken from left to right, but the key is to judge the left and right according to the position of the diagonal line.

Codeforces Round #756 Robot and Candies Solution (Java/C++)
Solution:First of all, we can immediately find that for the grid (x, y), no matter how the robot moves, the parity of the grid x+y is always the same. So it is natural to solve for odd and even numbers separately.
Click the link above for detail solution
Show Comments
DigitalOcean Referral Badge