题目描述
�
a、
�
b是两个长度分别为
�
n和
�
m的数组，二者中没有相同的元素，我们可以定义一个长度为
�
+
�
n+m的新数组
�
�
�
�
�
(
�
,
�
)
merge(a,b):
如果
�
a和
�
b有一个为空数组，那么新数组就是非空的那个数组。即:
�
�
�
�
�
(
∅
,
�
)
�
,
�
�
�
�
�
(
�
,
∅
)
�
merge(∅,b)=b,merge(a,∅)=a.
如果
�
a和
�
b都非空，那么每次比较
�
a和
�
b的第一个元素，选择小的那个放入新数组，并将其删除。即：
如果
�
1
<
�
1
a
1
<b
1
，那么
�
�
�
�
�
(
�
,
�
)
[
�
1
]
+
�
�
�
�
�
(
[
�
2
,
.
.
.
,
�
�
]
,
�
)
.
merge(a,b)=[a
1
]+merge([a
2
,…,a
n
],b).我们将
�
a的第一个元素
�
1
a
1
放入新数组，然后在
�
a中将
�
1
a
1
删除，再继续和
�
b比较。
如果
�
1
�
1
a
1
b
1
，那么
�
�
�
�
�
(
�
,
�
)
=
[
�
1
]
�
�
�
�
�
(
�
,
[
�
2
,
.
.
.
,
�
�
]
)
.
merge(a,b)=[b
1
]+merge(a,[b
2
,…,b
n
]).我们将
�
b的第一个元素
�
1
b
1
放入新数组，然后在
�
b中将
�
1
b
1
删除，再继续和
�
a比较。
现在给你一个长度为
2
�
2n的序列
�
p(
1
,
2
,
.
.
.
,
2
�
1,2,…,2n的随机排列)，问你是否存在两个长度为
�
n的数组
�
a和
�
b使得
�
�
�
�
�
�
(
�
,
�
)
p=merge(a,b)。
输入示例
第一行包含整数
�
(
1
≤
�
≤
2000
)
t(1≤t≤2000)，表示测试数据组数。
对于每组测试数据，第一行包含一个整数
�
(
1
≤
�
≤
2000
)
n(1≤n≤2000)。
第二行包含
2
�
2n个整数
�
1
,
.
.
.
,
�
2
�
(
1
≤
�
�
≤
2
�
)
p
1
,…,p
2n
(1≤p
i
≤2n)，保证
�
p是一个序列。
保证所有测试数据
�
n的总和不超过
2000
2000。
输出示例
对于每组测试数据，如果存在没有相同元素的数组
�
a和
�
b，使得
�
�
�
�
�
�
(
�
,
�
)
p=merge(a,b)，输出"YES"，否则输出"NO"。
样例#1
输入样例#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
]
�
�
�
�
�
(
[
3
,
1
]
,
[
2
,
4
]
)
[2,3,1,4]=merge([3,1],[2,4])。
第二个测试数据，可以发现
[
3
,
1
,
2
,
4
]
[3,1,2,4]不能由两个长度为
2
2的数组构成。
第三个测试数据，
[
3
,
2
,
6
,
1
,
5
,
7
,
8
,
4
]
�
�
�
�
�
(
[
3
,
2
,
8
,
4
]
,
[
6
,
1
,
5
,
7
]
)
[3,2,6,1,5,7,8,4]=merge([3,2,8,4],[6,1,5,7])。
第四个测试数据，
[
1
,
2
,
3
,
4
,
5
,
6
]
�
�
�
�
�
(
[
1
,
3
,
6
]
,
[
2
,
4
,
5
]
)
[1,2,3,4,5,6]=merge([1,3,6],[2,4,5])。
以上只是单独拿某种情况以供参考。
加载最近代码
1
Debug提示
9
/9