「日常训练」Magic Stones（CodeForces-1110E）

时间：2021-02-23 22:17:57

题意

给定两个数组c和t，可以对c数组中的任何元素变换\(c_i\)​成\(c_{i+1}+c_{i-1}-c_i\)​，问c数组在若干次变换后能否变换成t数组。

分析

这种魔法题目我是同样的没做过。Editorial里说用差分来能够看出思路。问题是，如何能够想到差分来做？因为它的变换就是相邻的数的加减法，那么想要找到思路的突破口必须也得从这里突破。

考虑变换前后的数组：

原来：\(a_{i-1}, a_i, a_{i+1}\)

之后：\(a_{i-1}, a_{i-1}+a_{i+1}-a_i,a_{i+1}\)

观察差分，会发现差分从\(a_i-a_{i-1}, a_{i+1}-a_i\)变成了\(a_{i+1}-a_i, a_i-a_{i-1}\)。

这意味着什么？差分交换了位置。进一步观察推理可以发现，无论怎么操作，最后你做这个变换就是在交换差分位置。

于是问题得到解答，具体见代码。

一道考察思维的题目。

代码

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define PB emplace_back

#define MP make_pair

#define fi first

#define se second

#define rep(i,a,b) for(repType i=(a); i<=(b); ++i)

#define per(i,a,b) for(repType i=(a); i>=(b); --i)

#define ZERO(x) memset(x, 0, sizeof(x))

#define MS(x,y) memset(x, y, sizeof(x))

#define ALL(x) (x).begin(), (x).end()

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

using pi=pair<int,int>;

using repType=int;

using ll=long long;

using ld=long double;

using ull=unsigned long long;

const int MAXN = 100005;

int arra[MAXN], arrb[MAXN];

int main()

{

	int n; cin>>n;

	vector<int> veca, vecb;

	rep(i,1,n)

	{

		cin>>arra[i];

		if(i!=1) veca.PB(arra[i]-arra[i-1]);

	}

	rep(i,1,n)

	{

		cin>>arrb[i];

		if(i!=1) vecb.PB(arrb[i]-arrb[i-1]);

	}

	sort(ALL(veca));

	sort(ALL(vecb));

	bool ok=true;

	rep(i,0,n-2)

	{

		if(veca[i]!=vecb[i])

		{

			ok=false;

			break;

		}

	}

	if(ok && arra[1]==arrb[1]) cout<<"Yes"<<endl;

	else cout<<"No"<<endl;

	return 0;

}

相关文章