Bracket Sequencing

题目描述

A 括号序列 是以下形式之一的字符串：

一个空字符串； 按此顺序连接 $($、$A$ 和 $)$，其中 $A$ 为某个括号序列； 按此顺序连接 $A$ 和 $B$，其中 $A$ 和 $B$ 为某些非空括号序列 /

给出 $N$ 个字符串 $S_i$。是否可以通过以某种顺序连接所有这 $N$ 个字符串来得到一个括号序列？

输入格式

输入以标准输入给出，格式如下： $N$ $S_1$ : $S_N$

输出格式

如果可以通过以某种顺序连接所有这 $N$ 个字符串得到一个括号序列，则输出 $Yes$；否则输出 $No$。

2
)
(()

Yes

2
)(
()

No

4
((()))
((((((
))))))
()()()

Yes

3
(((
)
)

No

提示

$1 \leq N \leq 10^6$ 所有字符串 $S_i$ 的总长度至多为 $10^6$。 $S_i$ 是由 $($ 和 $)$ 构成的非空字符串。将 $(()$ 与 $)$ 按此顺序连接可以得到一个括号序列。

标签: AtCoder|abc167F

来源

AtCoder|abc167F