← 返回题目列表

AtCoder · arc203_b

B. 总和相等则交换

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

分数: 500 点

问题陈述

你的长度是-N 整数序列 A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_N),每个由 0 和 1。 让 A[i,j] 表示连续子序列 A 来自 i-th 通过 j- 第一个元素。如果 i>j,然后 A[i,j] 是一个长度-0 序列。 您可以执行以下操作 A 任意次数:

  • 选择四个整数 a,b,c,d 满足以下两个条件:
    • 1 \leq a \leq b < c \leq d \leq N
    • \sum_{i=a}^{b}{A_i}=\sum_{i=c}^{d}{A_i}
  • 交换 A[a,b] 和 A[c,d]。更准确地说,替换 A 与通过连接形成的序列 A[1,a-1], A[c,d], A[b+1,c-1], A[a,b], A[d+1,N] 按此顺序。

判断是否 A 可以匹配 B.

解决 T 每个输入文件的测试用例。

约束

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 1
  • 0 \leq B_i \leq 1
  • 总和 N 所有测试用例最多 2\times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
case_1
case_2
\vdots
case_T

每个案例均按以下格式给出:

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

输出

总共输出答案 T 行。 的 t- 第行应包含 Yes if A 可以匹配 B 为 t- 第一个测试用例,以及 No 否则。


示例输入 1

3
6
1 1 1 0 0 1
0 1 1 0 1 1
2
0 0
1 0
3
1 1 1
1 1 1

示例输出 1

Yes
No
Yes

在第一个测试用例中, A 最初是 (1,1,1,0,0,1).
通过选择 (a,b,c,d)=(1,2,3,6) 并执行操作, A 变为 (1,0,0,1,1,1).
接下来,通过选择 (a,b,c,d)=(1,2,3,4) 并执行操作, A 变为 (0,1,1,0,1,1),匹配 B.
在第二个测试用例中, A 无法匹配 B.
在第三个测试用例中, A 已匹配 B 从头开始。