「Codeforces 1110E」Magic Stones

Description

题目链接:Codeforces 1110E

Grigory 有 $n​$ 个魔法石,标号为 $1​$ 到 $n​$。第 $i​$ 个石头的电荷量为 $c_i​$。有时 Grigory 会选择一些内部的石头(第 $i​$ 个石头满足 $2\le i\le n-1​$),使得它失去自己的电荷,得到相邻的石头的电荷。也就是说,它的电荷 $c_i​$ 变为 $c_i’=c_{i+1}+c_{i-1}-c_i​$。

Grigory 的朋友 Andrew 也有 $n$ 个电荷量为 $t_i$ 的石头。Grigory 想知道是否存在一系列操作,将 Grigory 的石头的电荷量和 Andrew 的石头的电荷量相同。如果存在操作,那么输出 Yes 否则输出 No

数据范围:$2\le n\le 10^5​$,$0\le c_i,t_i\le 2\times 10^9​$


Solution

我们定义差分数组 $d_i=c_{i+1}-c_i$,如果我们此时对 $c_i$ 进行操作,即 $c_i’=c_{i+1}+c_{i-1}-c_i$,那么我们将得到:

  • $d_{i-1}’=c_i’-c_{i-1}=(c_{i+1}+c_{i-1}-c_i)-c_{i-1}=c_{i+1}-c_i=d_i$
  • $d_i’=c_{i+1}-c_i’=c_{i+1}-(c_{i+1}+c_{i-1}-c_i)=c_i-c_{i-1}=d_{i-1}$

也就是说,我们对 $c_i$ 进行一次操作,在差分数组中的体现,只不过是将 $d_{i-1}$ 和 $d_i$ 的值交换了。这意味着,如果我们把差分数组看做是无序的,那么它将是永远不会变化的。

因此,我们只要把 $c$ 和 $t$ 数组的差分数组求出来,如果排序后两个数组完全相同那么意味着有解(注意:我们首先要判断 $c_1=t_1,c_n=t_n$);否则就是无解。

时间复杂度:$O(n\log n)$


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <algorithm>

const int N=1e5+5;
int n,a[N],b[N];

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