308343: CF1504B. Flip the Bits

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Flip the Bits

题意翻译

有长度为 $n$ 的两个 01 字符串 $a$ 和 $b$。如果对于一个 $i$,$a$ 的区间 $[1,i]$ 中,$0$ 的数量等于 $1$ 的数量,则你可以将这个区间的所有 $1$ 变成 $0$,$0$ 变成 $1$。求是否可以将 $a$ 变成 $b$。

题目描述

There is a binary string $ a $ of length $ n $ . In one operation, you can select any prefix of $ a $ with an equal number of $ 0 $ and $ 1 $ symbols. Then all symbols in the prefix are inverted: each $ 0 $ becomes $ 1 $ and each $ 1 $ becomes $ 0 $ . For example, suppose $ a=0111010000 $ . - In the first operation, we can select the prefix of length $ 8 $ since it has four $ 0 $ 's and four $ 1 $ 's: $ [01110100]00\to [10001011]00 $ . - In the second operation, we can select the prefix of length $ 2 $ since it has one $ 0 $ and one $ 1 $ : $ [10]00101100\to [01]00101100 $ . - It is illegal to select the prefix of length $ 4 $ for the third operation, because it has three $ 0 $ 's and one $ 1 $ . Can you transform the string $ a $ into the string $ b $ using some finite number of operations (possibly, none)?

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1\le t\le 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1\le n\le 3\cdot 10^5 $ ) — the length of the strings $ a $ and $ b $ . The following two lines contain strings $ a $ and $ b $ of length $ n $ , consisting of symbols $ 0 $ and $ 1 $ . The sum of $ n $ across all test cases does not exceed $ 3\cdot 10^5 $ .

输出格式


For each test case, output "YES" if it is possible to transform $ a $ into $ b $ , or "NO" if it is impossible. You can print each letter in any case (upper or lower).

输入输出样例

输入样例 #1

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

输出样例 #1

YES
YES
NO
YES
NO

说明

The first test case is shown in the statement. In the second test case, we transform $ a $ into $ b $ by using zero operations. In the third test case, there is no legal operation, so it is impossible to transform $ a $ into $ b $ . In the fourth test case, here is one such transformation: - Select the length $ 2 $ prefix to get $ 100101010101 $ . - Select the length $ 12 $ prefix to get $ 011010101010 $ . - Select the length $ 8 $ prefix to get $ 100101011010 $ . - Select the length $ 4 $ prefix to get $ 011001011010 $ . - Select the length $ 6 $ prefix to get $ 100110011010 $ . In the fifth test case, the only legal operation is to transform $ a $ into $ 111000 $ . From there, the only legal operation is to return to the string we started with, so we cannot transform $ a $ into $ b $ .

Input

题意翻译

有长度为 $n$ 的两个 01 字符串 $a$ 和 $b$。如果对于一个 $i$,$a$ 的区间 $[1,i]$ 中,$0$ 的数量等于 $1$ 的数量,则你可以将这个区间的所有 $1$ 变成 $0$,$0$ 变成 $1$。求是否可以将 $a$ 变成 $b$。

加入题单

算法标签: