题面

Grigory has n n magic stones, conveniently numbered from \(1\) to \(n\). The charge of the \(i\)-th stone is equal to \(c_i\).

Sometimes Grigory gets bored and selects some inner stone (that is, some stone with index \(i\), where \(2 \le i \le 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 \(c_i\) changes to \(c_i' = c_{i + 1} + c_{i - 1} - c_i\)

Andrew, Grigory's friend, also has n n stones with charges \(t_i\). 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 \(c_i\) into \(t_i\) for all \(i\)?

题意

给定两个数组 \(c\) 和 \(t\)，一次操作可以把 \(c_i\) 变成 \(c_{i-1}+c_{i+1}-c_{i} \ (2 \le i \le n-1)\)，问若干次操作后，可不可以把 \(c\) 数组变成 \(t\)

思路

设 \(a\) 为 \(c\) 的差分数组（即 \(a_i=c_i-c_{i-1}\)）

每对 \(c_i\) 进行一次操作后：

所以，每次操作会将 \(c\) 的差分数组交换两个数，只要判一下 \(c\) 与 \(t\) 的差分数组是否相同即可

代码

#include <bits/stdc++.h>

using namespace std;

int n,a[100001],b[100001],c[100001],d[100001];

int main() {

    cin >> n;

    for (int i = 1;i <= n;i++) {

        cin >> a[i];

        if (i ^ 1) b[i-1] = a[i]-a[i-1];

    }

    sort(b+1,b+n);

    for (int i = 1;i <= n;i++) {

        scanf("%d",&c[i]);

        if (i ^ 1) d[i-1] = c[i]-c[i-1];

    }

    sort(d+1,d+n);

    if (a[1] ^ c[1] || a[n] ^ c[n]) {

        printf("No");

        return 0;

    }

    for (int i = 1;i < n;i++)

        if (b[i] ^ d[i]) {

            printf("No");

            return 0;

        }

    printf("Yes");

	return 0;

}