数列转换——高级

 1 Sec 64 MB |  显示标签
1124
通过提交

题目描述

有一个数列,a1,a2,a3,…,an。每次可以从中任意选三个相邻的数,ai-1,ai,ai+1,进行如下操作(此操作成为对ai的操作):
(a(i-1),ai,a(i+1))---> (a(i-1)+ai,-ai,a(i+1)+ai)
给定初始和目标序列,是否能通过以上操作,讲初始序列转换为目标序列?例如初始序列为(1 6 9 4 2 0),目标序列为(7 -6 19 2 -6 6)。经过对4,5,2,个数操作之后,可以变换。
初始序列是(1 2 3),目标序列(1 3 2)无论如何都无法转换。
现在给定序列,问能否通过有限步的操作进行转换。

输入格式

有多组测试数据:
第一行,包含一个整数Num,表示测试数据的个数。(1<=Num<=10)
每组测试数据,
第一行一个整数N,表示序列有N个整数。1<=N<=10000
接下来两行,每行N个数,初始和目标序列。每个数范围[-K and K]。1<=K<=10,000,000。

输出格式

共Num行,每行Yes或者No

样例输入 #1

2
6
1 6 9 4 2 0
7 -6 19 2 -6 6
2
1 2 3
1 3 2

样例输出 #1

Yes
No

 上传者
coach
 创建时间
2012-11-13 12:22