CodeForces 1051c-Vasya and Multisets

桃扇骨 2022-02-15 13:37 153阅读 0赞

题目衔接：[http://codeforces.com/problemset/problem/1051/C][http_codeforces.com_problemset_problem_1051_C]

> C. Vasya and Multisets
> 
> time limit per test
> 
> 1 second
> 
> memory limit per test
> 
> 256 megabytes
> 
> input
> 
> standard input
> 
> output
> 
> standard output
> 
> Vasya has a multiset ss consisting of nn integer numbers. Vasya calls some number xx nice if it appears in the multiset exactly once. For example, multiset \{1,1,2,3,3,3,4\}\{1,1,2,3,3,3,4\} contains nice numbers 22 and 44.
> 
> Vasya wants to split multiset ss into two multisets aa and bb (one of which may be empty) in such a way that the quantity of nice numbers in multiset aa would be the same as the quantity of nice numbers in multiset bb (the quantity of numbers to appear exactly once in multiset aaand the quantity of numbers to appear exactly once in multiset bb).
> 
> Input
> 
> The first line contains a single integer n (2≤n≤100)n (2≤n≤100).
> 
> The second line contains nn integers s1,s2,…sn (1≤si≤100)s1,s2,…sn (1≤si≤100) — the multiset ss.
> 
> Output
> 
> If there exists no split of ss to satisfy the given requirements, then print "NO" in the first line.
> 
> Otherwise print "YES" in the first line.
> 
> The second line should contain a string, consisting of nn characters. ii-th character should be equal to 'A' if the ii-th element of multiset ssgoes to multiset aa and 'B' if if the ii-th element of multiset ss goes to multiset bb. Elements are numbered from 11 to nn in the order they are given in the input.
> 
> If there exist multiple solutions, then print any of them.

> Examples
> 
> input
> 
> 4
> 
> 3 5 7 1
> 
> output
> 
> YES
> 
> BABA
> 
> input
> 
> 3
> 
> 3 5 1
> 
> output
> 
> NO

题目大意：给你n个数字，其中只出现一次的是好数，现在把这些数分成两个部分其中好数的数量都相同（注意如果这个数不是好数，我们可以分开放放到两个集合中，这样也是好数）  
思路：首先统计好数的个数，与出现次数大于3的数的个数然后：  
 若集合中好数的数量为奇数，并且其它数的出现次数均小于3，那么无法满足要求。

若集合中好数的数量为奇数，则从其它数中取一个出现次数大于或等于3的数，将其中一个与其余分别分配到不同的集合，那么这个数在只有一个被分配到的集合中也是好数，此时可以分配的好数总数量为偶数，平均分配即可；我们在实现的时候可以将出现次数大于3的数的最后一次出现放在另一个集合中，且分配完一个出现次数大于3的数后，对后面再出现出现次数大于3则直接分配。具体操作看代码；

若集合中好数的数量为偶数，则平均分配到两个集合，其它数均分配到同一个集合；  
代码有些复杂，但是好懂

代码：

/*
    题目大意：给你n个数字，其中只出现一次的是好数，
    现在把这些数分成两个部分其中好数的数量都相同（注意如果这个数不是好数，我们可以分开放，这样也是好数）
    思路：若集合中好数的数量为偶数，则平均分配到两个集合，其它数均分配到同一个集合；
          若集合中好数的数量为奇数，则从其它数中取一个出现次数大于或等于3的数，将其中一个与其余分别分配到不同的集合，那么这个数在只有一个被分配到的集合中也是好数，此时可以分配的好数总数量为偶数，平均分配即可；
          若集合中好数的数量为奇数，并且其它数的出现次数均小于3，那么无法满足要求。
    */
    #include<map>
    #include<set>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    const int maxn=1e4+100;
    const double pi=acos(-1.0);
    const int N=1100;
    const int mod=1e9+7;
    int num[maxn];
    int book[maxn];
    int a[maxn];
    int main()
    {
        int n;
        cin>>n;
        for(int i=0; i<n; i++)
        {
            cin>>a[i];
            num[a[i]]++;
        }
        int sum1=0,sum2=0,sum3=0;///分别用于统计出现次数为1，出现次数为2，出现次数大于2的数的个数
        for(int i=1; i<110; i++)
        {
            if(num[i]==1)
                sum1++;
            else if(num[i]==2)
                sum2++;
            else if(num[i]>2)
                sum3++;
        }
        if(sum1%2&&sum3==0)///好数个数为奇数且没有出现出现次数大于3的数
        {
            printf("NO\n");
            return 0;
        }
        if(sum1%2&&sum3)///好数个数为一,把出现次数为3的数分成两部分：1 num-1，分别放入不同集合
        {
            printf("YES\n");
            int flag=0,mark=0;
            for(int i=0; i<n; i++)
            {
                if(num[a[i]]==1&&!flag)///出现次数为1，且flag标记为0输出A
                {
                    printf("A");
                    flag=1;
                    continue;
                }
                if(num[a[i]]==1&&flag)
                {
                    printf("B");
                    flag=0;
                    continue;
                }
                if(num[a[i]]==2)
                {
                    printf("A");
                    continue;
                }
                if(num[a[i]]>2&&book[a[i]]<num[a[i]]-1&&mark==0)///出现次数为大于3，且不是最后一次出现
                {
                    printf("A");
                    book[a[i]]+=1;
                    continue;
                }
                if(num[a[i]]>2&&num[a[i]]-book[a[i]]==1&&mark==0)///出现次数为3，且是最后一次出现
                {
                    printf("B");
                    mark=1;
                    continue;
                }
                else
                    printf("A");
    
            }
            printf("\n");
            return 0;
        }
        if(sum1%2==0)
        {
            int flag=0;
            printf("YES\n");
            for(int i=0; i<n; i++)
            {
                if(num[a[i]]==1&&!flag)
                {
                    printf("A");
                    flag=1;
                    continue;
                }
                if(num[a[i]]==1&&flag)
                {
                    printf("B");
                    flag=0;
                    continue;
                }
                else if(num[a[i]]>1)
                    printf("A");
            }
            printf("\n");
        }
        return 0;
    }

[http_codeforces.com_problemset_problem_1051_C]: http://codeforces.com/problemset/problem/1051/C