ARC 155（Even Sum Triplet）题解（施工中）
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
构造题思路简单但很多细节多的逆天 W A \mathcal{WA} WA 了一万遍忘了我吧
简单题意你可以做任意次如下操作。
选择一个 i i i满足 1 ≤ i ≤ n − 2 1 \leq i \leq n - 2 1≤i≤n−2, 且 a [ i ] + a [ i + 1 ] + a [ i + 2 ] a[i] + a[i + 1] + a[i + 2] a[i]+a[i+1]+a[i+2] 是一个偶数将 a [ i ] , a [ i + 1 ] , a [ i + 2 ] a[i],a[i + 1], a[i + 2] a[i],a[i+1],a[i+2] 随意排序回答 A A A 序列能否通过任意次操作变为 B B B。
三个数加起来为偶数只有可能是
1.偶数+偶数+偶数
2.偶数+奇数+奇数
结论一
相邻三个数有两个奇数一个偶数简称为可以组成一组的话两个奇数可以一起移动向左移动一位或者向右移动一位并且除去他们三个后的序列不变。
证明
容易构造出来一种方案无非分为两种情况。
只考虑向左移动向右同理。
令 a [ i ] a[i] a[i] 为偶数 a [ i + 1 ] , a [ i + 2 ] a[i + 1],a[i + 2] a[i+1],a[i+2]为奇数
1. 奇数,
a
[
i
]
,
a
[
i
+
1
]
,
a
[
i
+
2
]
a[i], a[i + 1], a[i + 2]
a[i],a[i+1],a[i+2]
a
[
i
−
1
]
,
a
[
i
]
,
a
[
i
+
1
]
,
a
[
i
+
2
]
→
a
[
i
+
1
]
,
a
[
i
]
,
a
[
i
−
1
]
,
a
[
i
+
2
]
→
a
[
i
+
1
]
,
a
[
i
+
2
]
,
a
[
i
]
,
a
[
i
−
1
]
→
a
[
i
]
,
a
[
i
+
1
]
,
a
[
i
+
2
]
,
a
[
i
−
1
]
a[i - 1], a[i], a[i + 1], a[i + 2] \\ \rightarrow a[i + 1],a[i],a[i - 1],a[i + 2] \\ \rightarrow a[i + 1],a[i + 2],a[i], a[i - 1] \\ \rightarrow a[i],a[i + 1], a[i + 2], a[i - 1]
a[i−1],a[i],a[i+1],a[i+2]→a[i+1],a[i],a[i−1],a[i+2]→a[i+1],a[i+2],a[i],a[i−1]→a[i],a[i+1],a[i+2],a[i−1]
a [ i ] , a [ i + 1 ] , a [ i + 2 ] a[i],a[i + 1],a[i + 2] a[i],a[i+1],a[i+2] 为新的一组
2. 偶数,
a
[
i
]
,
a
[
i
+
1
]
,
a
[
i
+
2
]
a[i],a[i + 1],a[i + 2]
a[i],a[i+1],a[i+2]
a
[
i
−
1
]
,
a
[
i
]
,
a
[
i
+
1
]
,
a
[
i
+
2
]
→
a
[
i
−
1
]
,
a
[
i
+
1
]
,
a
[
i
+
2
]
,
a
[
i
]
a[i - 1], a[i], a[i + 1], a[i + 2] \\ \rightarrow a[i - 1], a[i + 1], a[i + 2], a[i]
a[i−1],a[i],a[i+1],a[i+2]→a[i−1],a[i+1],a[i+2],a[i]
a [ i − 1 ] , a [ i + 1 ] , a [ i + 2 ] a[i - 1],a[i + 1],a[i + 2] a[i−1],a[i+1],a[i+2] 为新的一组
Ex·结论一
存在三个数可以组成一组的话奇数间相对顺序可以任意排列并且偶数间相对顺序不变。
由于相邻两项可以随意交换等价于任意排列这个序列冒泡排序,我们只需证明相邻两个奇数的相对顺序可以随意交换即可。
设想交换的两个奇数为 i , j i,j i,j k , k + 1 , k + 2 k,k +1,k + 2 k,k+1,k+2 为一组。
结论二
偶数+奇数+奇数这种类型任意变换都无法改变偶数间的相对顺序。
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define db double
#define LL long long
// #define int long long
#define PII pair <int, int>
#define ULL unsigned long long
#define MP(x,y) make_pair (x, y)
#define rep(i,j,k) for (int i = (j); i <= (k); i++)
#define per(i,j,k) for (int i = (j); i >= (k); i--)
template <typename T>
void read (T &x) {
x = 0; T f = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar ();
}
x *= f;
}
template <typename T, typename... Args>
void read (T &x, Args&... Arg) {
read (x), read (Arg...);
}
const int MaxPrint = 1000;
int Poi_For_Print, Tmp_For_Print[MaxPrint + 5];
template <typename T>
void write (T x) {
if (x == 0) {
putchar ('0');
return;
}
bool flag = (x < 0 ? 1 : 0);
x = (x < 0 ? -x : x);
while (x) Tmp_For_Print[++Poi_For_Print] = x % 10, x /= 10;
if (flag) putchar ('-');
while (Poi_For_Print) putchar (Tmp_For_Print[Poi_For_Print--] + '0');
}
template <typename T, typename... Args>
void write (T x, Args... Arg) {
write (x); putchar (' '); write (Arg...);
}
template <typename T, typename... Args>
void print (T x, char ch) {
write (x); putchar (ch);
}
template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
const int Maxn = 2 * 1e5;
int n, cnt1, cnt2;
int a[Maxn + 5], b[Maxn + 5];
int c[Maxn + 5], d[Maxn + 5];
int fk1, st1[Maxn + 5], fk2, st2[Maxn + 5];
signed main () {
// freopen ("C:\\Users\\BZ\\Desktop\\.vscode\\1.in", "r", stdin);
// freopen ("C:\\Users\\BZ\\Desktop\\.vscode\\1.out", "w", stdout);
read (n);
rep (i, 1, n)
read (a[i]), c[i] = a[i];
rep (i, 1, n)
read (b[i]), d[i] = b[i];
sort (c + 1, c + 1 + n);
sort (d + 1, d + 1 + n);
rep (i, 1, n)
if (c[i] != d[i]) {
printf ("No");
return 0;
}
rep (i, 1, n) {
if (a[i] & 1) cnt1++;
else cnt2++;
}
if (cnt2 >= 3) {
rep (i, 1, n - 1) {
if (((a[i] & 1) && (a[i + 1] & 1)) || (i + 2 <= n && (a[i] & 1) && (a[i + 2] & 1))) {
bool fl = 0;
rep (j, 1, n - 1) {
if (((b[j] & 1) && (b[j + 1] & 1)) || (j + 2 <= n && (b[j] & 1) && (b[j + 2] & 1))) {
fl = 1;
break;
}
}
if (fl == 1) printf ("Yes");
else printf ("No");
return 0;
}
}
//sort (a + 1, a + 1 + n)
int lst = 1;
rep (i, 1, n) {
if (a[i] & 1) {
if (a[i] != b[i]) {
printf ("No");
return 0;
}
if (i - lst >= 3) {
sort (a + lst, a + 1 + i - 1);
sort (b + lst, b + 1 + i - 1);
rep (j, lst, i - 1) {
if (a[j] != b[j]) {
printf ("No");
return 0;
}
}
}
else {
rep (j, lst, i - 1) {
if (a[j] != b[j]) {
printf ("No");
return 0;
}
}
}
lst = i + 1;
}
}
printf ("Yes");
}
else if (cnt2) {
rep (i, 1, n) {
if (!(a[i] & 1))
st1[++fk1] = a[i];
if (!(b[i] & 1))
st2[++fk2] = b[i];
}
rep (i, 1, fk1)
if (st1[i] != st2[i]) {
printf ("No");
return 0;
}
if (cnt1 >= 3) {
printf ("Yes");
}
else {
if (n == 4) {//2 + 2
bool fl1 = 0, fl2 = 0;
if ((a[1] & 1) && (a[4] & 1)) fl1 = 1;
if ((b[1] & 1) && (b[4] & 1)) fl2 = 1;
if (fl1 ^ fl2) {
if (fl1) {
rep (i, 1, n)
if (a[i] != b[i]) {
printf ("No");
return 0;
}
printf ("Yes");
}
else {
printf ("Yes");
}
}
else printf ("No");
}
else {//1 + 2
if (cnt1 == 2) printf ("Yes");
else {
rep (i, 1, n)
if (a[i] != b[i]) {
printf ("No");
return 0;
}
printf ("Yes");
}
}
}
}
else {
rep (i, 1, n)
if (a[i] != b[i]) {
printf ("No");
return 0;
}
printf ("Yes");
}
return 0;
}