5-6 小季的密码

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制:1s
空间限制:256MB

Description

小季想给他的手机设置一个开机密码,但是他不希望别人能打开它,因此他的密码应该尽可能的复杂,对此他想出了以下标准:

  • 密码的长度应该正好是 \(m\) ;
  • 密码应该只由 0 到 9 的数字组成;
  • 密码不能是常用密码(以字符串 \(s\) 给出)中的任意子序列(不一定连续)。

小季还想出了两个长度为 \(m\) 的字符串:\(l\) 和 \(r\) ,都只由 0 到 9 的数字组成。他希望密码中的第 \(i\) 位数字在 \(l_i\) 和 \(r_i\) 之间。

那么是否存在一个符合小季提出的所有标准的密码?

Input Format

第一行包含一个整数 \(t\)(\(1≤t≤10^4\))- 测试用例的数量。

对于每个测试用例:

  • 第一行包含一个字符串 \(s\)( \(1≤|s|≤3⋅10^5\) ),仅由 0 到 9 的数字组成,代表常用密码。
  • 第二行包含一个单一的整数 \(m\)( \(1≤m≤10\) )- 密码长度。
  • 第三行、第四行各包含一个字符串 \(l,r\)( \(|l|=m,|r|=m\) ),仅由 0 到 9 中的数字组成 - 每个数字的下、上限值。

保证所有的 \(l_i \le r_i\) 成立,所有测试案例中 s 的长度之和不超过 \(3⋅10^5\) 。

Output Format

对于每个测试案例,如果存在一个符合所有标准的密码,打印 "YES"。否则打印 "NO"。

Data Range

\(1≤t≤10^4,1≤|s|≤3⋅10^5,1≤m≤10,|l|=m,|r|=m,l_i \le r_i,\sum_{i=1}^{t}len(s_i) \le 3 \times 10^5\) 。

Input Example #1:

5
88005553535123456
2
50
56
123412341234
3
111
444
1234
4
4321
4321
459
2
49
59
00010
2
10
11

Output Example #1:

YES
NO
YES
NO
YES

Note

在第一个测试案例中,小季可以选择密码 "50"。它没有作为子序列出现在\(s\)中。

在第二个测试案例中,所有三个数字的组合,每个数字都是从 \(1\) 到 \(4\) ,符合 \(l\) 和 \(r\) 的标准。然而,它们都作为子序列出现在 \(s\) 中。例如,"314" 出现在 \([3, 5, 12]\) 位,"222" 出现在 \([2, 6, 10]\) 位。

在第三个测试案例中,小季可以选择密码 "4321" 。实际上,这是唯一符合 \(l\) 和 \(r\) 上标准的密码,并且没有作为子序列出现在 \(s\) 中。

在第四个测试案例中,只有 "49" 和 "59" 符合 \(l\) 和 \(r\) 的标准。它们都作为子序列出现在 \(s\) 中。

在第五个测试案例中,小季可以选择密码 "11" 。

2023暑假集训7月10日训练题

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2023-07-10 09:00
结束于
2023-07-10 11:30
持续时间
2.5 小时
主持人
参赛人数
20