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.

Codeforces Round #737 Ezzat and Two Subsequences Solution (Java/C++)
Solution:First, it is not difficult to guess the conclusion of this question: that is, the largest number is divided into one subsequence, and the remaining part is divided into another subsequence. But the proof of this problem is still a bit interesting.
Click the link above for detail solution

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

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

C++

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

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

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

C++

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

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.

Codeforces Round #737 Ezzat and Grid Solution (Java/C++)
Solution:This question is divided into four parts.Part 1: HashBecause there at most m segments of the grid that contain digits 1, So we naturally think of hashing
Click the link above for detail solution