1010. 合法括号

题目描述

给定一个仅包含 ?、 ( 、 ) 的字符串。你需要构造一个字符串，将原字符串中的 ? 替换为 ( 或 ) 。 你要保证：

• 字符串构成一个 合法括号串。
• 字符串总 层数 为 $m$。 ​在这里我们定义总层数：

开始时存在一个空栈和总层数 $cnt=0$ ，依次从左往右匹配字符串的第 $i$ 位：

• 如果当前位置 $s_i$ 是左括号，将当前左括号加入栈顶。
• 如果当前位置 $s_i$ 是右括号，将 $cnt$ 加上此时栈内的元素数 $k$，之后再弹出栈顶的第一个左括号。

匹配完整个字符串后，此时 $cnt$ 即为总层数。

合法括号串的定义是：

• 空串为一个合法括号串。
• 若 A 是合法括号串。则 (A) 也是合法括号串。
• 若 A, B 是合法括号串。则 AB 也是合法括号串。

题目保证给定数据必然存在至少一个合法括号串。

输入格式

第一行测试组数 $T ( T \leq 20 )$。

对于每组测试数据：

第一行一个整数 $n, m\space ( 2\leq n \leq 2 \times 10^5, 1 \leq m \leq 10^7 )$ 其中 $n$ 是一个偶数，表示字符串长度，$m$ 见题目描述。

第二行一个字符串 $s$ 。

给定的字符串中 ? 必然连续（即只存在一串连续的 ? ）

输出格式

对于每组测试数据输出一行表示你构造的合法括号串 s'，同时需要保证题目性质（ 总层数 = $m$ ）。

样例输入

2
4 2
(??)
4 3
(??)

样例输出

()()
(())

提示

第二组测试数据中 (()) 对于第三个位置的右括号的层数为 $2$ ,第四个位置右括号层数为 $1$. $2 + 1 = 3$ 符合 $m = 3$ 的要求。

来源：2026杭电多校-测试专用（杭电第1场-内测） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1237&pid=1010 ⚠ 本题为 Special Judge。官方数据中的 .out 多为评测机判定输出（如 AC/OK/Correct/yes），导入后需自行提供 checker 方可正确评测。