分数: 700 点
问题陈述
给定整数序列 A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_M) 长度 2 或更多,由以下组成 0和 1s。
您可以对 A 任意次数:
- 选择一个整数 i 满意 1 \leq i \leq |A|-1.
- 插入 1-A_i 和 1-A_{i+1} 之间按此顺序 A_i 和 A_{i+1}.
判断是否可以使 A 等于 B.
解决 T 每个输入的测试用例。
约束
- 1 \leq T \leq 10^5
- 2 \leq N \leq M \leq 2 \times 10^5
- A_i, B_i \in \{0,1\}
- 总和 N+M 所有测试用例最多 4 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例 \mathrm{case}_t 按以下格式给出:
N M A_1 A_2 \dots A_N B_1 B_2 \dots B_M
输出
输出总共的答案 T 行。
的 t- 第行应包含 Yes 如果可以的话 A 等于 B 为 t第一个测试用例,以及 No 否则。
示例输入 1
3 3 7 0 1 1 0 1 0 1 1 0 1 2 4 0 1 0 1 0 1 3 4 0 0 0 0 0 0 1
示例输出 1
Yes Yes No
对于第一个测试用例,最初 A=(0,1,1).
首先,选择 i=2 给出 A=(0,1,0,0,1).
接下来,选择 i=3 给出 A=(0,1,0,1,1,0,1).