题意：首先输入一个t，是样例数，然后输入一个n，表示有n个结点，下面有n-1个数，都是1和2，表示从第2个点开始到第n个点的选择，如果是1，表示这个点和前面所有的点中间建立一条边，2则是无操作，例如4 1 1 2，点2与点1相连，点3与点1点2相连，点4无操作。最后求是否构成完美匹配，完美匹配就是指每个点都配上对。
思路：奇数肯定不可以，然后相当于1可以消掉前面的2，如果前面没2，1就没用了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ll mod=1e9+7; 5 6 int a[100004]; 7 8 int main(){ 9 int t; 10 scanf("%d",&t); 11 while(t--){ 12 int n; 13 int s1=0; 14 scanf("%d",&n); 15 for(int i=1;i<n;i++) scanf("%d",&a[i]); 16 if(n%2==1){ 17 printf("No\n");continue; 18 } 19 for(int i=1;i<n;i++){ 20 if(a[i]==2) s1++; 21 else { 22 s1--; 23 s1=max(0,s1); 24 } 25 } 26 if(s1==0) printf("Yes\n"); 27 else printf("No\n"); 28 } 29 return 0; 30 }
原文：http://www.cnblogs.com/hhxj/p/6953397.html