「Codeforces 1110E」Magic Stones

发表于 | | 阅读次数:
字数统计: 532 字

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%