B. 第2题-石刻暗号
第2题-石刻暗号
秋招模拟赛第37场|2023.09.02-美团
- Status
- Done
- Rule
- IOI
- Problem
- 5
- Start at
- 2023-9-4 19:00
- End at
- 2023-9-4 21:00
- Duration
- 2 hour(s)
- Host
- Partic.
- 42
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
一个指针指向 s = "future" 这个字符串的下标 idx,初始从 0 开始。
按字符串输入的顺序来枚举每个输入的字符串,这个字符串中存在 s[idx] 这个字符,则 idx++ ,否则继续枚举下一个字符串。
如果 idx==6,即 s 这个串的所有字符都可以在输入的字符串中按输入顺序在每个字符串中找到一个对应字符,那么就说明可以找到这么一个子序列,否则遍历完所有输入的字符串,idx 仍然小于 6 ,说明找不到。
时间复杂度:O(nm)
一位研究员发现了 n 块从上到下整齐排列的石板,每块石板上刻着一条长度为 m 的小写字母序列。他想从这些石板中按顺序依次选取若干个字符,每块石板至多选取一个,使得这些字符依次形成暗号 tazige。选取时可以跳过若干块石板。请判断是否存在这样的选取方案。保证 n 和 m 均为不超过 1000 的正整数,所有字符均为小写英文字母。
第一行包含两个整数 n 和 m,分别表示石板数量和每块石板上字母序列的长度。保证 n 和 m 均为不超过 1000 的正整数。
接下来 n 行,每行包含一个长度为 m 的字符串,依次表示从上到下各块石板上的字母序列。
输出 Yes 表示存在选取方案可以形成暗号 tazige,否则输出 No。
输入
6 4
atab
aaba
zabc
ibcd
gdef
eefg
输出
Yes
说明
共有 n=6 块石板,每块长度为 m=4。可以依次选择第 1 块的 t、第 2 块的 a、第 3 块的 z、第 4 块的 i、第 5 块的 g、第 6 块的 e,组成字符串 tazige。因此输出 Yes。
输入
7 2
at
ab
zz
ii
gg
ee
zz
输出
Yes
说明
每块石板上字符串长度为 m=2。可以依次选择第 1 块的 t、第 2 块的 a、第 3 块的 z、第 4 块的 i、第 5 块的 g、第 6 块的 e,跳过第 7 块。这些字符依次组成 tazige,因此输出 Yes。
输入
5 1
t
a
z
i
g
输出
No
说明
暗号 tazige 的长度为 6,而每块石板至多只能选取 1 个字符,所以至少需要 6 块石板。
本样例中只有 n=5 块石板,即使每行都含有目标字符,也无法选够 6 个字符组成暗号,因此输出 No。
输入
6 1
e
g
i
z
a
t
输出
No
说明
这 6 块石板依次只能提供单个字符 e、g、i、z、a、t。虽然其中包含了 tazige 的一些字母,但按照从上到下的顺序不能形成 tazige。
例如第一块无法提供 t,且无法回到前面继续选取,因此输出 No。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册