CodeForces 1110E magic stones（构造题、好题）

题目大意：
给定两个序列ci和ti，每次变换操作ci`=ci+1+ci-1-ci，询问ci能否变成ti

这是一道构造题

我们可以先列出变换操作的柿子
ci’=ci+1+ci-1-ci
化简
ci’-ci-1=ci+1-ci
我们可以发现，每次进行变换操作，即变换ci-ci-1与ci+1-ci的差值
我们可以设查分数组di=ci+1-ci
如果在i位置进行变换操作，那么有下面柿子
di+1=ci+1-(ci+1+ci-1-ci)=ci-ci-1=di
di=(ci+1+ci-1-ci)-ci-1=ci+1-ci=di+1
更加证明了每一次变换等价于变换查分数组di，即ci-ci-1与ci+1-ci的差值
我们只需要比较两个数列的查分数组是否相同即可

代码如下

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
int a[maxn],b[maxn],c[maxn],d[maxn],n;
inline int read()
{
	int w=1,s=0; char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')w=-1; ch=getchar();}
	while(ch>='0' && ch<='9'){s=s*10+ch-'0'; ch=getchar();}
	return w*s;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++) b[i]=read();
	if(a[1]!=b[1] || a[n]!=b[n]) {printf("No"); return 0;}
	for(int i=1;i<n;i++)
	{
		c[i]=a[i+1]-a[i]; d[i]=b[i+1]-b[i];
	}
	sort(c+1,c+n); sort(d+1,d+n);
	for(int i=1;i<n;i++) if(c[i]!=d[i]) {printf("No"); return 0;}
	printf("Yes");
	return 0;
}

最后

以上就是紧张钢铁侠为你收集整理的CodeForces 1110E magic stones（构造题、好题）的全部内容，希望文章能够帮你解决CodeForces 1110E magic stones（构造题、好题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。