[CF1110E]Magic Stones

题目大意：有一个长度为$n(n\leqslant10^5)$的数列$c$，问是否可以经过若干次变换变成数列$t$，一次变换为$c'_i=c_{i+1}+c_{i-1}-c_i$

题解：思考一次变换的本质，对$c$做差分，原差分为$c_i-c_{i-1},c_{i+1}-c_i$；对$c_i$做一次变换后为：$c'_i-c_{i-1}=c_{i+1}+c_{i-1}-c_i-c_{i-1}=c_{i+1}-c_i,c_{i+1}-c'_i=c_{i+1}-(c_{i+1}+c_{i-1}-c_i)=c_i-c_{i-1}$，也就是说交换了原差分数组的两位。

所以就把$c$数组差分一下，看是不是和$t$数组相同即可，注意判断$c_1,c_n$是否和$t_1,t_n$相同，因为这两个位置无法做变换。

卡点：无

C++ Code：

#include <algorithm>

#include <cstdio>

#define maxn 100010

int n;

int s[maxn], t[maxn];

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i) scanf("%d", s + i);

	for (int i = 1; i <= n; ++i) scanf("%d", t + i);

	if (s[1] != t[1] || s[n] != t[n]) {

		puts("No");

		return 0;

	}

	for (int i = n; i + 1; --i) {

		s[i] -= s[i - 1];

		t[i] -= t[i - 1];

	}

	std::sort(s + 2, s + n + 1); std::sort(t + 2, t + n + 1);

	for (int i = 2; i <= n; ++i) if (s[i] != t[i]) {

		puts("No");

		return 0;

	}

	puts("Yes");

	return 0;

}

巴特西

[CF1110E]Magic Stones

最新文章

热门文章