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

A. Ezzat and Two Subsequences

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

Codeforces Round #737 Ezzat and Two Subsequences 题解 (Java/C++)
题解首先,不难猜到这个题的最终结论:那就是最大的数分为一段,剩下的部分分为另一段。但这个题目的证明还是有点意思的。
点击上面链接查看详细题解

B. Moamen and k-subarrays

题解

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

代码

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

题解

显然$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

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

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

Codeforces Round #737 Ezzat and Grid 题解 (Java/C++)
题解这个题大概分为四个部分。 第一部分:Hash由于最多只有m段1,因此我们很自然的想到将$1\leq l \leq r \leq 10^9$的hash到$1\leq l \leq r \leq 2\cdot 3\cdot 10^5$。将原先的线段的两端离散后排序,按照大小顺序依次hash即可。
点击上面链接查看详细题解
展示评论