B. Button Pressing 题解

题意概述

有 $N$ 盏灯和 $N$ 个按钮。

只有当第 $i$ 盏灯当前是亮的时，才能按下按钮 $i$。按下按钮 $i$ 后：

• 如果 $i>1$，则灯 $i-1$ 的状态翻转；
• 如果 $i<N$，则灯 $i+1$ 的状态翻转；
• 灯 $i$ 本身不变。

给定初始状态 $A$ 和目标状态 $B$，判断是否能经过若干次操作把 $A$ 变成 $B$。

关键观察

设当前灯的状态为：

$$a_1,a_2,\dots,a_N.$$

定义前缀异或序列：

$$p_i = p_{i-1} \oplus a_i \quad (1 \le i \le N),$$

并先令

$$p_0 = 0.$$

于是有：

$$a_i = p_{i-1} \oplus p_i.$$

一次按按钮等价于交换相邻两个前缀位

考虑按下按钮 $i$。

它会翻转灯 $i-1$ 和灯 $i+1$，从而只会影响前缀异或中的两个位置：

$$p_{i-1},\ p_i.$$

更具体地说：

• 灯 $i-1$ 翻转，会让所有下标 $\ge i-1$ 的前缀异或翻转一次；
• 灯 $i+1$ 翻转，会让所有下标 $\ge i+1$ 的前缀异或再翻转一次。

两次叠加后，只有

$$p_{i-1},\ p_i$$

会被翻转。

另一方面，按钮 $i$ 能被按下，当且仅当灯 $i$ 是亮的，也就是：

$$a_i = 1.$$

结合

$$a_i = p_{i-1} \oplus p_i,$$

可知此时一定有

$$p_{i-1} \ne p_i.$$

而把两个不同的二进制位同时翻转，效果正好就是交换它们，也就是：

$$01 \;\longleftrightarrow\; 10.$$

所以，按下按钮 $i$ 等价于交换相邻的两个前缀位 $p_{i-1}$ 和 $p_i$。

可达状态的本质

既然一次操作就是交换相邻的不同前缀位，那么我们实际上可以把前缀异或序列中的若干个 1 和 0 通过相邻交换任意重排。

因此，一个前缀异或序列能够到达哪些状态，唯一不变的是：

$$\text{前缀异或序列中 }1\text{ 的个数}.$$

也就是说，只要两个前缀异或序列中 1 的总数相同，它们就可以互相到达。

为什么还要考虑 $p_0=1$

注意，灯的状态由相邻前缀位异或得到：

$$a_i = p_{i-1} \oplus p_i.$$

如果把整个前缀异或序列全部取反，那么每一位灯的值都不会变：

$$(p_{i-1} \oplus 1) \oplus (p_i \oplus 1) = p_{i-1} \oplus p_i. $$

所以，同一个灯串会对应两种前缀表示：

1. 令 $p_0=0$ 得到的一种；
2. 把整串取反后，等价于令 $p_0=1$ 得到的另一种。

因此，对于目标状态 $B$，如果它在 $p_0=0$ 时的前缀异或中有 $c_B$ 个 1，那么另一种等价表示里就有：

$$(N+1)-c_B$$

个 1。

于是答案就是判断：

设 $c_A$ 是 $A$ 的前缀异或序列中 1 的个数，$c_B$ 是 $B$ 的前缀异或序列中 1 的个数，那么只需检查

$$c_A \in \{c_B,\ (N+1)-c_B\}.$$

如果满足则输出 YES，否则输出 NO。

如何线性计算前缀异或中 1 的个数

直接从左到右维护当前前缀异或值 pref 即可：

• 初始 pref = 0
• 每读到一位，就做一次 pref ^= bit
• 如果此时 pref = 1，就把答案加一

这样得到的是：

$$p_1,p_2,\dots,p_N$$

中 1 的个数。由于这里固定使用的是 $p_0=0$，而 $p_0$ 本身为 $0$，所以不需要额外统计它。

正确性说明

性质 $1$

对任意状态，记其前缀异或序列为 $p_0,p_1,\dots,p_N$，则有：

$$a_i = p_{i-1} \oplus p_i.$$

这是前缀异或定义的直接推论。

性质 $2$

按下按钮 $i$ 时，只有 $p_{i-1}$ 和 $p_i$ 会发生翻转。

并且由于按钮 $i$ 可按的条件是 $a_i=1$，所以有：

$$p_{i-1} \oplus p_i = 1,$$

即 $p_{i-1}$ 与 $p_i$ 不同。于是同时翻转这两位，恰好等价于交换这两个相邻位置。

性质 $3$

相邻交换不同的二进制位，只会改变这些位的位置，不会改变整个前缀异或序列中 1 的总个数。

反过来，对于任意两个长度相同且 1 的个数相同的二进制串，都可以通过若干次相邻交换互相变换。这里允许的基本操作就是：

$$01 \;\longleftrightarrow\; 10.$$

所以，一个状态可达的全部前缀异或序列，恰好就是所有 1 的个数相同的二进制串。

性质 $4$

同一个灯串对应两种前缀异或表示，它们互为按位取反，因此它们的 1 的个数分别为：

$$c_B \quad \text{和} \quad (N+1)-c_B.$$

结论

因此，从 $A$ 可以到达 $B$，当且仅当 $A$ 的前缀异或序列中 1 的个数等于 $B$ 的某一种前缀表示中的 1 的个数，也就是：

$$c_A \in \{c_B,\ (N+1)-c_B\}.$$

算法判定条件正确。

复杂度分析

每组数据只需线性扫描两次字符串。

时间复杂度为：

$$O(N).$$

空间复杂度为：

$$O(1).$$

标准程序

#include <bits/stdc++.h>
using namespace std;

static int prefix_xor_ones(const string& s) {
    int pref = 0;
    int cnt = 0;
    for (char ch : s) {
        pref ^= (ch - '0');
        cnt += pref;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N;
        string A, B;
        cin >> N >> A >> B;

        int ca = prefix_xor_ones(A);
        int cb = prefix_xor_ones(B);

        if (ca == cb || ca == (N + 1 - cb)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}