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

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

C++

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

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

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

C++

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

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

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

C++

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

D. Treelabeling

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

Codeforces Round #754 Treelabeling Solution (Java/C++)
Solution:We first consider when $u\oplus v> \min(u,v)$. It is not difficult to find that $u\oplus v> \min(u,v)$ if and only if one of the highest bits of u and v is 0 and the other is 1. Take the following picture as an example:
Click the link above for detail solution

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.

Codeforces Round #754 Array Equalizer Solution (Java/C++)
Solution:First of all, we can naturally notice that i=1 will directly affect all numbers, and the final result will only be affected by b[1]-a[1].
Click the link above for detail solution