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

A. Domino Disaster

Solution:

Obviously, if the first row is LR or RL, then the second row only needs to be the same.
If the first row is U, then the second row is obviously D. Conversely, if the first row is D, the second row is U.

Code:

Java

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

C++

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

B. MEXor Mixup

Solution:

Obviously, according to the definition of MEX, all numbers from 0 to a-1 must be selected, and a must not be selected.

Then, if $0\oplus 1\oplus\dots\oplus a-1=b$, just output a directly.

If $0\oplus 1\oplus\dots\oplus (a-1)\neq b$ and $0\oplus 1\oplus\dots\oplus (a-1)\oplus b\neq a$, then we choose 0 to a-1, and $0\oplus 1\oplus\dots\oplus (a-1)\oplus b$, so in total a+1 is enough.

If $0\oplus 1\oplus\dots\oplus (a-1)\neq b$ and $0\oplus 1\oplus\dots\oplus (a-1)\oplus b= a$, because you cannot choose $0\oplus 1\oplus\dots\oplus (a-1)\oplus b$, so we randomly choose any other number x, where $0\oplus 1\oplus\dots\oplus (a-1)\oplus b\oplus x \neq a$.
That is, select 0 to a-1, and x and $0\oplus 1\oplus\dots\oplus (a-1)\oplus b\oplus x$, so in total a+2 is enough.

Code:

Java

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

C++

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

C. Carrying Conundrum

Solution:

Because the defined addition operation is to carry forward the first two bits. So its operation can be divided into two parts, odd and even bits.

So we split the odd and even bits of n, we can get the sum of odd bits and the sum of even bits, denoted as x and y, respectively. Then we just need to find all x=x1+x2 and y=y1+y2. Among them, a is composed of x1 and y1, and b is composed of x2 and y2.

Obviously, for fixed x and y, once x1 and y1 are determined, x2 and y2 can be determined. So there are a total of $(x+1)\cdot(y+1)$ possibilities.
Finally, consider the condition that a and b cannot be zero. Obviously if and only when x1=0 and y1=0, a is 0. If and only if x1=x and y1=y, b is 0.
So, the final result is: $(x+1)\cdot(y+1)-2$.

Code:

Java

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

C++

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

D. Expression Evaluation Error

Solution:

Obviously, we want to avoid carry as much as possible. If you have to carry out, then the bit of carry as low as possible.
So it is natural to think that we take 1 from the highest position, as long as this 1 is taken away, it is still possible to be divided into n-1 shares. If the remaining number is not enough, then it can only be carried out.

Give a few examples:

  1. 900 is divided into 3 numbers. Obviously, it can be divided into [100, 100, 700].
  2. 200 is divided into 3 numbers.
    For the first time, we tried to take away 100 and found that the remaining 100 was enough to be divided into 2 numbers.
    The second time, we found that we could not take away 100, because the remaining 0 could not be divided into 1 numbers. So it can only be forced to carry. So try to take away 10, and the remaining 90 is enough to give 1 number.

In general, every time you try to take 1 at the highest position. If it fails, it can be forced to carry.

Code:

Java

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

C++

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

E. Non-Decreasing Dilemma

This question is a very typical application of line segment tree, very common, it is recommended to master this usage.

Codeforces Round #742 Non-Decreasing Dilemma Solution (Java/C++)
Solution:This problem is a typical application of segment tree.As shown in the figure below, we maintain three attributes for each interval:
Click the link above for detail solution