传送门
[http://codeforces.com/contest/1051/problem/C]
题意
给你一堆数,问是否可以分为两堆使得两堆里只出现一下的数字的种类相等,可以输出任意一种分的方式
分析
具体看代码
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("in.txt","r",stdin);
int n,i;
int a[110],b[110];
while(cin>>n){
memset(b,0,sizeof(b));
for(i=0;i<n;i++){
cin>>a[i];
b[a[i]]++;//统计每个数字的个数
}
int cnt=0;
bool f=false,t=false;
for(i=1;i<=100;i++){
if(b[i]==1)
cnt++;//统计个数为1的种类数
if(b[i]>2) f=true;//看有没有个数大于2的
}
int h=1;
if(cnt%2==0)//如果个数为1的数字种类为偶数肯定可以分为两个集合均即可
{//剩下的大于等于2的随便扔进那一堆
cout<<"YES\n";
for(i=0;i<n;i++){
if(b[a[i]]>1) cout<<'A';
else if(b[a[i]]==1&&h==1){
cout<<'A';
h*=-1;
}
else if(b[a[i]]==1&&h==-1){
cout<<'B';
h*=-1;
}
}
cout<<endl;
}
else if(cnt%2==1&&f){//只有个数为1的数字种类为奇数且有个数大于2的才可以均分
cout<<"YES\n";//具体操作把一个大于2的一个拿来凑使得个数为1的数字种类为偶数,剩下的大于等于2的随便扔进那一堆
for(i=0;i<n;i++){
if(b[a[i]]==2) cout<<'A';
else if(b[a[i]]>2&&t){
cout<<'A';
}
else if(b[a[i]]>2&&!t){
cout<<'B';
t=true;
}
else if(b[a[i]]==1&&h==1){
cout<<'A';
h*=-1;
}
else if(b[a[i]]==1&&h==-1){
cout<<'B';
h*=-1;
}
}
cout<<endl;
}
else cout<<"NO\n";//剩下皆不可以均分为俩个集合
}
return 0;
}