309593: CF1704A. Two 0-1 Sequences
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Two 0-1 Sequences
题意翻译
### 题目描述 你有两个 $01$ 串 $a$ 和 $b$，每次你可以对 $a$ 串进行以下两种操作（以下 $a_1$ 表示 $a$ 现在的第一个字符，$a_2$ 表示 $a$ 现在的第二个字符，以此类推）： 1. 若 $|a| \geq 2$，则可将 $a_2$ 改为 $\min(a_1,a_2)$，然后删除 $a_1$。 2. 若 $|a| \geq 2$，则可将 $a_2$ 改为 $\max(a_1,a_2)$，然后删除 $a_1$。 显然，删除 $a_1$ 后，原先的 $a_2$ 变成 $a_1$，$a_3$ 变成 $a_2$，$a$ 的长度减少 $1$。 试判断 $a$ 是否能够经过若干次操作（也可以不进行操作）变成 $b$。 ### 输入格式 第一行一个正整数 $t$（$1 \leq t \leq 2000$），表示测试数据的组数。接下来每组数据三行： - 第一行，两个正整数 $n$ 和 $m$，表示 $a$ 和 $b$ 的长度。保证 $1 \leq m \leq n \leq 50$。 - 第二行一个 $01$ 串 $a$。 - 第三行一个 $01$ 串 $b$。 ### 输出格式 输出共 $t$ 行，每行一个字符串 ``YES`` 或 ``NO``（大小写不敏感），表示 $a$ 能否变成 $b$。 ### 样例解释 - 第一组样例：对 $a$ 不断进行操作 $2$ 即可。 - 第二组样例：对 $a$ 不断进行操作 $1$ 即可。 - 第三、四组样例：显然，无论如何对 $a$ 进行操作都无法使其变成 $b$。 - 第五组样例：虽然可以用操作 $2$ 使 $a$ 变成 $10101$（这与 $b$ 的第一个字符相同），但显然，无论如何对 $a$ 进行操作都无法使其变成 $b$。题目描述
AquaMoon has two binary sequences $ a $ and $ b $ , which contain only $ 0 $ and $ 1 $ . AquaMoon can perform the following two operations any number of times ( $ a_1 $ is the first element of $ a $ , $ a_2 $ is the second element of $ a $ , and so on): - Operation 1: if $ a $ contains at least two elements, change $ a_2 $ to $ \operatorname{min}(a_1,a_2) $ , and remove the first element of $ a $ . - Operation 2: if $ a $ contains at least two elements, change $ a_2 $ to $ \operatorname{max}(a_1,a_2) $ , and remove the first element of $ a $ . Note that after a removal of the first element of $ a $ , the former $ a_2 $ becomes the first element of $ a $ , the former $ a_3 $ becomes the second element of $ a $ and so on, and the length of $ a $ reduces by one. Determine if AquaMoon can make $ a $ equal to $ b $ by using these operations.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 2\,000 $ ) — the number of test cases. Description of test cases follows. The first line of each test case contains two integers $ n $ , $ m $ ( $ 1 \leq n,m \leq 50 $ , $ m \leq n $ ) — the lengths of $ a $ and $ b $ respectively. The second line of each test case contains a string $ a $ of length $ n $ , consisting only $ 0 $ and $ 1 $ . The third line of each test case contains a string $ b $ of length $ m $ , consisting only $ 0 $ and $ 1 $ .
输出格式
For each test case, output "YES" if AquaMoon can change $ a $ to $ b $ by using these options; otherwise, output "NO". You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as a positive answer).
输入输出样例
输入样例 #1
10
6 2
001001
11
6 2
110111
01
6 2
000001
11
6 2
111111
01
8 5
10000101
11010
7 4
1010001
1001
8 6
01010010
010010
8 4
01010101
1001
8 4
10101010
0110
7 5
1011100
11100输出样例 #1
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES说明
In the first test case, you can use Operation 2 four times to make $ a $ equals to $ b $ . In the second test case, you can use Operation 1 four times to make $ a $ equals to $ b $ . In the third test case, it can be proved that no matter how we use the operations, it is impossible to make $ a $ equal to $ b $ . In the fourth test case, it can be proved that no matter how we use the operations, it is impossible to make $ a $ equal to $ b $ . In the fifth test case, you can use Operation 2 three times to make $ a $ become $ 10101 $ , so the first element of $ a $ equals to the first element of $ b $ , but it can be proved that no matter how to operate, the second to the fifth elements of $ a $ can't be the same as $ b $ .Input
题意翻译
### 题目描述 你有两个 $01$ 串 $a$ 和 $b$，每次你可以对 $a$ 串进行以下两种操作（以下 $a_1$ 表示 $a$ 现在的第一个字符，$a_2$ 表示 $a$ 现在的第二个字符，以此类推）： 1. 若 $|a| \geq 2$，则可将 $a_2$ 改为 $\min(a_1,a_2)$，然后删除 $a_1$。 2. 若 $|a| \geq 2$，则可将 $a_2$ 改为 $\max(a_1,a_2)$，然后删除 $a_1$。 显然，删除 $a_1$ 后，原先的 $a_2$ 变成 $a_1$，$a_3$ 变成 $a_2$，$a$ 的长度减少 $1$。 试判断 $a$ 是否能够经过若干次操作（也可以不进行操作）变成 $b$。 ### 输入格式 第一行一个正整数 $t$（$1 \leq t \leq 2000$），表示测试数据的组数。接下来每组数据三行： - 第一行，两个正整数 $n$ 和 $m$，表示 $a$ 和 $b$ 的长度。保证 $1 \leq m \leq n \leq 50$。 - 第二行一个 $01$ 串 $a$。 - 第三行一个 $01$ 串 $b$。 ### 输出格式 输出共 $t$ 行，每行一个字符串 ``YES`` 或 ``NO``（大小写不敏感），表示 $a$ 能否变成 $b$。 ### 样例解释 - 第一组样例：对 $a$ 不断进行操作 $2$ 即可。 - 第二组样例：对 $a$ 不断进行操作 $1$ 即可。 - 第三、四组样例：显然，无论如何对 $a$ 进行操作都无法使其变成 $b$。 - 第五组样例：虽然可以用操作 $2$ 使 $a$ 变成 $10101$（这与 $b$ 的第一个字符相同），但显然，无论如何对 $a$ 进行操作都无法使其变成 $b$。Output
**题目大意**：
给定两个仅包含0和1的序列$a$和$b$，可以对序列$a$执行以下两种操作任意次数：
1. 如果$a$至少有两个元素，则将$a_2$改为$\min(a_1,a_2)$，然后移除$a_1$。
2. 如果$a$至少有两个元素，则将$a_2$改为$\max(a_1,a_2)$，然后移除$a_1$。
每次移除第一个元素后，原序列中后续元素前移，$a$的长度减一。
需要判断通过上述操作能否使序列$a$变为$b$。
**输入输出数据格式**：
**输入格式**：
- 第一行一个正整数$t$（$1 \leq t \leq 2000$），表示测试数据的组数。
- 每组数据三行：
- 第一行，两个正整数$n$和$m$，表示$a$和$b$的长度。保证$1 \leq m \leq n \leq 50$。
- 第二行一个01串$a$。
- 第三行一个01串$b$。
**输出格式**：
- 输出共$t$行，每行一个字符串``YES``或``NO``（大小写不敏感），表示$a$能否变成$b$。
**样例解释**：
- 第一组样例：对$a$不断进行操作$2$即可。
- 第二组样例：对$a$不断进行操作$1$即可。
- 第三、四组样例：显然，无论如何对$a$进行操作都无法使其变成$b$。
- 第五组样例：虽然可以用操作$2$使$a$变成$10101$（这与$b$的第一个字符相同），但显然，无论如何对$a$进行操作都无法使其变成$b$。**题目大意**： 给定两个仅包含0和1的序列$a$和$b$，可以对序列$a$执行以下两种操作任意次数： 1. 如果$a$至少有两个元素，则将$a_2$改为$\min(a_1,a_2)$，然后移除$a_1$。 2. 如果$a$至少有两个元素，则将$a_2$改为$\max(a_1,a_2)$，然后移除$a_1$。 每次移除第一个元素后，原序列中后续元素前移，$a$的长度减一。 需要判断通过上述操作能否使序列$a$变为$b$。 **输入输出数据格式**： **输入格式**： - 第一行一个正整数$t$（$1 \leq t \leq 2000$），表示测试数据的组数。 - 每组数据三行： - 第一行，两个正整数$n$和$m$，表示$a$和$b$的长度。保证$1 \leq m \leq n \leq 50$。 - 第二行一个01串$a$。 - 第三行一个01串$b$。 **输出格式**： - 输出共$t$行，每行一个字符串``YES``或``NO``（大小写不敏感），表示$a$能否变成$b$。 **样例解释**： - 第一组样例：对$a$不断进行操作$2$即可。 - 第二组样例：对$a$不断进行操作$1$即可。 - 第三、四组样例：显然，无论如何对$a$进行操作都无法使其变成$b$。 - 第五组样例：虽然可以用操作$2$使$a$变成$10101$（这与$b$的第一个字符相同），但显然，无论如何对$a$进行操作都无法使其变成$b$。
给定两个仅包含0和1的序列$a$和$b$，可以对序列$a$执行以下两种操作任意次数：
1. 如果$a$至少有两个元素，则将$a_2$改为$\min(a_1,a_2)$，然后移除$a_1$。
2. 如果$a$至少有两个元素，则将$a_2$改为$\max(a_1,a_2)$，然后移除$a_1$。
每次移除第一个元素后，原序列中后续元素前移，$a$的长度减一。
需要判断通过上述操作能否使序列$a$变为$b$。
**输入输出数据格式**：
**输入格式**：
- 第一行一个正整数$t$（$1 \leq t \leq 2000$），表示测试数据的组数。
- 每组数据三行：
- 第一行，两个正整数$n$和$m$，表示$a$和$b$的长度。保证$1 \leq m \leq n \leq 50$。
- 第二行一个01串$a$。
- 第三行一个01串$b$。
**输出格式**：
- 输出共$t$行，每行一个字符串``YES``或``NO``（大小写不敏感），表示$a$能否变成$b$。
**样例解释**：
- 第一组样例：对$a$不断进行操作$2$即可。
- 第二组样例：对$a$不断进行操作$1$即可。
- 第三、四组样例：显然，无论如何对$a$进行操作都无法使其变成$b$。
- 第五组样例：虽然可以用操作$2$使$a$变成$10101$（这与$b$的第一个字符相同），但显然，无论如何对$a$进行操作都无法使其变成$b$。**题目大意**： 给定两个仅包含0和1的序列$a$和$b$，可以对序列$a$执行以下两种操作任意次数： 1. 如果$a$至少有两个元素，则将$a_2$改为$\min(a_1,a_2)$，然后移除$a_1$。 2. 如果$a$至少有两个元素，则将$a_2$改为$\max(a_1,a_2)$，然后移除$a_1$。 每次移除第一个元素后，原序列中后续元素前移，$a$的长度减一。 需要判断通过上述操作能否使序列$a$变为$b$。 **输入输出数据格式**： **输入格式**： - 第一行一个正整数$t$（$1 \leq t \leq 2000$），表示测试数据的组数。 - 每组数据三行： - 第一行，两个正整数$n$和$m$，表示$a$和$b$的长度。保证$1 \leq m \leq n \leq 50$。 - 第二行一个01串$a$。 - 第三行一个01串$b$。 **输出格式**： - 输出共$t$行，每行一个字符串``YES``或``NO``（大小写不敏感），表示$a$能否变成$b$。 **样例解释**： - 第一组样例：对$a$不断进行操作$2$即可。 - 第二组样例：对$a$不断进行操作$1$即可。 - 第三、四组样例：显然，无论如何对$a$进行操作都无法使其变成$b$。 - 第五组样例：虽然可以用操作$2$使$a$变成$10101$（这与$b$的第一个字符相同），但显然，无论如何对$a$进行操作都无法使其变成$b$。