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; }
