Magic Stones CodeForces - 1110E

标签： 思维 差分

---

题目描述

Grigory has nn magic stones, conveniently numbered from 11 to nn. The charge of the ii-th stone is equal to ci.

Sometimes Grigory gets bored and selects some inner stone (that is, some stone with index i, where 2≤i≤n−1), and after that synchronizes it with neighboring stones. After that, the chosen stone loses its own charge, but acquires the charges from neighboring stones. In other words, its charge ci changes to c_i=c_i+1+c_i−1−c_i.

Andrew, Grigory’s friend, also has nn stones with charges titi. Grigory is curious, whether there exists a sequence of zero or more synchronization operations, which transforms charges of Grigory’s stones into charges of corresponding Andrew’s stones, that is, changes ci into ti for all i?
Input

The first line contains one integer n (2≤n≤10⁵) — the number of magic stones.

The second line contains integers c1,c2,…,cn(0≤ci≤2⋅10⁹) — the charges of Grigory’s stones.

The second line contains integers t1,t2,…,tn(0≤ti≤2⋅10⁹) — the charges of Andrew’s stones.
Output

If there exists a (possibly empty) sequence of synchronization operations, which changes all charges to the required ones, print “Yes”.

Otherwise, print “No”.
Examples
input
4
7 2 4 12
7 15 10 12

output
Yes

input
3
4 4 4
1 2 3

output
No

Note

In the first example, we can perform the following synchronizations (1-indexed):

First, synchronize the third stone [7,2,4,12]→[7,2,10,12][7,2,4,12]→[7,2,10,12].
Then synchronize the second stone: [7,2,10,12]→[7,15,10,12][7,2,10,12]→[7,15,10,12].

In the second example, any operation with the second stone will not change its charge

解法

可以发现即使进行了操作，数字之间两两差分的值组成的序列是不会变的，变的只是顺序。并且经过足够多的操作之后也肯定会变回原序列。
所以我们只需要对原来两个序列分别计算出差分序列，排序后看是否相等即可（注意原序列头尾两个数字也必须相等）

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define N 100010
using namespace std;

int n;
int a[N], a1[N], b[N], b1[N];

bool judge()
{
    if(a[1] != b[1] || a[n] != b[n]) return false;
    for(int i = 1; i < n; i ++)
        if(a1[i] != b1[i]) return false;
    return true;    
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for(int i = 1; i < n; i ++) a1[i] = a[i + 1] - a[i];
    for(int i = 1; i <= n; i ++) scanf("%d", &b[i]);
    for(int i = 1; i < n; i ++) b1[i] = b[i + 1] - b[i];
    sort(a1 + 1, a1 + n); sort(b1 + 1, b1 + n);
    if(judge()) printf("Yes");
    else printf("No");
    return 0;
} 

心得

考场上没想出来，看了题解才知道的。
以后看到类似于相邻两数相减(或者其他操作之类的)，都可以用差分的思想去思考一下。