Codeforces Round #754 ABCDE Solutions (Java/C++)

A. A.M. Deviation

Solution:

Obviously it is meaningless to adjust $a_1$ and $a_3$. So it is not difficult to find that the effect of each operation on the result is 3.

Therefore, only the remainder of the initial value divided by 3 needs to be considered. If the remaining 0, then output 0. Otherwise, output 1 (because 3 is subtracted again when the remainder is 2, you can get -1).

Code:

Java

C++

B. Reverse Sort

Solution:

Obviously, every replacement is the replacement of the 1 on the left and the 0 on the right. And such replacements must not conflict with each other. Therefore, only one operation is required at most.

Code:

Java

C++

C. Dominant Character

Solution:

In fact, there are only 4 types of substrings that may satisfy the conditions:

1. Obviously, if there are two consecutive a, that is, "aa", then this substring must meet the condition.
2. "aba" or "aca".
3. "abca" or "acba".
4. "abbacca".

We try to construct other approaches.
We start with the fourth case. We try to add letters after "abbaccc", we need to add two additional letters a.
Obviously, two letters a cannot be added directly, because at this time #1 is a better solution.
Also cannot add aca or aca. At this time #2 is a better solution.
Nor can you add abca or acba. At this time #3 is a better solution.
But adding abba or acca does not work either. Because too many other letters have been added.

Code:

Java

C++

D. Treelabeling

The key to this problem is to find the condition of $u\oplus v> \min(u,v)$.

E. Array Equalizer

The key to this problem is to take the unknown b[1]-a[1] as a variable and substitute it into other numbers to obtain a series of linear expressions. Then according to b[1]-a[1], find expressions greater than 0 and less than 0 through binary search.