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

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

C++

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

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

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

C++

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

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

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

C++

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

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

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

C++

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

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

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

C++

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

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

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

C++

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

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

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

C++

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

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.

Codeforces Round #744 Minimal Coverage Solution (Java/C++)
Solution:First of all, let’s think about the simplest way: Obviously, for every segment, there will be two possibilities of going to the left or right. Each possibility contains three pieces of information:
Click the link above for detail solution