题解 CF1110E 【Magic Stones】
ChthollyTree
2019-02-08 08:30:17
题意：
给定一个长度为n的序列c 对于一个位置 i（1 < i < n）
可以进行如下变换操作
$c_{i}'$ = $c_{i+1} + c_{i-1} - c_{i}$
问是否可以经过若干次操作变成序列t
作c序列的差分数组
就是定义 $a_{i}$ = $c_{i} - c_{i-1}$
我们会发现
对于 $c_{i}$ 的一次变换，交换的差分数组的两个数
如$c_{i}'$ = $c_{i+1} + c_{i-1} - c_{i}$ 操作后
本来差分数组是 $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}$,$c_{i}-c_{i-1}$ ,
这样就求出c,t的差分数组就行了
注意因为1，n无法更改，要特判
```
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
int n,m;
int a[MAXN],b[MAXN];
int c[MAXN],d[MAXN];
void rd()
{
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]);
}
int main()
{
rd();//
if(a[1] != b[1])
{//
cout<<"No";//
return 0;
}
if(a[n] != b[n])
{
cout<<"No";
return 0;
}
for(int i = 2; i <= n; i ++)
{
c[i-1] = a[i] - a[i-1];
d[i-1] = b[i] - b[i-1];
}
sort(c+1,c+n);//
sort(d+1,d+n);//
for(int i = 1; i < n; i ++)
if(c[i] != d[i])
{//
cout<<"No";//
return 0;//
}//
cout<<"Yes";//
return 0;//
}//
/*
4
7 2 4 12
7 15 10 12
4
1 2 2 4
1 1 3 4
*/
```