← 返回题目列表

Codeforces · 2233/C

C. 括号序列的成本

中文机器翻译题面 查看原题

令任意括号字符串的成本为其最长子序列$$$^{\text{*}}$$$的长度,该子序列是常规括号序列$$$^{\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 5\,000$$$; $$$0 \le k \le n$$$) - 字符串 $$$s$$$ 的长度和最大删除次数。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,由字符“$$$\texttt{(}$$$”和/或“$$$\texttt{)}$$$”组成。

附加输入限制:

  • 所有测试用例的 $$$n$$$ 总和不超过 $$$5\,000$$$。

输出

对于每个测试用例,输出长度为 $$$n$$$ 的二进制字符串。第 $$$i$$$ 个字符应等于“1"如果字符串$$$s$$$对应的字符被删除,并且"0”否则。

字符串中 1 的数量不得超过 $$$k$$$。去掉标记字符后得到的字符串的代价必须尽可能小。

如果有多个答案,则输出其中任何一个。

示例

输入
复制

10
2 1
)(
2 0
()
4 1
(())
4 1
())(
5 1
((())
6 2
()()()
6 2
(()())
6 2
())(()
7 3
(()((()
10 3
(()())())(

输出
复制

00
00
1000
1000
00010
101000
001001
100001
1100001
0101001000

注意

在第一个测试用例中,字符串的成本已经是 $$$0$$$,因此可以不删除任何内容。

在第三个测试用例中,一次删除后不可能得到成本$$$0$$$的字符串,但是删除任意字符都可以获得成本$$$2$$$的字符串。