Once again, Boris needs the help of Anton in creating a task. This time Anton needs to solve the following problem:
There are two arrays of integers aa and bb of length nn . It turned out that array aa contains only elements from the set {−1,0,1}{−1,0,1} .
Anton can perform the following sequence of operations any number of times:
- Choose any pair of indexes (i,j)(i,j) such that 1≤i<j≤n1≤i<j≤n . It is possible to choose the same pair (i,j)(i,j) more than once.
- Add aiai to ajaj . In other words, jj -th element of the array becomes equal to ai+ajai+aj .
For example, if you are given array [1,−1,0][1,−1,0] , you can transform it only to [1,−1,−1][1,−1,−1] , [1,0,0][1,0,0] and [1,−1,1][1,−1,1] by one operation.
Anton wants to predict if it is possible to apply some number (zero or more) of these operations to the array aa so that it becomes equal to array bb . Can you help him?
Each test contains multiple test cases.
The first line contains the number of test cases tt (1≤t≤100001≤t≤10000 ). The description of the test cases follows.
The first line of each test case contains a single integer nn (1≤n≤1051≤n≤105 ) — the length of arrays.
The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (−1≤ai≤1−1≤ai≤1 ) — elements of array aa . There can be duplicates among elements.
The third line of each test case contains nn integers b1,b2,…,bnb1,b2,…,bn (−109≤bi≤109−109≤bi≤109 ) — elements of array bb . There can be duplicates among elements.
It is guaranteed that the sum of nn over all test cases doesn't exceed 105105 .
For each test case, output one line containing "YES" if it's possible to make arrays aa and bb equal by performing the described operations, or "NO" if it's impossible.
You can print each letter in any case (upper or lower).
5 3 1 -1 0 1 1 -2 3 0 1 1 0 2 2 2 1 0 1 41 2 -1 0 -1 -41 5 0 1 -1 1 -1 1 1 -1 1 -1
YES NO YES YES NO
这个题翻译过来就是：对于每个b[j]，能否表示为a[j]+k1*a[1]+k2*a[2]+...kj-1*a[j-1]，即线性组合。对于这个题目而言，因为b[i]依赖于a数组里i之前的数，所以有两种处理方法，一是从前向后遍历看能否组合出b[i]，一种是从后向前。那么选择哪种呢？因为假设当前的a[i]已经变成了b[i]，那么这会对处理后面的数产生影响。
考虑：
a数组 0 -1 1 -1
b数组 0 -1 -2 1
处理完第三个数后a数组里唯一的一个正数就消失了，无法继续构造出b[4]；但如果从后向前更新就没有这种问题。也就是说需要用到的都是当前数之前的数，从后往前更新比从前往后更新可利用的数的种类多，所以选择从后向前这种贪心策略。
这样的话只需要预处理出每个位置到一开始的正数，负数和0的个数，从后向前判断每个位置即可。
#include <bits/stdc++.h> using namespace std; int a[100005],b[100005],pos[100005],neg[100005],zero[100005],n; int main() { int t; cin>>t; while(t--) { scanf("%d",&n); int i; for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1;i<=n;i++) { scanf("%d",&b[i]); } bool flag=1; pos[0]=neg[0]=zero[0]=0; if(a[1]!=b[1])flag=0; for(i=1;i<=n;i++) { if(a[i]>0)pos[i]=pos[i-1]+1,zero[i]=zero[i-1],neg[i]=neg[i-1];//别忘更新不变的量 else if(a[i]==0)zero[i]=zero[i-1]+1,pos[i]=pos[i-1],neg[i]=neg[i-1]; else neg[i]=neg[i-1]+1,pos[i]=pos[i-1],zero[i]=zero[i-1]; } //遍历的时候应该从右往左，先处理右边的，因为左边的数会对右边的数产生影响而右边的数不会对左边的数产生影响 for(i=n;i>=2;i--) { if(b[i]-a[i]>0) { if(pos[i-1]==0){ flag=0;break;} } else if(b[i]-a[i]<0) { if(neg[i-1]==0){ flag=0;break;} } } if(flag)cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }