A14247. Flip the Bits
编程题
普及/提高-
知识点
题目描述
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)?
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$ .
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$ .
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$ .