2023-09-18
题目
难度&重要性(1~10):5
题目来源
luogu
题目算法
贪心
解题思路
一道大水题。
这道题解法非常的套路，我们需要对于处理按位或和按位异或时，首先就要把数拆成二进制的形式去考虑。
首先我们需要简单了解一下按位或和按位异或的运算规则：
-
按位或，对于两个数每一位，只要有一个是 \(1\) 结果就是 \(1\)，只有当两个都是 \(0\) 是结果才为 \(0\)。
-
按位异或，对于两个数每一位，如果两位相同即为 \(0\)，两位不同即为 \(1\)。
知道这些已经可以做这道题了，我们就可以考虑贪心了。
我们的贪心要做一个小小的分讨：
-
当 \(n\equiv0\pmod{2}\) 时，每对 \(b_i\) 做一次处理，\(b_i\) 中为 \(1\) 的位在 \(a_i\) 之中就都为 \(1\) 了。而由于 \(1\) 的个数是偶数个，异或结果就只能为 \(0\)，这很明显答案单调不增。所以最大答案就是不进行任何的操作，而最小答案则是对每一个 \(b_i\) 都进行一次操作，这样 \(b_i\) 中含 \(1\) 的位数在答案中就都是 \(0\)。
-
当 \(n\equiv1\pmod{2}\) 时，而由于 \(1\) 的个数是奇数个，异或结果就为 \(1\)，这很则是答案单调不减。所以最小答案不进行任何的操作，最大答案就每一个 \(b_i\) 都进行一次操作，这样 \(b_i\) 中含 \(1\) 的位数在答案中就都是 \(1\) 了。
这样我们就解决了这道题，具体细节请看代码。
完成状态
已完成