Codeforces Round #737 ABCD 题解 (Java/C++)

A. Ezzat and Two Subsequences

这个题目的贪心算法并不难想到。但其严格证明还是有一些意思。

B. Moamen and k-subarrays

题解

不难想到，我们会把本身已经排好序的部分分成一份。因此我们只需要通过排序找出目标的位置，然后再看目标位置是否连续。如果不连续，那么就需要新加一段。如果需要的段数大于k，则不行，否则就可以。

代码

Java

C++

C. Moamen and XOR

题解

显然$a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$的某一位为1，则在这一位上每一个$a_i$均为1。于是我们可以对n分情况讨论。

当n为偶数时：
如果$a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$的某一位为1，则$a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$的这一位必为0。
而当$a_1, a_2, \dots a_n$的某一位上，有奇数个0时，$a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$的这一位为0，但$a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$在这一位必为1。
而当$a_1, a_2, \dots a_n$的某一位上，有偶数个0时，$a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$的这一位为0，但$a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$在这一位必为0。

当n为奇数时：
如果$a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$的某一位为1，则$a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$的这一位必为1。
而当$a_1, a_2, \dots a_n$的某一位上，有奇数个0时，$a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$的这一位为0，但$a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$在这一位必为0（因为剩下了偶数个1）。
而当$a_1, a_2, \dots a_n$的某一位上，有偶数个0时，$a_1 ,\&, a_2 ,\&, a_3 ,\&, \dots ,\&, a_n$的这一位为0，但$a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$在这一位必为1。

综上，
当n为偶数时，我们只需要枚举第一个让&的部分为1，且$\oplus$的部分为0的地方。通过排列组合计算即可。
当n为奇数时，不论如何，等式左边不可能大于右边，因此只需要通过排列组合算出让等式相等的所有可能即可。

另外，有一个特殊的情况，那就是每一位都是0的情况，等式左右均为0。

代码

Java

C++

D. Ezzat and Grid

这个题的关键是想到最简单暴力的DP，之后使用线段树进行优化即可。