CF1110E Magic Stones
Coros_Trusds
·
·
题解
更好的阅读体验
神仙题
题目大意
一次操作选择 1 \lt i\lt n，使 c_i 变为 c_i'，c_i'=c_{i+1}+c_{i-1}-c_i。
是否能做若干次操作，使每个 c_i 和 t_i 相等？
题目分析
NOIP 2021 方差和这道题差不多。
差分，是前缀和的逆运算。形式化来说，长度为 n 的序列 a 的差分序列 c 满足：
$2\le i\le n$ 时，$c_i=a_i-a_{i-1}$。
--------
首先发现，如果 $c_1\neq t_1$ 或 $c_n\neq t_n$，显然不可能，直接输出 $\verb!No!$ 即可。
--------
考虑原序列中的一段 $c_{i-1},c_i,c_{i+1}$，差分后，差分序列为：$c_{i-1}-c_{i-2},c_{i}-c_{i-1},c_{i+1}-c_i$。
进行一次操作后：$c_{i-1},c_{i-1}+c_{i+1}-c_i,c_{i+1}$，差分一下，发现此时为：$c_{i-1}-c_{i-2},c_{i+1}-c_i,c_i-c_{i-1}$。
发现差分序列中的数没有变，但是位置发生了变化。
同理可得，序列 $c$ 无论经过多少次操作，差分序列内的数都没有变，改变的惟有顺序。
所以我们求出序列 $c,t$ 的差分序列 $ca,ct$ 后，排序比较是否一致即可。
时间复杂度 $\operatorname{O}(n\log n)$。
# 代码
```cpp
//2021/11/29
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <climits>//need "INT_MAX","INT_MIN"
#include <algorithm>
#define enter() putchar(10)
#define debug(c,que) cerr<<#c<<" = "<<c<<que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i=(st);i<=(ed);i++)cout<<arr[i]<<w;
#define speed_up() std::ios::sync_with_stdio(false)
#define endl "\n"
#define Input_Int(n,a) for(register int i=1;i<=n;i++)scanf("%d",a+i);
#define Input_Long(n,a) for(register long long i=1;i<=n;i++)scanf("%lld",a+i);
namespace Newstd
{
inline int read()
{
int x=0,k=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
{
k=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*k;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
}
using namespace Newstd;
using namespace std;
const int MA=100005;
int a[MA],b[MA];
int sua[MA],sub[MA];
int n;
int main(void)
{
n=read();
Input_Int(n,a);
Input_Int(n,b);
if(a[1]!=b[1] || a[n]!=b[n])
{
puts("No");
return 0;
}
sua[1]=a[1],sub[1]=b[1];
for(register int i=2;i<=n;i++)
{
sua[i]=a[i]-a[i-1];
sub[i]=b[i]-b[i-1];
}
sort(sua+1,sua+n+1);
sort(sub+1,sub+n+1);
for(register int i=1;i<=n;i++)
{
if(sua[i]!=sub[i])
{
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}
```