B. 第2题-石刻暗号

第2题-石刻暗号

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.

题目内容

一位研究员发现了 nn 块从上到下整齐排列的石板,每块石板上刻着一条长度为 mm 的小写字母序列。他想从这些石板中按顺序依次选取若干个字符,每块石板至多选取一个,使得这些字符依次形成暗号 tazige。选取时可以跳过若干块石板。请判断是否存在这样的选取方案。保证 nnmm 均为不超过 1000 的正整数,所有字符均为小写英文字母。

输入描述

第一行包含两个整数 nnmm,分别表示石板数量和每块石板上字母序列的长度。保证 nnmm 均为不超过 1000 的正整数。 接下来 nn 行,每行包含一个长度为 mm 的字符串,依次表示从上到下各块石板上的字母序列。

输出描述

输出 Yes 表示存在选取方案可以形成暗号 tazige,否则输出 No

样例1

输入

6 4
atab
aaba
zabc
ibcd
gdef
eefg

输出

Yes

说明

共有 n=6n=6 块石板,每块长度为 m=4m=4。可以依次选择第 1 块的 t、第 2 块的 a、第 3 块的 z、第 4 块的 i、第 5 块的 g、第 6 块的 e,组成字符串 tazige。因此输出 Yes

样例2

输入

7 2
at
ab
zz
ii
gg
ee
zz

输出

Yes

说明

每块石板上字符串长度为 m=2m=2。可以依次选择第 1 块的 t、第 2 块的 a、第 3 块的 z、第 4 块的 i、第 5 块的 g、第 6 块的 e,跳过第 7 块。这些字符依次组成 tazige,因此输出 Yes

样例3

输入

5 1
t
a
z
i
g

输出

No

说明

暗号 tazige 的长度为 6,而每块石板至多只能选取 1 个字符,所以至少需要 6 块石板。

本样例中只有 n=5n=5 块石板,即使每行都含有目标字符,也无法选够 6 个字符组成暗号,因此输出 No

样例4

输入

6 1
e
g
i
z
a
t

输出

No

说明

6 块石板依次只能提供单个字符 egizat。虽然其中包含了 tazige 的一些字母,但按照从上到下的顺序不能形成 tazige

例如第一块无法提供 t,且无法回到前面继续选取,因此输出 No

秋招模拟赛第37场|2023.09.02-美团

Not Attended
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