题解 T93283 【集合】

传送门

考虑如何将s中的每种数分到$a$和$b$集中

假设一个数$x$有$k$个，可以对$a$和$b$集“好的”数的个数差产生什么影响？

$k=1$

• 让一个集合“好的”数个数++，另一集合的个数不变

$k=2$

• 让两个集合“好的”数个数都++

• 让两个集合“好的”数个数不变

$k>2$

• 让一个集合“好的”数个数++，另一集合的个数不变

• 让两个集合“好的”数个数不变

因此$k=2$的情况对答案没有影响

$k=1$的$x$会使两个集合的差别++，$k>2$的$x$可以起到“平衡”的作用

可如下分类讨论：

• $k=1$的数个数为偶数，平均分到两组即可。其它的数可以不产生影响。

• $k=1$的数个数为奇数，必然有一个集合多出一个。

  • 如果存在$k>2$的数，那么可以平衡这多出的一个。

  • 否则是唯一的无解情况。

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

int n, a[105], cnt[105];

int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		memset(cnt, 0, sizeof(cnt));
		scanf("%d", &n);
		for(int i = 1; i <= n; i++)
		{
		    scanf("%d", a + i);
		    cnt[a[i]]++;
		}
		int c1 = 0, c2 = 0;
		for(int i = 1; i <= 100; i++)
		{
			c1 += (cnt[i] == 1);
			c2 += (cnt[i] > 2);
		}
		if(c1 % 2 == 1 && !c2)
			puts("No");
		else
			puts("Yes");
	}
	return 0;
}