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 tt (1≤t≤1001\le t\le 100) — the number of test cases. The descriptions of the tt test cases follow.

The first line of each test case contains a string uu (1≤∣u∣≤2001\le |u|\le 200) — the DNA of the weasel.

The second line of each test case contains a string vv (1≤∣v∣≤2001\le |v|\le 200) — the DNA of the basilisk.

The values ∣u∣|u|, ∣v∣|v| denote the lengths of the strings uu and vv. It is guaranteed that both strings uu and vv consist of the letters A, B and C.

每个测试包含多个测试用例。第一行包含一个整数 tt(1≤t≤1001\le t\le 100),表示测试用例的数量。接下来是 tt 个测试用例的描述。

每个测试用例的第一行包含一个字符串 uu(1≤∣u∣≤2001\le |u|\le 200)——雪貂的 DNA 序列。

每个测试用例的第二行包含一个字符串 vv(1≤∣v∣≤2001\le |v|\le 200)——蛇怪的 DNA 序列。

其中 ∣u∣|u|、∣v∣|v| 分别表示字符串 uu 和 vv 的长度。保证字符串 uu 和 vv 均仅由字母 A、B 和 C 组成。

输出格式

For each test case, print YES if there is a sequence of mutations to get from uu to vv and NO otherwise.

对于每个测试用例,如果存在从 uu 到 vv 的一系列突变,则输出 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测评打分。不知道怎么写?

首页