codeforces edu #51 C. Vasya and Multisets (思维题)

Posted by 111qqz on Tuesday, October 2, 2018

TOC

题目链接

题意:有n个数,现在要分成2个集合,使得2个集合中,仅出现1次的数的个数相同,问是否有解,以及具体的分法。

思路:

一开始考虑出现多个的数的思路麻烦了,比如对于出现2次的某个数x,与其一个集合中分得一个,使得两个结合中,仅出现1次的数的个数各+1,还不如都放在同一个集合中,使得仅出现1次的数的个数不增加。

因此思路是这样的:

先考虑出现1次的数的个数,如果为偶数,那么均分,然后把其他出现多次的数全都放在第一个集合;

如果出现1次的数的个数为奇数,我们还是尽可能均分,然后不妨假设第一个集合中的只出现1次的数的个数比第二个集合中多1个。

我们现在需要让第二个集合中,仅出现一次的数增加一个。

什么样的数可以满足这个条件呢? 出现2次的数是不行的,因为这会使得两个集合中的数字各自+1

因此需要至少有一个出现3次或者以上的数。

具体见代码:

/* ***********************************************
Author :111qqz
mail: renkuanze@sensetime.com
Created Time :2018年10月02日 星期二 15时28分39秒
File Name :c.cpp
************************************************ */
#include <bits/stdc++.h>
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=105;
int n;
int cnt[N];
int a[N];
string ans="";
int main()
{
        #ifndef  ONLINE_JUDGE 
    //    freopen("./in.txt","r",stdin);
  #endif
        cin>>n;
        ms(cnt,0);
        for ( int i = 1; i <= n ; i++)
        {
            cin>>a[i];
            cnt[a[i]]++;
        }
        int cnt_1 = 0;
        for ( int i = 1 ; i <= 100 ; i++)
        {
            if (cnt[i]==1) cnt_1++;
        }
        int cur_1 = 0 ;
        for ( int i = 1 ;i  <= n ; i++)
        {
            if (cnt[a[i]]>=2)
            {
                ans+='A';
            }
            if (cnt[a[i]]==1)
            {
                cur_1++;
                if (cur_1<=(cnt_1+1)/2)
                {
                    ans+='A';
                }
                else
                {
                    ans+='B';
                }
            }
        }

        if (cnt_1%2==0)
        {
            puts("YES");
            cout<<ans<<endl;
        }
        else
        {
            bool triple = false;
            for ( int i = 1; i <= n ; i++)
            {
                if (cnt[a[i]]>=3&&!triple)
                {
                    triple = true;
                    ans[i-1] = 'B';
                }
            }
            if (triple)
            {
                puts("YES");
                cout<<ans<<endl;
            }
            else
            {
                puts("NO");
            }
        }
			




  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付