题目详情题解（0）讨论（0）提交记录（0）

AT_xmascon19_j.Sub-Post Correspondence Problem

通过率：0%

AC君温馨提醒

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

题目描述

有 NN 种各 201920192019^{2019} 张的卡片。

第 ii 种卡片的上侧印有字符串 AiA_i，下侧印有字符串 BiB_i。

现在，从这些卡片中选择至少一张卡并按任意顺序排列成一列。排列后，上侧字符串连接成一个整体形成字符串 ss，下侧字符串连接成另一个整体形成字符串 tt。

请问，是否可以通过选择和排列卡片，使得可以通过删除 ss 的任意字符来使其变成 tt？

输入格式

第一行输入一个整数 NN。
接下来的 NN 行中，每行包含两个字符串 AiA_i 和 BiB_i。

输出格式

如果可以满足条件地选择并排列卡片，输出 YES；否则，输出 NO。

输入输出样例

  • 输入#1

    2
cab ac
acba ab

    输出#1

    YES

  • 输入#2

    1
xmas contest

    输出#2

    NO

说明/提示

  • 1≤N≤161 \leq N \leq 16。
  • 1≤∣Ai∣,∣Bi∣≤1051 \leq |A_i|, |B_i| \leq 10^5。
  • AiA_i 和 BiB_i 仅由小写字母组成。

样例解释

例如，按第 2 种、再第 2 种、最后第 1 种的顺序排列卡片，得到 $s = $acbaacbacab 和 $t = $ababac，满足题目条件。

本翻译由 AI 自动生成

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

首页