310620: CF1861B. Two Binary Strings
Description
You are given two strings $a$ and $b$ of equal length, consisting of only characters 0 and/or 1; both strings start with character 0 and end with character 1.
You can perform the following operation any number of times (possibly zero):
- choose one of the strings and two equal characters in it; then turn all characters between them into those characters.
Formally, you choose one of these two strings (let the chosen string be $s$), then pick two integers $l$ and $r$ such that $1 \le l < r \le |s|$ and $s_l = s_r$, then replace every character $s_i$ such that $l < i < r$ with $s_l$.
For example, if the chosen string is 010101, you can transform it into one of the following strings by applying one operation:
- 000101 if you choose $l = 1$ and $r = 3$;
- 000001 if you choose $l = 1$ and $r = 5$;
- 010001 if you choose $l = 3$ and $r = 5$;
- 010111 if you choose $l = 4$ and $r = 6$;
- 011111 if you choose $l = 2$ and $r = 6$;
- 011101 if you choose $l = 2$ and $r = 4$.
You have to determine if it's possible to make the given strings equal by applying this operation any number of times.
InputThe first line contains a single integer $t$ ($1 \le t \le 2000$) — the number of test cases.
Each test case consists of two lines:
- the first line contains the string $a$ ($2 \le |a| \le 5000$), consisting of only characters 0 and/or 1.
- the second line contains the string $b$ ($2 \le |b| \le 5000$), consisting of only characters 0 and/or 1.
Additional constraints on the input:
- in each test case, $|a| = |b|$ (the strings have equal length);
- in each test case, both strings start with 0 and end with 1;
- the total length of all strings $a$ in all test cases does not exceed $5000$.
For each test case, print YES if it is possible to make the strings equal. Otherwise, print NO. You can print each letter in any register.
ExampleInput7 01010001 01110101 01001 01001 000101 010111 00001 01111 011 001 001001 011011 010001 011011Output
YES YES YES NO NO NO YESNote
In the first test case, we can perform the following operations:
- choose the string $a$, $l = 2$, $r = 4$; after this operation, $a$ is 01110001, $b$ is 01110101;
- choose the string $b$, $l = 5$, $r = 7$; after this operation, $a$ is 01110001, $b$ is 01110001.
In the second test case, the strings are already equal.
In the third test case, we can perform the following operations:
- choose the string $a$, $l = 4$, $r = 6$; after this operation, $a$ is 000111, $b$ is 010111;
- choose the string $b$, $l = 1$, $r = 3$; after this operation, $a$ is 000111, $b$ is 000111;
In the fourth and fifth test cases, it's impossible to make the given strings equal.
Output
给你两个等长的由字符0和1组成的字符串a和b，字符串a和b都以0开始，以1结束。你可以执行以下操作任意次（可能为零次）：选择一个字符串和其中的两个相同的字符，然后将它们之间的所有字符都变成这两个字符。形式上，你选择这两个字符串中的一个（设选中的字符串为s），然后选择两个整数l和r，使得1≤l
输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤2000），表示测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含字符串a（2≤|a|≤5000），由字符0和/或1组成。
- 第二行包含字符串b（2≤|b|≤5000），由字符0和/或1组成。
- 输入的附加限制条件：
- 在每个测试用例中，|a|=|b|（字符串长度相等）；
- 在每个测试用例中，两个字符串都以0开始，以1结束；
- 所有测试用例中所有字符串a的总长度不超过5000。
输出：
- 对于每个测试用例，如果可以使字符串相等，则打印YES。否则，打印NO。你可以以任何大小写打印每个字母。
示例：
输入：
```
7
01010001
01110101
01001
01001
000101
010111
00001
01111
011
001
001001
011011
010001
011011
```
输出：
```
YES
YES
YES
NO
NO
NO
YES
```
注意：
- 在第一个测试用例中，我们可以执行以下操作：
1. 选择字符串a，l=2，r=4；操作后，a是01110001，b是01110101；
2. 选择字符串b，l=5，r=7；操作后，a是01110001，b是01110001。
- 在第二个测试用例中，字符串已经相等。
- 在第三个测试用例中，我们可以执行以下操作：
1. 选择字符串a，l=4，r=6；操作后，a是000111，b是010111；
2. 选择字符串b，l=1，r=3；操作后，a是000111，b是000111。
- 在第四和第五个测试用例中，无法使给定的字符串相等。题目大意： 给你两个等长的由字符0和1组成的字符串a和b，字符串a和b都以0开始，以1结束。你可以执行以下操作任意次（可能为零次）：选择一个字符串和其中的两个相同的字符，然后将它们之间的所有字符都变成这两个字符。形式上，你选择这两个字符串中的一个（设选中的字符串为s），然后选择两个整数l和r，使得1≤l