CF1110E Magic Stones

CF1110E Magic Stones

给定长度为 (n) 的两个数组 (c, t)

一次操作可以选择 (1<i<n) ，使 (c_i) 变为 (c_i'=c_{i+1}+c_{i-1}-c_i)

能否做若干次操作使得 (c_i=t_i(1leq ileq n))

(1<nleq10^5, c_i, t_iin[0, 2 imes10^9])

差分

---

令 (c) 的差分数组为 (d)

一次操作后 (d_i=c_{i+1}-c_i, d_{i+1}=c_i-c_{i-1}) ，可以发现这就是交换了 (d_i, d_{i+1})

因此再将 (t) 差分，比较 (d) 在 ([2, n]) 中的每个数是否都在 (t) 的差分数组中出现过，出现过则为 Yes

注意要特判 (c_1=t_1, c_n=t_n)

时间复杂度 (O(nlog n))

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
int n, c[maxn], d[maxn], t[maxn];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", c + i);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", t + i);
  }
  if (c[1] != t[1] || c[n] != t[n]) {
    return puts("No"), 0;
  }
  for (int i = n; i; i--) {
    d[i] = c[i] - c[i - 1];
    t[i] -= t[i - 1];
  }
  sort(d + 2, d + n + 1);
  sort(t + 2, t + n + 1);
  for (int i = 2; i <= n; i++) {
    if (d[i] != t[i]) {
      return puts("No"), 0;
    }
  }
  puts("Yes");
  return 0;
}