C. Vasya and Multisets

传送门

[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;

}

巴特西

C. Vasya and Multisets

传送门

题意

分析

代码

最新文章

热门文章