Codeforces Round #731 (Div. 3) ABCDEFG Solution (Java/C++)

A. Shortest Path with Obstacle

Solution:

If and only if the three points of ABF are in a straight line and F is between AB, the answer is Manhattan distance +2. Otherwise, the answer is the Manhattan distance of AB.

Code:

Java

C++

B. Alphabetical Strings

Solution:

Find the position where the letter a appears for the first time, and then start from this position and find the subsequent letters to the left and right in turn. If you can't find the entire string one by one, print no.

Code:

Java

C++

C. Pair Programming

Solution:

Just simulate directly. As long as A can meet the conditions, take priority, otherwise, try to see whether the conditions can be met in B. Otherwise it will not work.

Code:

Java

C++

D. Co-growing Sequence

Solution:

First of all, the first number must be 0. At the same time, obviously (x[i]^y[i])&(x[i+1]^y[i+1])=(x[i]^y[i]). So, y[i+1]=[(x[i] ^y[i]) & x[i+1]]^ (x[i] ^y[i]).
So that, for the last result x[i] ^y[i] and x[i+1], if a certain position is 1, then the y of this position should be 0.
If x[i] ^y[i] is 1, and x[i+1] is 0, then y must be 1.
If x[i] ^y[i] is 0 and x[i+1] is 1, then y should be 0. This can ensure that y is as small as possible.

Code:

Java

C++

E. Air Conditioners

Solution:

There are only three situations for the final temperature of each room: 1. An air conditioner on the left has the lowest temperature; 2. An air conditioner on the right has the lowest temperature; 3. Your room has the lowest temperature.

So naturally, we first scan from left to right. dp[i]=min(dp[i-1]+1, a[i]). In the same way, scan from right to left again.

Code:

Java

C++

F. Array Stabilization (GCD version)

Solution:

The template problem of segment tree. Maintaining the GCD of the interval. find the smallest interval length by binary search. So that the GCD of any two divisions is equal to the GCD of the entire array.

Code:

Java

C++

G. How Many Paths?

Solution:

Two DFS is enough.
For the first DFS, we can find out: unreachable points, points with multiple sources, points that produce loops, and ordinary points with only one path.
Then, the second DFS is mainly to expand the points where the loop is generated and the points with multiple paths. Because starting from these points, all reachable points have infinite paths or multiple paths to go.

Code:

Java

C++