分数: 300 点
问题陈述
给你一个字符串 S 长度 N 由小写英文字母组成。判断是否可以分割 S 到两个或多个连续的子字符串中,以便它们严格按字典顺序递增。
准确的说是判断是否存在字符串序列 t=(t_1,t_2,\dots,t_k) 满足以下所有条件。
-
序列的长度 k 至少 2.
-
t_i 不为空。 (1 \le i \le k)
-
连接 t_1,t_2,\dots,t_k 按此顺序会导致 S.
-
t_i 按字典顺序小于 t_{i+1} 对于每个整数 i 这样 1 \le i < k.
你被给予 T 测试用例。找出每个问题的答案。
什么是字典顺序?
一个字符串 S = S_1S_2\ldots S_{|S|} 据说是 按字典顺序较小 比字符串 T = T_1T_2\ldots T_{|T|} 如果下面的 1. 或 2. 成立。 在这里, |S| 和 |T| 代表的长度 S 和 T。
- |S| \lt |T| 和 S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
- 有一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两项成立。
- S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}.
- 角色 S_i 出现在之前 T_i 按字母顺序排列。
约束
- 1 \le T \le 2000
- 2 \le N \le 2000
- S 是一个长度为 N 由小写英文字母组成。
- 总和 N 单个输入中的所有测试用例不超过 2000.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
在这里, \mathrm{case}_i 代表 i- 第一个测试用例。每个测试用例均按以下格式给出:
N S
输出
打印 T 行。
的 i第行 (1 \le i \le T) 应包含 Yes 如果可以划分 S 在 i-第一个测试用例转换为满足条件的子字符串,并且 No 否则。
示例输入 1
5 4 abac 3 cac 2 ab 12 abababababab 5 edcba
示例输出 1
Yes No Yes Yes No
对于第一个测试用例,您可以划分 S 进入 a, ba, c.
对于第二个测试用例,无法划分 S 转换为子字符串,以便它们严格按字典顺序递增。