补题 Strong Password

题面翻译

给定一个字符串 $s$，以及两个长度为 $m$ 的字符串 $l,r$。你需要判断是否没有长度为 m 的字符串 $t$ 满足以下要求：

  1. 对于 $1\le i\le n$，$l_i\le t_i\le r_i$。
  2. $t$ 不是 $s$ 的一个子序列。

题目描述

Monocarp finally got the courage to register on ForceCoders. He came up with a handle but is still thinking about the password.

He wants his password to be as strong as possible, so he came up with the following criteria:

  • the length of the password should be exactly $ m $ ;
  • the password should only consist of digits from $ 0 $ to $ 9 $ ;
  • the password should not appear in the password database (given as a string $ s $ ) as a subsequence (not necessarily contiguous).

Monocarp also came up with two strings of length $ m $ : $ l $ and $ r $ , both consisting only of digits from $ 0 $ to $ 9 $ . He wants the $ i $ -th digit of his password to be between $ l_i $ and $ r_i $ , inclusive.

Does there exist a password that fits all criteria?

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases.

The first line of each testcase contains a string $ s $ ( $ 1 \le |s| \le 3 \cdot 10^5 $ ), consisting only of digits from $ 0 $ to $ 9 $ — the password database.

The second line contains a single integer $ m $ ( $ 1 \le m \le 10 $ ) — the required length of the password.

The third line contains a string $ l $ ( $ |l| = m $ ), consisting only of digits from $ 0 $ to $ 9 $ — the lower restriction on each digit.

The fourth line contains a string $ r $ ( $ |r| = m $ ), consisting only of digits from $ 0 $ to $ 9 $ — the upper restriction on each digit. $ l_i \le r_i $ for all $ i $ from $ 1 $ to $ m $ .

The sum of lengths of $ s $ over all testcases doesn’t exceed $ 3 \cdot 10^5 $ .

输出格式

For each testcase, print “YES” if there exists a password that fits all criteria. Print “NO” otherwise.

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
5
88005553535123456
2
50
56
123412341234
3
111
444
1234
4
4321
4321
459
2
49
59
00010
2
10
11

样例输出 #1

1
2
3
4
5
YES
NO
YES
NO
YES

提示

In the first testcase, Monocarp can choose password “50”. It doesn’t appear in $ s $ as a subsequence.

In the second testcase, all combinations of three digits, each of them being from $ 1 $ to $ 4 $ , fit the criteria on $ l $ and $ r $ . However, all of them appear in $ s $ as subsequences. For example, “314” appears at positions $ [3, 5, 12] $ and “222” appears at positions $ [2, 6, 10] $ .

In the third testcase, Monocarp can choose password “4321”. Actually, that is the only password that fits the criteria on $ l $ and $ r $ . Luckily, it doesn’t appear in $ s $ as a subsequence.

In the fourth testcase, only “49” and “59” fit the criteria on $ l $ and $ r $ . Both of them appear in $ s $ as subsequences.

In the fifth testcase, Monocarp can choose password “11”.

题解

题目解析

一道贪心判断子序列的题,我当时确实不会判断子序列,所以这道题我当时没有切掉.不过现在我稍微理解了如何去做这道题.

首先介绍一下判断是否存在子序列的方法,是双指针法,具体方法不是很难,就是 $O(n)$ 的匹配嘛.这道题主要的问题在于贪心:

到底如何才能缩少比较次数呢?

我最后了解到的方法是这样的:

  • 首先我们要确定我们需要干什么

    我们需要从多种密码可能中找到可能的任意一种使得在原数列内不存在子序列.

  • 我们需要构造一个数组使得我们可以快速的找到在每一位下都能找到各个数字在后面出现的位置,以便我们查询

    注意,对于构造这个数列,需要我们从后往前构造,为何呢?

    这就考虑到了贪心了,我们只需要找出到底有没有不是子序列的组合方式,也就是说我们仅需要找到一个就能说明有不存在的.所以我们仅需要从后往前遍历.具体原因我可以拿个例子解释:

    1
    2
    3
    4
    5
    假设原始串是:
    "123123123"
    我需要判断每一个数位,但是每个数位上有多种可能.
    我们只需要找到有数位上匹配的位置最远的那个位置作为下一个数位匹配的地点即可.
    因为我们如果选了前面的数字,其中以不同方式组合成的子序列都会包含选后面的数字进行遍历的子序列.也就是说我们完全可以从后往前贪心.

可能我还是有点说的不是特别清楚,如果再不是很清楚,这是其讲解视频:最小子段和 动态规划【Codeforces EDU 151】_哔哩哔哩_bilibili

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

int m,n;

signed main(){
	T_{
		string s,l,r;
		cin >> s >> m >> l >> r;
		n = s.size();
		vector<array<int,10>> v(n + 1);
		v[n].fill(n);//把最后一个设为n以便判断
		fb(i,n-1,0){
			v[i] = v[i+1];//就是后面继承前面.然后呢后面再在继承的基础上进行修改.
			v[i][s[i] - '0'] = i;
		}
		int left = -1;//可以达到的最左侧的位置,如果超过了原字符串长度-1,则说明有至少一组密码可以不存在子序列里面,
		for(int i=0;i<m&&left<n;i++){
			int next = 0;
			for(int j=l[i]-'0';j<=r[i]-'0';j++){
				next = max(next,v[left+1][j]);//找从left下一位开始并且数字为j的位置
			}
			left = next;
		}
		cout << (left == n?"YES":"NO") << endl;
	}
	return 0;
}