codeforce每日一题
题目链接
题目分数:1500
题目描述
输入$n(2<=n<=100)$和长为$n$的数组$s(1<s[i]<=100)$。把$s$ 分成两个子序列$A$和$B$(子序列可以为空),使得$A$里面只出现一次的数的个数,等于$B$里面只出现一次的数的个数。如果无法做到,输出$NO$。否则输出$YES$以及方案(见样例)。注意$s$ 中可能有重复元素。
样例
输入样例1
4
3 5 7 1
输出样例1
YES
BABA
输入样例2
3
3 5 1
输出样例2
NO
算法
(暴力枚举) $O(n^2)$
找到出现一次的数字个数x和出现两次以上的数字个数y,如果x为偶数,就一半给A,一半给B就好了;如果x为奇数,就x/2给A,x/2+1给B,再从y中找一个数字给A,其余数字都填A就行。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 110, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int w[N];
char res[N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
rep(i, 1, n) cin>>w[i];
map<int,int> ma;
rep(i, 1, n) ma[w[i]] ++;
int a = 0, b = 0;
for(auto &[x, y] : ma)
if(y == 1) a++;
else if(y >= 3) b++;
if(a%2==0 || a%2 && b){
if(a%2)
{
for(auto &[x, y] : ma)
{
if(y >= 3)
{
for(int i=0;i<n;i++)
if(w[i] == x){
res[i] = 'B';
break;
}
break;
}
}
}
int mid = a / 2;
for(auto [x, y] : ma)
{
if(y == 1)
{
if(a > mid)
{
for(int i=1;i<=n;i++)
if(!res[i] && w[i] == x){
res[i] = 'A';
a--;
break;
}
}else{
for(int i=1;i<=n;i++)
if(!res[i] && w[i] == x){
res[i] = 'B';
a--;
break;
}
}
}
}
for(int i=1;i<=n;i++)
if(!res[i]) res[i] = 'A';
cout<<"YES"<<endl;
for(int i=1;i<=n;i++) cout<<res[i];
cout<<endl;
}else cout<<"NO"<<endl;
return 0;
}