さよなら、全てのエヴァンゲリオン。

宝宝分讨。

连续三个位置之和为偶数，要么没有奇数，要么恰有两个奇数。

如果任两个奇数中间都间隔至少两个偶数，那么显然无法操作到任何一个奇数，故奇数不能改变位置，只可以把相邻两个奇数之间的偶数任意重排，排序之后判断即可，注意特判相邻两个奇数之间只有两个偶数的情况，此时不能重排。

否则存在一对位置相邻的奇数可以重排邻近的三个位置，容易发现我们利用它可以在序列内任意移动，任意交换邻近的三个位置，所以我们可以任意重排奇数和偶数。特判整个序列只有两个偶数的情况，此时容易发现两个偶数之间不能交换相对顺序，因为我们只能通过直接的一次操作重排两个偶数，但是两个偶数一个奇数总和奇数不合法。

复杂度 1log。

CPP

#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
const int N = 2e5 + 10;
int n, A[N], B[N];
int main() {
	freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
	int _ = 1;
	while (_ --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> A[i];
		for (int i = 1; i <= n; i ++) cin >> B[i];
		bool flag = false;
		for (int i = 3; i <= n; i ++)
			flag |= ((A[i] + A[i - 1] + A[i - 2]) % 2 == 0 && ((A[i] & 1) || (A[i - 1] & 1) || (A[i - 2] & 1)));
		if (!flag) {
			bool Ans = true;
			vector<int> pos; pos.push_back(0);
			for (int i = 1; i <= n; i ++) if (A[i] % 2 == 1 || B[i] % 2 == 1) {
				if (A[i] != B[i]) Ans = false;
				pos.push_back(i);
			}
			pos.push_back(n + 1);
			if (Ans) {
				for (int i = 1; i < (int)pos.size(); i ++) if (pos[i] - pos[i - 1] > 3) {
					sort(A + pos[i - 1] + 1, A + pos[i]); sort(B + pos[i - 1] + 1, B + pos[i]);
				}
				for (int i = 1; i <= n; i ++) Ans &= (A[i] == B[i]);
			}
			cout << (Ans ? "Yes\n" : "No\n");
		} else {
			bool flag2 = false;
			for (int i = 3; i <= n; i ++)
				flag2 |= ((B[i] + B[i - 1] + B[i - 2]) % 2 == 0 && ((B[i] & 1) || (B[i - 1] & 1) || (B[i - 2] & 1)));
			if (!flag2) { cout << "No\n"; continue; }
			vector<int> vec1, vec2;
			for (int i = 1; i <= n; i ++) if (A[i] % 2 == 0) vec1.push_back(A[i]);
			for (int i = 1; i <= n; i ++) if (B[i] % 2 == 0) vec2.push_back(B[i]);
			sort(A + 1, A + 1 + n); sort(B + 1, B + 1 + n);
			for (int i = 1; i <= n; i ++) flag2 &= (A[i] == B[i]);
			if (vec1.size() == 2) flag2 &= (vec1[0] == vec2[0] && vec1[1] == vec2[1]);
			cout << (flag2 ? "Yes\n" : "No\n");
		}
	}
	return 0;
}

さよなら、全てのエヴァンゲリオン。

文章操作

相关推荐

评论

さよなら、全てのエヴァンゲリオン。