博客

数列转换

  • Post author:
  • Post category:其他


描述

有一个数列a


1


,a


2


,a


3


…a


n


,每次可以从中任意选三个相邻的数a


i-1


,a


i


, a


i+1 ,


进行如下操作（此操作称为“对a


i


进行操作”）

(a

i-1

,a

i

,a

i+1

)->(a

i-1

+a

i

,-a

i

,a

i

+a

i+1

)

给定初始和目标序列，是否能通过以上操作，将初始序列转换成为目标序列？例如，初始序列(1 6 9 4 2 0)目标序列（7 -6 19 2 -6 6)可经过如下操作：

(1 6 9 4 2 0)->( 1 6 13 -4 6 0)->(1 6 13 2 -6 6)->(7 -6 19 2 -6 6)

请你判断给定的初始状态和目标状态，输出Yes（能够转换）或No（不能转换）

输入

第一行是一个正整数N,表示测试数据的组数。(N<=100)

每组测试数据的第一行是一个整数M(3<=M<=1000),表示该组测试数据的起始状态与结束状态都有M个数。

每组测试数据的第二行是M个整数Ai(-1000<=Ai<=1000)，表示起始状态。

每组测试数据的第三行是M个整数Bi(-1000<=Bi<=1000),表示终止状态。

输出

如果能够转换，输出Yes

如果不能转换，输出No

样例输入

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

样例输出

No

Yes


(ai-1, ai, ai+1)-> (ai-1+ai, -ai, ai+ai+1)




S1=ai-1                 S1’=ai-1+ai




S2=ai-1+ai            S2’=ai-1




S3=ai-1+ai+ai+1   S3’=ai-1+ai+ai+1




很容易看出S3=S3’，(S1,S2)=(S2’,S1’)。也就是说把(S1,S2,S3)中的S1和S2交换位置就能得到(S1’,S2’,S3’)。




稍微推广一下：设Si=a1+a2+…+ai，对(ai-1, ai, ai+1)操作本质上和交换Si-1, Si是等价的。




比如第一个Sample：




(1 6 9 4 2 0) ->(1 6 13 -4 6 0)->


(1 6 13 2 -6 6)->(7 -6 19 2 -6 6)




转化成和之后：




(1 7 16 20 22 22)->(1 7 20 16 22 22)->


(1 7 20 22 16 22)->(7 1 20 22 16 22)。



(1 2 3)->(1 3 6)




(1 3 2)->(1 4 6)




对(1 2 3)的操作实质上是不断的交换S(1 3 6)中的1, 3。无论如何也不可



能变成(1 4 6)，因为4 根本没在S(1 3 6)中出现过！

 

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a1[1010];
int a2[1010];
int s1[1010];
int s2[1010];
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        memset(s1,0,sizeof(s1));
        memset(s2,0,sizeof(s2));
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a1[i]);
            if(i==0) s1[i]=a1[i];
            else s1[i]=a1[i]+s1[i-1];
        }
        sort(s1,s1+n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a2[i]);
            if(i==0) s2[i]=a2[i];
            else s2[i]=a2[i]+s2[i-1];
        }
        sort(s2,s2+n);
        int f=0;
        for(int i=0;i<n;i++)
        {
            if(s1[i]!=s2[i])
                f=1;
        }
        if(f==0) printf("Yes\n");
        else printf("No\n");
    }
}