题目描述

难度分:$2600$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(3 \leq n \leq 2 \times 10^5)$和两个长为$n$的01字符串$a$和$b$。

每次操作，你可以选择一个值为$1$的$a[i]$，然后把$a[i-1]$和$a[i+1]$翻转（异或 $1$）。如果对最左边的$i$操作，就只把$a[i+1]$翻转；如果对最右边的$i$操作，就只把$a[i-1]$翻转。

注意操作不会翻转$a[i]$。

能否把$a$变成$b$？输出YES或NO。

输入样例$1$

2
4
0101
0100
3
000
010

输出样例$1$

YES
NO

输入样例$2$

5
7
0101011
1111010
5
11111
00000
4
1101
1101
6
101010
100100
3
000
000

输出样例$2$

NO
NO
YES
YES
YES

算法

找规律+前缀异或和

智力题，做不了一点。首先原序列是不好考虑的，我们考虑前缀异或序列（这一步就需要经验，有些题目会考虑差分序列等），$s_1$是$a$的前缀异或和数组，$s_2$是$b$的前缀异或和数组。然后发现以下规律，将操作分为两种：

1. 如果选择的$i \gt 1$，则每次操作就相当于交换$s_1[i-1]$和$s_1[i]$，根据冒泡排序的理论，只需要$s_1$和$s_2$中$0$的数量相等即可（$0$的数量相等，长度也相等，因此$1$的数量也相等）。
2. 如果选择了$i=1$进行操作，前面没有$s_1[0]$和$s_1[1]$交换，需要进一步分析。这时候发现如果$a[1]=$1，进行这一步操作就相当于$s_1[1]$不变，$s_1[2:n]$全部异或上$1$（反转）。这时候我们只需要操作前的$s_1$中“$0$的个数加$1$”等于“$s_2$中$1$的个数”即可，这样就能保证操作完后两个前缀异或序列$s_1$和$s_2$中有相同的$0$和$1$。如果$a[1]=$0，那就通过操作$1$（$i \gt 1$的情况）换个$1$到前面来再判断。

复杂度分析

时间复杂度

算法整体就是在统计$s_1$和$s_2$中$0$或$1$的个数，因此线性复杂度就能得到结果，时间复杂度为$O(n)$。

空间复杂度

开辟了前缀异或和的数组$s_1$和$s_2$，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int t, n, s1[N], s2[N];
char a[N], b[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        scanf("%s", a + 1);
        scanf("%s", b + 1);
        for(int i = 1; i <= n; i++) {
            s1[i] = s1[i - 1] ^ (a[i] - '0');
        }
        for(int i = 1; i <= n; i++) {
            s2[i] = s2[i - 1] ^ (b[i] - '0');
        }
        if(count(s1 + 1, s1 + n + 1, 0) == count(s2 + 1, s2 + n + 1, 0)) {
            puts("YES");
        }else if(count(s1 + 1, s1 + n + 1, 0) == n) {
            puts("NO");
        }else if(count(s1 + 1, s1 + n + 1, 0) + 1 == count(s2 + 1, s2 + n + 1, 1)) {
            puts("YES");
        }else {
            puts("NO");
        }
    }
    return 0;
}