题目链接:https://cn.vjudge.net/problem/CodeForces-1051C

https://cn.vjudge.net/problem/1889683/origin

题目

万圣节到了,杰哥准备给班级里的同学发糖吃,男生女生各一堆。于是他去腐败街的xx小卖部买糖,他认为糖只要是独一无二的那他就是好糖,他跟老板说他想要买n个不一样的糖,但是老板是个黑心商贩,当杰哥把糖带回去的时候才发现有挺多相同的糖
而杰哥是一个公平正直的人,他希望男生女生两堆糖中好糖的数量相同,于是他想找你帮忙来解决他的烦恼。
为了简化问题我们将不同的糖用不用的数字表示。

Input

第一行输入一个整数 n(2<=n<=100)
第二行输入n个整数 s1,s2,...sn(1<=si<=100)表示第i个糖是哪种糖

Output

如果杰哥无法将这些糖合理的分成2份则输出一行"NO"
如果可以 则输出一行"YES"下一行输出n个字符,第i个字符表示第i个糖属于男生还是女生(女生输出A,男生输出B)
情况有多种,任选一种情况输出即可。

Examples

Input

4
3 5 7 1

Output

YES
BABA

Input

3
3 5 1

Output

NO

题目大意:杰哥买想买一些独一无二的好糖(只要在一堆中是唯一的就是好糖),但是老板给了他存在相同的糖,但是他要些这些糖分给两堆,使每堆的好糖都相等。


思路:只要在一堆中是唯一就是好糖,如果原来的糖果在买来的那一堆中是好糖的个数是m个,那么如果m%2=0;把好糖平分一下,不论把剩余不是好糖的糖全部分给谁都无所谓。要是如果m%2!=0,那么,你要判断一下糖果个数不为一个和两个(就是大于数目两个的糖)的糖存不存在(为什么两个不行:两个你拆开一个之后,那么另一个就变成了好糖,所以不能使好糖是数目增加),如果存在那么分一个出来,放在一堆中使他成为好糖,其余放在另一堆那他就不是就不是好糖。要是不存在个数大于两个的,那就输出“NO”。
 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int a[105];
int b[105];
int c[105];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        b[a[i]]++;
    }
    int w=-1;

    int m=1;
    int u=-1;
    for(int i=1; i<102; i++)
    {
        if(b[i]==1)
        {
            c[m++]=i;
        }
        if(w<b[i])
        {
            w=b[i];
            u=i;
        }
    }
    if(m%2==0&&w<3)
    {
        printf("NO\n");
    }
    else
    {
        printf("YES\n");
        for(int i=1; i<=n; i++)
        {
            int flog=0;
            for(int j=1; j<m; j++)
            {
                if(a[i]==c[j])
                {
                    flog=1;
                    if(j%2==1)
                    {
                        printf("A");
                    }
                    else
                    {
                        printf("B");
                    }
                    break;
                }
            }
            if(a[i]==u&&flog==0&&m%2==0)
            {
                flog==1;
                u=-1;
                printf("B");
            }
            else if(flog==0)
            {
                printf("A");
            }
        }
        printf("\n");
    }
    return 0;
}