#17952. 密码锁

密码锁

题目背景

这天由于保安的疏忽大意,蒙自一中的大门被锁住了。

门是用密码锁锁住的,遗憾的是没有人知道密码是多少。

现在要强的 five_rice_water 站了出来,输入了一串密码。

但愿他能把门打开。

题目描述

现在 five_rice_water 输入了一个密码序列 aa, 真实的密码序列是 bb,保证 len(a)len(b)len(a) \ge len(b),其中 len(a)len(a) 表示序列 aa 的长度,len(b)len(b) 表示序列 bb 的长度。

密码锁监测密码的规则是,当且仅当输入的 aa 序列有一个子序列bb,此时密码锁就会打开。

一个序列的子序列的定义是:若序列 xx 可以通过删除某些数变成 yy 序列,此时就说明序列 yy 是序列 xx 的子序列。

简化题意:给定两个序列 a,ba,b,请你判断 bb 序列是不是 aa 序列的子序列

如果 bb 序列是 aa 序列的子序列,输出 Yes,否则输出 No

Tips:本题采用捆绑测试,所以如果你单纯的输出 Yes 或者 No,得分可能会比你想象的少得多。

输入格式

输入第一行两个整数 n,mn,m,分别表示序列 aa 和序列 bb 的长度。

接下来一行 nn 个整数,表示输入的密码序列 aa

接下来一行 mm 个整数,表示原本真实的密码序列 bb

输出格式

如果 bbaa 的子序列,那么输出 Yes,否则输出No

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

样例解释

对于样例1,可以在序列 aa 中删除 2,42,4 位置的数,得到序列 bb

对于样例4,可以在序列 aa 中删除 2,3,72,3,7 位置的数,得到序列 bb

对于样例 2,32,3 ,可以证明没有删除数字的方案,使得 aa 序列在删除某些数字以后变成序列 bb

数据范围

对于 10%10\% 的数据,保证最终大门成功打开。

对于另外 20%20\% 的数据,保证 n=mn=m

对于另外 20%20\% 的数据,保证 1n,m51\le n,m\le 5

对于 100%100\% 的数据,保证 1n,m2×105,0密码序列的数字91\le n,m \le 2\times 10^5, 0\le 密码序列的数字 \le 9nmn\ge m