CF2233C Cost of a Bracket Sequence

定义任意括号序列的“代价”为其最长子序列是“正规括号序列”$^{\text{∗}}$的长度。 给定一个括号字符串 $s$ 和一个整数 $k$，你的任务是从字符串 $s$ 中删除至多 $k$ 个字符，使得最终得到的字符串的代价尽可能小。 $^{\text{∗}}$ 序列 $a$ 是序列 $b$ 的子序列，当且仅当 $a$ 可以通过从 $b$ 中删除若干（可能为零个或全部）位于任意位置的元素得到。 $^{\text{†}}$ 如果可以通过在序列中插入若干个 $+$ 和 $1$ 字符，使其变为一个合法的算术表达式，则称该括号序列为“正规括号序列”。比如，序列“$\texttt{(())()}$”、“$\texttt{()}$”、“$\texttt{(()(()))}$”是正规括号序列，而“$\texttt{)(}$”、“$\texttt{(()}$”和“$\texttt{(()))(}$”不是正规括号序列。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 5000$；$0 \le k \le n$），表示字符串 $s$ 的长度和最多可以删除的字符数。 每个测试用例的第二行是一个长度为 $n$ 的字符串 $s$，仅包含字符“(”和“)”。 附加输入限制： - 所有测试用例中 $n$ 的总和不超过 $5000$。

对于每个测试用例，输出一个长度为 $n$ 的二进制字符串。当且仅当你删除了第 $i$ 位字符时，第 $i$ 位为 $1$，否则为 $0$。 二进制字符串中 $1$ 的数量不能超过 $k$。删除相应字符后所得到字符串的代价要尽可能小。 如果有多种答案，输出任意一种即可。

在第一个测试用例中，字符串的代价已经为 $0$，因此可以选择不删除任何字符。 在第三个测试用例中，只能删除一个字符，无法得到代价为 $0$ 的字符串，但可以通过删除任意一个字符得到代价为 $2$ 的字符串。 由 ChatGPT 5 翻译