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
C++
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
C++
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
C++
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:
- 900 is divided into 3 numbers. Obviously, it can be divided into [100, 100, 700].
- 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
C++
E. Non-Decreasing Dilemma
This question is a very typical application of line segment tree, very common, it is recommended to master this usage.
