← 返回题目列表

Codeforces · 1861/B

B. 两个二进制字符串

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

给你两个长度相等的字符串 $$$a$$$ 和 $$$b$$$,仅包含字符 0 和/或 1;两个字符串都以字符 0 开头并以字符 1 结尾。

您可以执行以下操作任意次数(可能为零):

- 选择字符串之一和其中两个相等的字符;然后将它们之间的所有字符都转换为这些字符。

正式地,您选择这两个字符串之一(让所选字符串为 $$$s$$$),然后选择两个整数 $$$l$$$ 和 $$$r$$$ 使得 $$$1 \le l < r \le |s|$$$ 和 $$$s_l = s_r$$$,然后替换每个字符 $$$s_i$$$ 使得 $$$l < i < r$$$与$$$s_l$$$。

例如,如果选择的字符串是 010101,则可以通过应用一项操作将其转换为以下字符串之一:

- 000101,如果您选择 $$$l = 1$$$ 且 $$$r = 3$$$;
- 000001,如果您选择 $$$l = 1$$$ 且 $$$r = 5$$$;
- 010001,如果您选择 $$$l = 3$$$ 且 $$$r = 5$$$;
- 010111,如果您选择 $$$l = 4$$$ 且 $$$r = 6$$$;
- 011111,如果您选择 $$$l = 2$$$ 且 $$$r = 6$$$;
- 011101,如果您选择 $$$l = 2$$$ 且 $$$r = 4$$$。

您必须确定是否可以通过多次应用此操作来使给定字符串相等。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2000$$$) — 测试用例的数量。

每个测试用例由两行组成:

- 第一行包含字符串 $$$a$$$ ($$$2 \le |a| \le 5000$$$),仅包含字符 0 和/或 1。
- 第二行包含字符串 $$$b$$$ ($$$2 \le |b| \le 5000$$$),仅包含字符 0 和/或 1。

输入的附加限制:

- 在每个测试用例中,$$$|a| = |b|$$$ (字符串长度相等);
- 在每个测试用例中,两个字符串都以 0 开头并以 1 结尾;
- 所有测试用例中所有字符串$$$a$$$的总长度不超过$$$5000$$$。

输出

对于每个测试用例,如果可以使字符串相等,则打印 YES。否则,打印NO。您可以打印任何寄存器中的每个字母。

示例

输入 #1

7
01010001
01110101
01001
01001
000101
010111
00001
01111
011
001
001001
011011
010001
011011

输出 #1

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;

在第四个和第五个测试用例中,不可能使给定的字符串相等。