CF1662D.Evolution of Weasels
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
A wild basilisk just appeared at your doorstep. You are not entirely sure what a basilisk is and you wonder whether it evolved from your favorite animal, the weasel.
How can you find out whether basilisks evolved from weasels? Certainly, a good first step is to sequence both of their DNAs. Then you can try to check whether there is a sequence of possible mutations from the DNA of the weasel to the DNA of the basilisk.
Your friend Ron is a talented alchemist and has studied DNA sequences in many of his experiments. He has found out that DNA strings consist of the letters A, B and C and that single mutations can only remove or add substrings at any position in the string (a substring is a contiguous sequence of characters). The substrings that can be removed or added by a mutation are AA, BB, CC, ABAB or BCBC. During a sequence of mutations a DNA string may even become empty.
Ron has agreed to sequence the DNA of the weasel and the basilisk for you, but finding out whether there is a sequence of possible mutations that leads from one to the other is too difficult for him, so you have to do it on your own.
一只野生的蛇怪突然出现在你家门口。你并不完全清楚蛇怪是什么,于是开始怀疑它是否由你最喜爱的动物——黄鼠狼进化而来。
你该如何确定蛇怪是否由黄鼠狼进化而来呢?显然,一个良好的第一步是分别测定两者的DNA序列。接着,你可以尝试判断:是否存在一连串可能发生的突变,能将黄鼠狼的DNA序列转变为蛇怪的DNA序列?
你的朋友罗恩是一位才华横溢的炼金术士,他在许多实验中研究过DNA序列。他发现:DNA字符串仅由字母 A、B 和 C 构成;而单次突变仅允许在字符串的任意位置插入或删除某个子串(子串指一串连续的字符)。允许被插入或删除的子串为:AA、BB、CC、ABAB 或 BCBC。在一系列突变过程中,DNA字符串甚至可能变为空串。
罗恩已答应为你测定黄鼠狼和蛇怪的DNA序列,但判断二者之间是否存在可行的突变序列对他而言过于困难,因此这项任务只能由你自己来完成。
输入格式
Each test contains multiple test cases. The first line contains an integer t (1≤t≤100) — the number of test cases. The descriptions of the t test cases follow.
The first line of each test case contains a string u (1≤∣u∣≤200) — the DNA of the weasel.
The second line of each test case contains a string v (1≤∣v∣≤200) — the DNA of the basilisk.
The values ∣u∣, ∣v∣ denote the lengths of the strings u and v. It is guaranteed that both strings u and v consist of the letters A, B and C.
每个测试包含多个测试用例。第一行包含一个整数 t(1≤t≤100),表示测试用例的数量。接下来是 t 个测试用例的描述。
每个测试用例的第一行包含一个字符串 u(1≤∣u∣≤200)——雪貂的 DNA 序列。
每个测试用例的第二行包含一个字符串 v(1≤∣v∣≤200)——蛇怪的 DNA 序列。
其中 ∣u∣、∣v∣ 分别表示字符串 u 和 v 的长度。保证字符串 u 和 v 均仅由字母 A、B 和 C 组成。
输出格式
For each test case, print YES if there is a sequence of mutations to get from u to v and NO otherwise.
对于每个测试用例,如果存在从 u 到 v 的一系列突变,则输出 YES;否则输出 NO。
输入输出样例
输入#1
8 A B B C C A AA BB BB CC CC AA ABAB BCBC ABC CBA
输出#1
NO NO NO YES YES YES YES NO
输入解题思路,AI测评打分。不知道怎么写?