AT_abc259_c.[ABC259C] XX to XXX

普及-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

给定两个由小写英文字母组成的字符串 SS 和 TT。请判断是否可以通过任意次数(可以为 00 次)的如下操作,将 SS 变为 TT。

在 SS 中,任选一处有两个相同字符连续出现的位置,在这两个字符之间插入一个相同的字符。即,操作包含以下三个步骤:

  1. 设当前 SS 的长度为 NN,记 S=S1S2…SNS = S_1S_2\ldots S_N。
  2. 选择一个满足 1≤i≤N−11 \leq i \leq N-1 且 Si=Si+1S_i = S_{i+1} 的整数 ii。(如果不存在这样的 ii,则跳过步骤 3,操作结束。)
  3. 在 SS 的第 ii 个字符和第 i+1i+1 个字符之间插入一个字符 Si(=Si+1)S_i(=S_{i+1})。操作后,SS 变为长度为 N+1N+1 的字符串 S1S2…SiSiSi+1…SNS_1S_2\ldots S_iS_iS_{i+1}\ldots S_N。

输入格式

输入以以下格式从标准输入读入。

SS TT

输出格式

如果可以将 SS 变为 TT,输出 Yes;否则输出 No。请注意,判题时严格区分大小写。

输入输出样例

  • 输入#1

    abbaac
    abbbbaaac

    输出#1

    Yes
  • 输入#2

    xyzz
    xyyzz

    输出#2

    No

说明/提示

限制条件

  • SS 和 TT 均为长度在 22 到 2×1052 \times 10^5 之间的仅包含小写英文字母的字符串。

样例解释 1

通过以下 33 次操作,可以将 $S = $ abbaac 变为 $T = $ abbbbaaac。

  • 首先,在 SS 的第 22 个和第 33 个字符之间插入 b,得到 $S = $ abbbaac。
  • 接着,再次在 SS 的第 22 个和第 33 个字符之间插入 b,得到 $S = $ abbbbaac。
  • 最后,在 SS 的第 66 个和第 77 个字符之间插入 a,得到 $S = $ abbbbaaac。
    因此,输出 Yes。

样例解释 2

无论如何操作,都无法将 $S = $ xyzz 变为 $T = $ xyyzz。因此,输出 No。

由 ChatGPT 4.1 翻译

输入解题思路,AI测评打分。不知道怎么写?

首页