[ARC155C] Even Sum Triplet 题解

一道大分类讨论。

如果有一个可以交换的段包含奇数，那么你可以把所有奇数移到最左边并任意调整相对顺序，然后回到任意一种有一个可以交换的段包含奇数的状态。这种情况，如果偶数的数量为 \(2\)，这两个偶数是不能交换相对位置的，有至少 \(3\) 个偶数就能交换偶数间相对位置。所以只需要判断 \(a\) 和 \(b\) 中的数是否相同以及两个偶数的相对位置即可。

如果没有一个可以交换的段包含奇数，则所有奇数都不能移动，同时奇数把整个序列分成几段，每一段中如果只有 \(2\) 个偶数，那不能移动；如果有至少 \(3\) 个偶数，那么块内的偶数是可以移动的。所以要判断 \(a\) 是奇数的位置和 \(b\) 是否相同，然后在每一段内判断 \(a\) 和 \(b\) 中的数是否相同以及两个偶数的段是否位置对应相同。

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, a[N], b[N];
int cnt[N];

bool check(int l, int r)
{
	if(l > r) return false;
	if(l == r && a[l] == a[r]) return false;
	if(r - l == 1)
	{
		if(a[l] == b[l] && a[r] == b[r]) return false;
		else return true;
	}
	for(int i = l; i <= r; i ++ ) cnt[a[i]] ++ ;
	for(int i = l; i <= r; i ++ )
	{
		if(!cnt[b[i]]) return true;
		cnt[b[i]] -- ;
	}
	return false;
}

int main()
{
	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]);
	
	bool flag = true;
	for(int i = 1; i <= n - 2; i ++ )
		if((a[i] + a[i + 1] + a[i + 2]) % 2 == 0 && (a[i] % 2 || a[i + 1] % 2))
			flag = false;
	
	if(flag)
	{
		for(int i = 1; i <= n; i ++ )
			if(a[i] % 2 && a[i] != b[i])
			{
				puts("No");
				return 0;
			}
		int l = 1;
		for(int i = 1; i <= n; i ++ )
			if(a[i] % 2)
			{
				if(check(l, i - 1))
				{
					puts("No");
					return 0;
				}
				l = i + 1;
			}
		if(check(l, n)) puts("No");
		else puts("Yes");
	}
	else
	{
		if(check(1, n)) puts("No");
		else
		{
			bool flag = true;
			for(int i = 1; i <= n - 2; i ++ )
				if((b[i] + b[i + 1] + b[i + 2]) % 2 == 0 && (b[i] % 2 || b[i + 1] % 2))
					flag = false;
			if(flag) puts("No");
			else
			{
				int oc = 0;
				for(int i = 1; i <= n; i ++ )
					if(a[i] % 2 == 0)
						oc ++ ;
				if(oc != 2) puts("Yes");
				else
				{
					int fo;
					for(int i = 1; i <= n; i ++ )
						if(a[i] % 2 == 0)
						{
							fo = a[i];
							break;
						}
					for(int i = 1; i <= n; i ++ )
						if(b[i] % 2 == 0)
						{
							if(b[i] == fo) puts("Yes");
							else puts("No");
							return 0;
						}
				}
			}
		}
	}
	return 0;
}