← 返回题目列表

Codeforces · 1906/B

B. 按钮按下

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

您有 $$$N$$$ 按钮(编号从 $$$1$$$ 到 $$$N$$$)和 $$$N$$$ 灯(编号从 $$$1$$$ 到 $$$N$$$)。每个灯都可以打开或关闭。最初,如果 $$$A_i = 1$$$,则灯 $$$i$$$ 打开;如果 $$$A_i = 0$$$,则灯关闭。

按钮 $$$i$$$ 连接到灯 $$$i - 1$$$(如果 $$$i > 1$$$)和灯 $$$i + 1$$$(如果 $$$i < N$$$)。仅当灯 $$$i$$$ 亮起时,您才能一次性按下按钮 $$$i$$$。当按下按钮时,连接到该按钮的灯的状态被切换。从形式上来说,如果先前关闭,则灯将打开,如果先前打开,则灯将关闭。请注意,灯 $$$i$$$ 未连接到按钮 $$$i$$$,因此,如果按下按钮 $$$i$$$,灯 $$$i$$$ 的状态不会改变。

零次或多次移动后,如果 $$$B_i = 1$$$,您希望灯 $$$i$$$ 打开,如果 $$$B_i = 0$$$,则关闭。确定是否有可能完成这项任务。

输入

这个问题有多个测试用例。第一行由一个整数 $$$T$$$ ($$$1 \leq T \leq 1000$$$) 组成,表示测试用例的数量。每个测试用例由三行组成。

每个测试用例的第一行由一个整数 $$$N$$$ ($$$3 \le N \le 200\,000$$$) 组成。所有测试用例的 $$$N$$$ 总和不超过 $$$200\,000$$$。

每个测试用例的第二行由长度为 $$$N$$$ 的字符串 $$$A$$$ 组成。 $$$A$$$的每个字符可以是0或1。第$$$i$$$个字符代表灯$$$i$$$的初始状态。

每个测试用例的第三行由长度为 $$$N$$$ 的字符串 $$$A$$$ 组成。 $$$B$$$ 的每个字符可以是 0 或 1。第 $$$i$$$ 个字符表示灯 $$$i$$$ 所需的最终状态。

输出

对于每个测试用例,如果在零次或多次移动后可以达到所有灯的最终状态,则在一行中输出“是”,否则输出“否”。

示例

输入 #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

注意

示例输入/输出 #1 的说明

对于第一个测试用例,依次按下按钮 $$$4, 2, 4, 3, 1, 2$$$,按钮的状态变化为: $$$0101 \rightarrow 0111 \rightarrow 1101 \rightarrow 1111 \rightarrow 1010 \rightarrow 1110 \rightarrow 0100$$$。

对于第二个测试用例,您无法按任何按钮,因此不可能达到最终状态。