A5884. 「CEOI2016」匹配
编程题
省选/NOI-
知识点
题目描述
**译自 [CEOI2016](http://www.ceoi2016.ro/) Day2 T1「[Match](http://ceoi.inf.elte.hu/probarch/16/match-statement.pdf)」**
我们定义一个合法的括号序列是如下之一：
- 一个空串；
- 串
-
令 $B$ 是一个长度为 $N$ 的合法括号序列。定义 $B_i$ 是序列 $B$ 中第 $i$ 个字符。对于两个下标 $i,j$，其中 $1\le i<j\le N$，我们称 $B_i$ 和 $B_j$ 是匹配的括号，如果满足：
- $B_i=\texttt{(}$ 且 $B_j=\texttt{)}$；
- $i=j-1$，或者子序列 $C=B_{i+1}B_{i+2}\ldots B_{j-1}$ 是合法的括号序列。
令 $S$ 是一个只包含小写英文字母的字符串。我们定义 $S_i$ 是 $S$ 串中第 $i$ 个字符。我们称一个合法的括号序列 $B$ 和 $S$ 匹配，如果满足：
- $B$ 的长度和 $S$ 相等；
- 对于任意下标 $i,j$ 对，且 $i<j$。如果 $B_i$ 和 $B_j$ 是匹配的，那么 $S_i=S_j$。
对于给定长度为 $N$ 的 $S$ 串，请找到字典序最小的合法括号序列，满足和 $S$ 匹配。如果这样的括号序列不存在，输出 $-1$。
我们定义一个合法的括号序列是如下之一：
- 一个空串；
- 串
(B)，其中 B 是一个合法的括号序列；-
LR，两个合法的括号序列 L 和 R 直接拼接而成得到的串。令 $B$ 是一个长度为 $N$ 的合法括号序列。定义 $B_i$ 是序列 $B$ 中第 $i$ 个字符。对于两个下标 $i,j$，其中 $1\le i<j\le N$，我们称 $B_i$ 和 $B_j$ 是匹配的括号，如果满足：
- $B_i=\texttt{(}$ 且 $B_j=\texttt{)}$；
- $i=j-1$，或者子序列 $C=B_{i+1}B_{i+2}\ldots B_{j-1}$ 是合法的括号序列。
令 $S$ 是一个只包含小写英文字母的字符串。我们定义 $S_i$ 是 $S$ 串中第 $i$ 个字符。我们称一个合法的括号序列 $B$ 和 $S$ 匹配，如果满足：
- $B$ 的长度和 $S$ 相等；
- 对于任意下标 $i,j$ 对，且 $i<j$。如果 $B_i$ 和 $B_j$ 是匹配的，那么 $S_i=S_j$。
对于给定长度为 $N$ 的 $S$ 串，请找到字典序最小的合法括号序列，满足和 $S$ 匹配。如果这样的括号序列不存在，输出 $-1$。
输入格式
输入一行一个长度为 $N$ 且只包含小写英文字母的串 $S$。
输出格式
输出长度为 $N$ 的，和 $S$ 匹配且字典序最小的合法括号序列，如果这样的括号序列不存在，输出 $-1$。
输入输出样例
输入 #1
abbaaa
输出 #1
(()())
输入 #2
abab
输出 #2
-1
说明/提示
对于全部数据，$2\le N\le 10^5$。
- 对于其中 $10$ 分的测试点，$N\le 18$。
- 对于另外 $27$ 分的测试点，$N\le 2\times 10^3$。
如果存在一个下标 $i\ (1\le i\le N)$，满足对于所有 $j<i$，都有 $A_j=B_j$，且 $A_i<B_i$，我们就称括号序列 $A$ 的字典序小于括号序列 $B$。
字符 $\texttt{(}$ 的字典序小于字符 $\texttt{)}$。
- 对于其中 $10$ 分的测试点，$N\le 18$。
- 对于另外 $27$ 分的测试点，$N\le 2\times 10^3$。
如果存在一个下标 $i\ (1\le i\le N)$，满足对于所有 $j<i$，都有 $A_j=B_j$，且 $A_i<B_i$，我们就称括号序列 $A$ 的字典序小于括号序列 $B$。
字符 $\texttt{(}$ 的字典序小于字符 $\texttt{)}$。