題意：

現有一個定義：（1）兩個數的奇偶性相同
（2）兩個數的差的絕對值為1 ，即|a-b|=1
滿足以上兩個條件之一，就可以說兩個數是相似的
先給你一個數組，讓你將數組內分成多組，每組兩個元素是否都相似。

題目：

We call two numbers x and y similar if they have the same parity (the same remainder when divided by 2), or if |x?y|=1. For example, in each of the pairs (2,6), (4,3), (11,7), the numbers are similar to each other, and in the pairs (1,4), (3,12), they are not.

You are given an array a of n (n is even) positive integers. Check if there is such a partition of the array into pairs that each element of the array belongs to exactly one pair and the numbers in each pair are similar to each other.

For example, for the array a=[11,14,16,12], there is a partition into pairs (11,12) and (14,16). The numbers in the first pair are similar because they differ by one, and in the second pair because they are both even.

Input
The first line contains a single integer t (1≤t≤1000) — the number of test cases. Then t test cases follow.

Each test case consists of two lines.

The first line contains an even positive integer n (2≤n≤50) — length of array a.

The second line contains n positive integers a1,a2,…,an (1≤ai≤100).

Output

For each test case print:

YES if the such a partition exists,
NO otherwise.
The letters in the words YES and NO can be displayed in any case.

Example

Input

7
4
11 14 16 12
2
1 8
4
1 1 1 1
4
1 2 5 6
2
12 13
6
1 6 3 10 5 8
6
1 12 3 10 5 8

Output

YES
NO
YES
YES
YES
YES
NO

Note

The first test case was explained in the statement.

In the second test case, the two given numbers are not similar.

In the third test case, any partition is suitable.

分析：

由于n為偶數，那么奇數個數和偶數個數奇偶性相同
（1）如果個數都為偶，直接各自配對
（2）如果個數為奇，我們只需要判斷是否存在一對奇數和偶數相差為1配對，如果找不到就NO

AC代碼：

#include<stdio.h> #include<cstring> #include<algorithm> using namespace std; int t,n,x,y,flag; int dp[60]; int main() {scanf("%d",&t);while(t--){x=y=flag=0;scanf("%d",&n);for(int i=0; i<n; i++){scanf("%d",&dp[i]);if(dp[i]%2) x++;}if(x%2==0)flag=1;sort(dp,dp+n);for(int i=1; i<n; i++)if(dp[i]-dp[i-1]==1){flag=1;break;}flag==1?printf("YES\n"):printf("NO\n");}return 0; }

總結

以上是生活随笔為你收集整理的Similar Pairs CodeForces - 1360C（图匹配+简单贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。