传送门：https://codeforces.com/contest/1110/problem/E
E. Magic Stones
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Grigory has nn magic stones, conveniently numbered from 11 to nn. The charge of the ii-th stone is equal to cici.
Sometimes Grigory gets bored and selects some inner stone (that is, some stone with index ii, where 2≤i≤n?12≤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 cici changes to c′i=ci+1+ci?1?cici′=ci+1+ci?1?ci.
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 cici into titi for all ii?
Input
The first line contains one integer nn (2≤n≤1052≤n≤105) — the number of magic stones.
The second line contains integers c1,c2,…,cnc1,c2,…,cn (0≤ci≤2?1090≤ci≤2?109) — the charges of Grigory's stones.
The second line contains integers t1,t2,…,tnt1,t2,…,tn (0≤ti≤2?1090≤ti≤2?109) — 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
Copy
4 7 2 4 12 7 15 10 12
output
Copy
Yes
input
Copy
3 4 4 4 1 2 3
output
Copy
No
Note
In the first example, we can perform the following synchronizations (11-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.
告诉你两个数组，你可以无限使用c[i] = c[i + 1] + c[i - 1] - cd[i]，问能不能由c数组变成t数组
我们可以证明：（设d为差分数组）
d[i] = c[i] - c[i - 1]
c'[i] = (c[i + 1] + c[i - 1] - c[i])
d'[i] = c'[i] - c[i - 1] = (c[i + 1] + c[i - 1] - c[i]) - c[i - 1] = c[i + 1] - c[i] = d[i + 1]
d'[i + 1] = c[i + 1] - c'[i] = c[i + 1] - (c[i + 1] + c[i - 1] - c[i]) = c[i] - c[i - 1] = d[i]
可以发现如果进行一次题目的操作，那差分数组就会交换顺序，所以直接求一下差分数组，判断是否一致，并且c数组的首尾和t数组的首尾相同（因为首尾是不可以修改的）
代码如下：
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
//vector<vector<ll> >v;vector<int> v;const int maxn = 1e5 + 10;ll a[maxn], b[maxn];
bool flag[maxn];int main() {int n;while(cin >> n) {for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)cin >> b[i];if(n == 2 || n == 1) {for(int i = 1; i <= n; i++) {if(a[i] != b[i]) {cout << "No" <<endl;return 0;}}cout << "Yes" << endl;continue;}vector<int>c;vector<int>d;for (int i = 1; i <= n;i++)c.push_back(a[i + 1] - a[i]),d.push_back(b[i + 1] - b[i]);sort(c.begin(),c.end());sort(d.begin(),d.end());for(int i = 0; i< n - 1; i++) {if(c[i] != d[i]) {cout << "No" << endl;return 0;}}if(a[1] == b[1] && a[n] == b[n])printf("Yes\n");elsecout << "No" << endl;}return 0;
}