← 返回题目列表

AtCoder · arc163_a

A. 分割字符串

中文机器翻译题面 查看原题

分数: 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。

  1. |S| \lt |T| 和 S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
  2. 有一个整数 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 转换为子字符串,以便它们严格按字典顺序递增。