codeforces edu #51 C. Vasya and Multisets (思维题)
题意:有n个数，现在要分成2个集合，使得2个集合中，仅出现1次的数的个数相同，问是否有解，以及具体的分法。
思路:
一开始考虑出现多个的数的思路麻烦了，比如对于出现2次的某个数x，与其一个集合中分得一个，使得两个结合中，仅出现1次的数的个数各+1，还不如都放在同一个集合中，使得仅出现1次的数的个数不增加。
因此思路是这样的:
先考虑出现1次的数的个数，如果为偶数，那么均分，然后把其他出现多次的数全都放在第一个集合；
如果出现1次的数的个数为奇数，我们还是尽可能均分，然后不妨假设第一个集合中的只出现1次的数的个数比第二个集合中多1个。
我们现在需要让第二个集合中，仅出现一次的数增加一个。
什么样的数可以满足这个条件呢？ 出现2次的数是不行的，因为这会使得两个集合中的数字各自+1
因此需要至少有一个出现3次或者以上的数。
具体见代码:
1/* ***********************************************
2Author :111qqz
3mail: renkuanze@sensetime.com
4Created Time :2018年10月02日 星期二 15时28分39秒
5File Name :c.cpp
6************************************************ */
7#include <bits/stdc++.h>
8#define ms(a,x) memset(a,x,sizeof(a))
9typedef long long LL;
10#define pi pair < int ,int >
11#define MP make_pair
12using namespace std;
13const double eps = 1E-8;
14const int dx4[4]={1,0,0,-1};
15const int dy4[4]={0,-1,1,0};
16const int inf = 0x3f3f3f3f;
17const int N=105;
18int n;
19int cnt[N];
20int a[N];
21string ans="";
22int main()
23{
24 #ifndef ONLINE_JUDGE
25 // freopen("./in.txt","r",stdin);
26 #endif
27 cin>>n;
28 ms(cnt,0);
29 for ( int i = 1; i <= n ; i++)
30 {
31 cin>>a[i];
32 cnt[a[i]]++;
33 }
34 int cnt_1 = 0;
35 for ( int i = 1 ; i <= 100 ; i++)
36 {
37 if (cnt[i]==1) cnt_1++;
38 }
39 int cur_1 = 0 ;
40 for ( int i = 1 ;i <= n ; i++)
41 {
42 if (cnt[a[i]]>=2)
43 {
44 ans+='A';
45 }
46 if (cnt[a[i]]==1)
47 {
48 cur_1++;
49 if (cur_1<=(cnt_1+1)/2)
50 {
51 ans+='A';
52 }
53 else
54 {
55 ans+='B';
56 }
57 }
58 }
1 if (cnt_1%2==0)
2 {
3 puts("YES");
4 cout<<ans<<endl;
5 }
6 else
7 {
8 bool triple = false;
9 for ( int i = 1; i <= n ; i++)
10 {
11 if (cnt[a[i]]>=3&&!triple)
12 {
13 triple = true;
14 ans[i-1] = 'B';
15 }
16 }
17 if (triple)
18 {
19 puts("YES");
20 cout<<ans<<endl;
21 }
22 else
23 {
24 puts("NO");
25 }
26 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}