问题 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。
提示
在测试样例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中的两个字符串无论怎样操作,都无法相等。
来源
[提交][状态]