「CF1572B」Xor of 3

发表于 2025-03-17 更新于 2026-03-05 分类于 Codeforces 本文字数： 359 阅读时长 ≈ 1 分钟

Description

给出一个长度为 $n$ 的序列 $a$ ，仅由 $0$ 或 $1$ 构成。

你需要对序列进行至多 $n$ 次操作（或者说明这是不可能的），每次操作你可以选择一个下标 $i$ ( $1 \leq i \leq n - 2$ )，然后将 $a_i, a_{i + 1}, a_{i + 2}$ 均改成 $a_i \oplus a_{i + 1} \oplus a_{i + 2}$ 。

数据范围： $3 \leq n \leq 2 \times 10^5$ ， $0 \leq a_i \leq 1$ 。

时空限制： $1$ s / $256$ MiB。

Solution

首先注意到，经过一次操作之后，所有数的异或和肯定不变。故有一个必要条件是，所有数的异或和为 $0$ 。

当 $n$ 为奇数时，有一个构造：

先选择 $n - 2, n - 4, \cdots, 3, 1$ 进行操作。此时 $a_1 = 0$ （即所有数的异或和），且 $a_{2i} = a_{2i + 1}$ 。
再选择 $1, 3, \cdots, n - 4, n - 2$ 进行操作。此时每次操作的位置 $x$ 必定满足 $a_x = 0, a_{x + 1} = a_{x + 2}$ ，故该次操作会使得 $a_x = a_{x + 1} = a_{x + 2} = 0$ 。

当 $n$ 为偶数时，考虑找一个长度为奇数，异或和为 $0$ 的前缀，然后对前后缀进行同 $n$ 为奇数情况的构造。

可以证明，若找不到这样的前缀，则一定无解。因为此时原串形如 1aabb..zz1（即首尾均为 $1$ 且 $a_{2i} = a_{2i + 1}$ ），不论如何操作仍然有 $a_{2i} = a_{2i+1}$ ，首尾的 $1$ 无法消掉。