← 返回题目列表

AtCoder · arc223_e

E. 阴阳两位插入

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

分数: 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).