#TCA2. 项链调色

    ID: 5683 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>贪心字符串模拟教师测试算法组哈希普及−数组排序

项链调色

题目描述

魔法学院开设了一项魔法训练课程,学员可通过学习掌握一种魔法,能够将任意一条项链转换为另一条项链。

项链由 nn 颗各种颜色的珠子串联而成,珠子的顺序可以自由调整。魔法的效果与限制如下:

  • 你可以施展若干次魔法
  • 每次魔法可以把项链中 所有颜色为 xx 的珠子变成颜色 yy
  • 但作为代价,项链中 所有颜色为 yy 的珠子也会同时变成颜色 xx

现在给定:

  • 一条 目标项链
  • 以及需要施展魔法的 kk初始项链

对于每一条初始项链,判断是否可以通过 若干次魔法施展 将其转换为目标项链。若可以,输出 Yes;否则输出 No

输入格式

第一行包含两个整数 nnkk
第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n,表示目标项链中每颗珠子的颜色,保证按从小到大排序。
接下来 kk 行,每行包含 nn 个整数 b1,b2,,bnb_1, b_2, \dots, b_n,表示一条初始项链中每颗珠子的颜色,保证按从小到大排序。

输出格式

kk 行,每行输出 YesNo,第 ii 行表示第 ii 条初始项链是否可以转换为目标项链。

样例

6 3
1 2 2 3 4 7
1 2 2 3 4 7
1 2 3 4 6 6
1 2 2 3 4 7
Yes
No
Yes

样例解释
目标项链的颜色为 1,2,2,3,4,71,2,2,3,4,7

  • 第一条初始项链与目标项链完全相同,可直接(通过 00 次魔法)转换,输出 Yes
  • 第二条初始项链的颜色为 1,2,3,4,6,61,2,3,4,6,6,无论怎样交换颜色,都无法得到目标项链的颜色分布(缺少 77,多出 66),输出 No
  • 第三条初始项链与目标项链相同,输出 Yes

数据范围与提示

  • 5n1005 \le n \le 100
  • 2k72 \le k \le 7
  • 对于 50%50\% 的数据:0ai,bi1000 \le a_i, b_i \le 100
  • 对于 100%100\% 的数据:0ai,bi1090 \le a_i, b_i \le 10^9