2017. 考卷博弈

时间限制 1000 ms   内存限制 256 MB

小派派和小龙龙要玩一个游戏。

考试的成绩没有出完,他们目前只获取到了目前的成绩单,分别是 $X,Y$。

成绩单 $X$ 中有 $n$ 个整数,其中第 $i$ 个整数为 $X_i$,表示小龙龙第 $i$ 个科目的成绩。

成绩单 $Y$ 中有 $m$ 个整数,其中第 $i$ 个整数为 $Y_i$,表示小派派第 $i$ 个科目的成绩。

由于成绩单中有些成绩并没有出,所以还没有出的成绩用 $-1$ 表示,已经出了的成绩是一个非负整数。

小龙龙答应小派派考试成绩出来后,成绩更高的跟成绩更低的交朋友。然而他想反悔,所以打算让两张成绩单的成绩相等从而拒绝掉小派派,然而他的意图被小派派知道了,所以他们决定通过游戏决出小派派是否有当小龙龙朋友的资格。

游戏的具体规则如下:

小龙龙与小派派轮流往没有出成绩的科目处填成绩(可以填对方的成绩单)。

假设成绩单 $X$ 和 $Y$ 中所有已经出了的成绩中最小值是 $a$,最大值是 $b$。小龙龙或小派派所填的成绩是 $x$,那么必须满足 $x∈[a, b]$ (即所填成绩必须处于所有已经出了的成绩中最大值和最小值之间)。

一个人填完了一个成绩之后另一个人填,如果两张卷子的成绩都填满了之后有 $ \sum_{i=1}^{n} X_i = \sum_{i=1}^{m} Y_i $ 就小龙龙赢,不然小派派赢。

请问小龙龙是否有必胜策略。

输入数据

第一行一个整数 $t$ 代表数据组数。 $1 \le t \le 10^4$ 。

每组数据第一行两个整数 $n,m$ ,代表 $X$ 与 $Y$ 的长度。 $1 \le n,m \le 10^3$ 。

第二行 $n$ 个整数,其中第 $i$ 个整数为 $X_i$ ,代表小龙龙试卷中第 $i$ 门科目的成绩。 $-1 \le X_i \le 10^4$,$-1$ 代表成绩没出。

第三行 $m$ 个整数,其中第 $i$ 个整数为 $Y_i$,代表小派派试卷中第 $i$ 门科目的成绩。 $-1 \le Y_i \le 10^4$,$-1$ 代表成绩没出。

第四行一个字符 $A$ 或者 $B$ 分别代表小龙龙或小派派先手。

保证每组数据中 $X,Y$ 中至少存在 $1$ 个不是 $-1$ 的数字。

保证所有数据点的 $\sum n+\sum m \le 10^5$。

输出数据

每组数据一个字符串: YES 代表小龙龙有必胜策略,NO反之。

样例输入

复制
4

3 2
19 2 -1
21 -1
B

3 2
1 3 -1
3 -1
B

4 4
1 2 -1 -1
1 2 1 2
B

3 2
1 3 -1
3 3
A \n
\n
 · \n
  · ·  \n
  ·  \n
 \n
\n
 · \n
 · ·  \n
 ·  \n
 \n
\n
 · \n
 · ·  ·  \n
 · · · \n
 \n
\n
 · \n
 · ·  \n
 · \n
 \n

样例输出

复制
YES
NO
YES
YES   \n
  \n
   \n
   \n

样例说明

样例$1$中,小派派可以填 $[2,21]$ 范围内的整数,小派派填完数字之后,小龙龙只需要在另一个位置填上小派派填的数字即可。

样例$2$中,小派派在 $X$ 中填 $3$ 即可,小龙龙可以填 $[1,3]$ 范围内的整数,无论他填写什么都无法满足 $\sum X=\sum Y$。

样例$3$中,小派派可以填 $[1,2]$ 范围内的整数,小派派填完数字之后,小龙龙在另外一个位置填上 $3-$ 小派派所填的数字即可。

样例$4$中,小龙龙在 $-1$ 处填写 $2$ 即可。

每组数据间没有空行,这里只是方便显示加上去的。

提交

请先 登录

© 2024 FAQs Contact About