题解 CF1360C 【Similar Pairs】
rui_er
2020-05-25 13:35:44
结论题。
自己列了几次找了一下规律,发现有两个数差为 $1$ 则必定可以,否则看奇偶数的个数。
找规律思考过程:
1. 如果有两个数差为 $1$,则必有一奇一偶。
2. 奇数个数与偶数个数的奇偶性必然相同。(因为总数是偶数个)
3. 去掉所有差为一的数,剩余的数仍然满足 $2$。
4. 如果剩余的数中奇数个数和偶数个数均为奇数,则将一对差为一的数拿出用于奇偶数对。(如果没有差为一的数,就不可能完成)
5. 否则将剩余的数按照奇数、偶数分组即可。
综上,如果有差为一的数,肯定能完成任务;否则如果奇偶数个数为奇数,不能完成,为偶数可以完成。
代码:
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
int T, n, a[51];
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
int odd = 0, even = 0;
for(int i=1;i<=n;i++) {
scanf("%d", &a[i]);
if(a[i] & 1) {
++odd;
}
else {
++even;
}
}
sort(a+1, a+1+n);
bool book = false;
for(int i=2;i<=n;i++) {
if(a[i] - a[i-1] == 1) {
book = true;
break;
}
}
if(book) {
puts("YES");
}
else if(even % 2 == 0 && odd % 2 == 0) {
puts("YES");
}
else {
puts("NO");
}
}
return 0;
}
```