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

A. Casimir's String Solitaire

Solution:

Obviously, Yes if and only if the sum of the number of letter A and letter C is equal to the number of letter B, otherwise No.

Code:

Java

C++

B. Shifting Sort

Solution:

Obviously, we do n operations from right to left, and each operation only restores the order of 1 number.

Code:

Java

C++

C. Ticks

Solution:

Go through the map in turn from bottom to top, and try to find the largest possible d whenever a colored cell is found. If d>k, start from this point and mark the relevant points. Finally, just check whether all the colored cells have been marked.

Code:

Java

C++

D. Productive Meeting

Solution:

Every time, use the priority queue to find the two people with the strongest social willingness and let them talk to each other.

Code:

Java

C++

E1. Permutation Minimization by Deque

Solution:

It only needs to see if the current number is less than the number at the front, if it is, put it at the front, otherwise put it at the back.

Code:

Java

C++

E2. Array Optimization by Deque

Solution:

It is not difficult to find that when we add a new number, whether we put it in front or behind, the relationship between this number and other previous numbers will be determined. The relationship between this number and the following number is actually completely determined by the following number.

So we only need to add each number greedily. When we add a new number, we only need to see how many of the existing numbers are smaller than the current one, and how many are larger than the current one.

In order to count the number of numbers greater than or less than a certain number, we can hash the array to the range of 1 to $10^5$, and then use a binary indexed tree or segment tree to count the number of numbers in the interval.

Code:

Java

C++

F. Array Stabilization (AND version)

Solution:

Taking n=5, d=2 and n=4, d=2 as examples, we can get the transformation of the figure below:

It is not difficult to find that each position is a fixed cycle. We find these cycles, and then count the longest continuous 1s.

Because it is a loop, we directly loop twice to find the longest continuous 1.
Another thing to note is that if it is all 1, just output -1.

Code:

Java

C++

G. Minimal Coverage

It is a good DP problem. The key is to find out the truly effective state. After that, it is easier to think of the state transition equation.