← 返回题目列表

Codeforces · 1381/B

B. 取消合并

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

设 $$$a$$$ 和 $$$b$$$ 分别为长度为 $$$n$$$ 和 $$$m$$$ 的两个数组,没有共同元素。我们可以递归地定义一个长度为 $$$n+m$$$ 的新数组 $$$\mathrm{merge}(a,b)$$$ ,如下所示:

- 如果其中一个数组为空,则结果为另一个数组。即 $$$\mathrm{merge}(\emptyset,b)=b$$$ 和 $$$\mathrm{merge}(a,\emptyset)=a$$$。特别是,$$$\mathrm{merge}(\emptyset,\emptyset)=\emptyset$$$。
- 如果两个数组都非空,且 $$$a_1<b_1$$$,则 $$$\mathrm{merge}(a,b)=[a_1]+\mathrm{merge}([a_2,\ldots,a_n],b)$$$。也就是说,我们删除 $$$a$$$ 的第一个元素 $$$a_1$$$,合并剩余的数组,然后将 $$$a_1$$$ 添加到结果的开头。
- 如果两个数组都非空,且 $$$a_1>b_1$$$,则 $$$\mathrm{merge}(a,b)=[b_1]+\mathrm{merge}(a,[b_2,\ldots,b_m])$$$。也就是说,我们删除 $$$b$$$ 的第一个元素 $$$b_1$$$,合并剩余的数组,然后将 $$$b_1$$$ 添加到结果的开头。

这个算法有一个很好的特性,如果 $$$a$$$ 和 $$$b$$$ 被排序,那么 $$$\mathrm{merge}(a,b)$$$ 也会被排序。例如,它用作合并排序中的子例程。然而,对于这个问题,我们也将考虑作用于非排序数组的相同过程。例如,如果 $$$a=[3,1]$$$ 且 $$$b=[2,4]$$$,则 $$$\mathrm{merge}(a,b)=[2,3,1,4]$$$。

排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。

存在长度为 $$$2n$$$ 的排列 $$$p$$$。确定是否存在两个数组 $$$a$$$ 和 $$$b$$$,每个数组的长度为 $$$n$$$ 并且没有共同元素,因此 $$$p=\mathrm{merge}(a,b)$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 1000$$$) — 测试用例的数量。接下来的 $$$2t$$$ 行包含测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2000$$$)。

每个测试用例的第二行包含 $$$2n$$$ 整数 $$$p_1,\ldots,p_{2n}$$$ ($$$1\le p_i\le 2n$$$)。保证 $$$p$$$ 是一个排列。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,如果存在数组$$$a$$$、$$$b$$$,每个长度为$$$n$$$并且没有公共元素,则输出“YES”,以便$$$p=\mathrm{merge}(a,b)$$$。否则,输出“NO”。

示例

输入 #1

6
2
2 3 1 4
2
3 1 2 4
4
3 2 6 1 5 7 8 4
3
1 2 3 4 5 6
4
6 1 3 7 4 5 8 2
6
4 3 2 5 1 11 9 12 8 6 10 7

输出 #1

YES
NO
YES
YES
NO
NO

注意

在第一个测试用例中,$$$[2,3,1,4]=\mathrm{merge}([3,1],[2,4])$$$。

在第二个测试用例中,我们可以证明 $$$[3,1,2,4]$$$ 不是两个长度为 $$$2$$$ 的数组的合并。

在第三个测试用例中,$$$[3,2,6,1,5,7,8,4]=\mathrm{merge}([3,2,8,4],[6,1,5,7])$$$。

在第四个测试用例中,例如$$$[1,2,3,4,5,6]=\mathrm{merge}([1,3,6],[2,4,5])$$$。