HDU - 2018杭电ACM集训队单人排位赛 - 4 - Problem C. Sequence

C — Sequence

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 0    Accepted Submission(s): 0

Problem Description

As we all know, Sister Ye is good at Graph Theory. Now he is intending to examine your Graph Theory level. Sister Ye would show you a degree sequence and ask you to find a simple graph that satisfies the sequence of degrees. Because the graph may be too large, you have to answer if such a graph exists or not only. In order to prevent you from guessing, Sister Ye will ask you more than once.

Input

The first line contains an integer T, the times Sister Ye ask you.

Each question will begin with a line contains an integer n, the size of sequence.

The following line contains a degree sequence a1,...,an.

Output

You should answer 'Y'(yes) or 'N'(no) for each question in one line.

1 ≤ T ≤ 50.

1 ≤ n ≤ 100000.

1 ≤ ai ≤ 10^9.

Sample Input

2

1

1

3

2 1 1

Sample Output

N

Y

Hint

loop:a loop is an edge that connects a vertex to itself.

simple graph: a graph without loops and multiple edges between two vertexes.

degree:the degree of a vertex in a graph is the number of edges connected to the vertex.

degree sequence: An integer sequence of the degrees for each vertex in the graph.

解题思路：给定一组节点的度序列来判断一个图是否为简单图？（符合以下两点即可）

每个节点度数要小于节点个数

该图具有偶数个奇数度的节点

AC 代码

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=100010;
int n,a[maxn];
bool ok()
{
    int sum=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]%2==1) sum++;
        if(a[i]>=n) return 0;
    }
    if(sum%2==1) return 0;
    return 1;
}
int main()
{
    int T; scanf("%d",&T);
    while(T-- && ~scanf("%d",&n))
    {
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        puts(ok()?"Y":"N");
    }
    return 0;
}