问题 6316 --兔兔的两个01串

6316: 兔兔的两个01串★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 20  解决: 12
[提交][状态][命题人:]

题目描述

给定两个长度相等且以0开头、以1结尾的01串。可以对任意一个串不限次数的做操作:
1.选择两个下标l,r(要求在串中这两个位置的字符必须相同,即若01串为s,则要求s[l]=s[r])
2.把[l,r]区间内的字符全部替换为与它们相同的字符。
如01串s为010101,则按上面方法操作,可得到如下转换:
若选择l=1,r=3,则操作后原串变为000101;
若选择l=1,r=5,则操作后原串变为000001;
若选择l=3,r=5,则操作后原串变为010001;
若选择l=4,r=6,则操作后原串变为010111;
若选择l=2,r=6,则操作后原串变为011111;
若选择l=2,r=4,则操作后原串变为011101。

现在请你帮忙计算一下,经过若干次操作后两字符串能否相等。

输入

第一整数为T,表示有T (1≤T≤2000)组测试样例。
每组测试样例包含2行,为字符串a与b。字符串a、b都为以0开头、以1结尾的01串。测试数据保证字符串a、b的长度相等且长度不超过5000。

输出

对于每组测试样例,经过若干次操作后两字符串若能相等,则输出YES;否则输出NO。

样例输入
Copy
7
01010001
01110101
01001
01001
000101
010111
00001
01111
011
001
001001
011011
010001
011011
样例输出
Copy
YES
YES
YES
NO
NO
NO
YES

提示

在测试样例1中,可以执行如下操作:
   1. 对字符串a,选择l=2,r=4;操作后串a变为01110001
   2. 对字符串b,选择l=5,r=7;操作后串b变为01110001

在测试样例2中的两个字符串已经相等了。

在测试样例3中,可以执行如下操作:
   1. 对字符串a,选择l=4,r=6;操作后串a变为000111
   2. 对字符串b,选择l=1,r=3;操作后串b变为000111
在测试样例4中的两个字符串无论怎样操作,都无法相等。

来源

[提交][状态]