Codeforces Round #737 ABCD Solutions (Java/C++)

A. Ezzat and Two Subsequences

The greedy algorithm for this problem is not difficult to think of. But its rigorous proof still interesting.

B. Moamen and k-subarrays

Solution:

It is not difficult to think that we will divide the parts that have already been sorted into one.
Therefore, we only need to find out the position of the target by sorting, and then see if the target position is continuous. If it is not continuous, then you need to add a new sub-array.
If the number of sub-array required is greater than k, then output No, otherwise output Yes.

Code:

Java

C++

C. Moamen and XOR

题解

Obviously if one bit of $a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$ is 1, then each $a_i$ in this bit is 1. So we consider the situation according to the parity of n.

When n is an even number:
If one bit of $a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$ is 1, then $a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$ This bit must be 0.
And when there is an odd number of 0s in one bit of $a_1, a_2, \dots a_n$, this one bit of $a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$ is 0, but $a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$ must be 1 in this bit.
And when there is an even number of 0s in one bit of $a_1, a_2, \dots a_n$, this one bit of $a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$ is 0, but $a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$ must be 0 in this bit.

When n is an odd number:
If one bit of $a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$ is 1, then $a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$ This bit must be 1.
And when there is an odd number of 0s in one bit of $a_1, a_2, \dots a_n$, this one bit of $a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$ is 0, but $a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$ must be 0 in this bit (Because there is an even number of 1s left).
And when there is an even number of 0s in one bit of $a_1, a_2, \dots a_n$, this one bit of $a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$ is 0, but $a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$ must be 1 in this bit.

In summary,
When n is an even number, we only need to enumerate the first place where the part of & is 1 and the part of $\oplus$ is 0. Then calculate through permutation and combination.
When n is an odd number, no matter what, the left side of the equation cannot be greater than the right side, so you only need to calculate all the possibilities to make the equation equal through permutation and combination.

In addition, there is a special case, that is, when every bit is 0, the left and right sides of the equation are 0.

代码

Java

C++

D. Ezzat and Grid

The key point for this question is to think of the simplest and brute force DP, and then use the segment tree to optimize it.