← 返回题目列表

Codeforces · 1504/B

B. 翻转位

中文机器翻译题面 查看原题

有一个长度为$$$n$$$的二进制字符串$$$a$$$。在一次操作中,您可以选择具有相同数量的 $$$0$$$ 和 $$$1$$$ 符号的任何 $$$a$$$ 前缀。然后前缀中的所有符号都会反转:每个 $$$0$$$ 变为 $$$1$$$,每个 $$$1$$$ 变为 $$$0$$$。

例如,假设 $$$a=0111010000$$$。

- 在第一个操作中,我们可以选择长度为 $$$8$$$ 的前缀,因为它有四个 $$$0$$$ 和四个 $$$1$$$:$$$[01110100]00\to [10001011]00$$$。
- 在第二个操作中,我们可以选择长度为 $$$2$$$ 的前缀,因为它有一个 $$$0$$$ 和一个 $$$1$$$:$$$[10]00101100\to [01]00101100$$$。
- 第三个操作选择长度为$$$4$$$的前缀是非法的,因为它有三个$$$0$$$和一个$$$1$$$。

你能使用一些有限次数的操作(可能没有)将字符串 $$$a$$$ 转换为字符串 $$$b$$$ 吗?

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 3\cdot 10^5$$$) — 字符串 $$$a$$$ 和 $$$b$$$ 的长度。

下面两行包含长度为$$$n$$$的字符串$$$a$$$和$$$b$$$,由符号$$$0$$$和$$$1$$$组成。

所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot 10^5$$$。

输出

对于每个测试用例,如果可以将 $$$a$$$ 转换为 $$$b$$$,则输出“YES”,如果不可能,则输出“NO”。您可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

5
10
0111010000
0100101100
4
0000
0000
3
001
000
12
010101010101
100110011010
6
000111
110100

输出 #1

YES
YES
NO
YES
NO

注意

第一个测试用例如语句中所示。

在第二个测试用例中,我们使用零运算将 $$$a$$$ 转换为 $$$b$$$。

在第三个测试用例中,没有合法的操作,因此无法将$$$a$$$转换为$$$b$$$。

在第四个测试用例中,这是一个这样的转换:

- 选择长度 $$$2$$$ 前缀以获得 $$$100101010101$$$。
- 选择长度 $$$12$$$ 前缀以获取 $$$011010101010$$$。
- 选择长度 $$$8$$$ 前缀以获得 $$$100101011010$$$。
- 选择长度 $$$4$$$ 前缀以获取 $$$011001011010$$$。
- 选择长度 $$$6$$$ 前缀以获得 $$$100110011010$$$。

在第五个测试用例中,唯一合法的操作是将 $$$a$$$ 转换为 $$$111000$$$。从那里开始,唯一合法的操作是返回到我们开始的字符串,因此我们无法将 $$$a$$$ 转换为 $$$b$$$。