开始: 2024-10-25 15:00:00

(24-25赛季)稠州常规赛11

结束: 2024-10-26 00:00:00
当前  2025-01-24 14:05:34  类型: IOI  状态: 已经结束 

P1. 字符串问题scope
描述

假设有一个字符串,只包含 `(`,`)`和小写字母。如果通过以下步骤,能使字符串为空,则称这个字符串为好的:

- 删除所有小写字母

- 不停地删除连续的`()`


给定一个好的字符串 S。字符串中所有的小写字母对应一个小球。此外,我们有一个箱子。

一个人按照 1,2,3,\cdots,|S| 的顺序取球:

- 如果 S_i 为`(`,什么也不做。

- 如果 S_i 为小写字母,就将这个小球放入箱子中。如果这个小球已经出现在箱子中,他会晕倒

- 如果 S_i 为`)`,取小于 i 的最大的 j,使 S_i \sim S_j 这个子串是好的。将 ji 操作中放入的小球全部取出。

在这个过程中,如果他晕倒了,输出`No`。否则输出`Yes`。


输入

输入一个好字符串

输出

如果他晕倒了,输出`No`。否则输出`Yes`。

样例

输入

((a)ba)

输出

Yes
提示

- 1 \leq |S| \leq 3 \times 10^5

- S 是一个好字符串。

\### 约束条件 - 1 \\leq |S| \\leq 3 \\times 10^5 S 是好字符串。- S 是一个好字符串。

样例1解释:

对于 i = 1 ,他什么也没做。  

对于 i = 2 ,他什么也不做。  

对于 i = 3 ,他将写有 "a "的球放入方框。  

对于 i = 4j=2的左括号 是小于 4 的最大序号,因此他从盒子里拿出写有 "a "的球。  

对于 i = 5 ,他将写有 "b "的球放入盒子中。  

对于 i = 6 ,他将写有 "a "的球放入盒子中。  

对于 i = 7j=1 的左括号 是小于 7 的最大序号,以他从盒子里拿出写有 "a "的球和另一个写有 "b "的球。

所以输出"Yes"


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交