CF1051C

FiraCode · 2022-09-29 11:11:18 · 题解

题意：

给你 n 个数，一个数是好的当且仅当它只出现了一次，给你一个序列，求是否可以把这个序列分成两组，是的他们好的的数字相同。

题解思路：

我们先排序，然后统计每个数字出现的次数，设 t1 为出现 1 次的数的个数，t2 为出现两次的数的个数，tn 表示出现了大于 2 的数的个数。

若他出现以此的数的个数是奇数，并且没有大于 2 的数的个数，那么就无解，输出 NO。

否则一定有解输出 YES。

然后我们分两种况来讨论，第一种情况是 t1 是偶数，那么若这个块的长度是 1 那么我们用一个 cnt 来计数，若 cnt == 1 则把他分给 A 否则分给 B，然后 cnt = 1 - cnt。

否则都给他分给 A 或者 B。

那么若 t1 是奇数，那么若这个块的长度是 1 那么我们用一个 cnt 来计数，若 cnt == 1 则把他分给 A 否则分给 B，然后 cnt = 1 - cnt。

若他的长度是 2 就直接都分给 A 或 B。

否则若是第一次长度 \ge 3，若当前的 cnt == 0 则第一个就分给 B 否则分给 A，然后后面的数字都分给 B 或 A(若上一次选了 A 那么后面就该给 B 反之亦然)。

然后 cnt = 1 - cnt。

若他不是第一次长度 \ge 3 就把他都给 A 或者都给 B。

CODE:

又臭又长的代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
pair<int, int> a[N];
int n;
char ans[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + 1 + n);
    int t1 = 0, t2 = 0, tn = 0;
    for (int i = 1; i <= n;) {
        int t = a[i].first;
        int sz = 0;
        int temp = i;
        while (a[i].first == t) {
            i ++;
            sz++;
        }
        if (sz == 1) {
            t1 ++;
        }
        else if (sz == 2) {        
            t2 ++;
        }else {
            tn ++;
        }
    }
    if (t1 & 1) {
        if (!tn) {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
    if (t1 & 1) {
        int cnt = 0;
        bool ok = false;
        for (int i = 1; i <= n;) {
            int sz = 0;
            int t = a[i].first;
            int id = a[i].second;
            int ttemp = i;
            while(a[i].first == t)
                i ++, sz ++;
            if (sz == 1) {
                if (cnt == 0)
                    ans[id] = 'B';
                else
                    ans[id] = 'A';
                cnt = 1 - cnt;
            }else if (sz == 2) {
                ans[id] = ans[a[ttemp + 1].second] = 'A';
            }else {
                if (!ok) {
                    char c = cnt == 0 ? 'B' : 'A';
                    ans[id] = c;
                    for (int j = 1; j < sz; ++j)
                        ans[a[ttemp + j].second] = c == 'A' ? 'B' : 'A';
                    cnt = 1 - cnt;
                    ok = true;
                }else {
                    for (int j = 1; j <= sz; ++j)
                        ans[a[ttemp + j - 1].second] = 'B';
                }
            }
        }
    }else {
        int cnt = 0;
        bool ok = false;
        for (int i = 1; i <= n;) {
            int sz = 0;
            int t = a[i].first;
            int id = a[i].second;
            int ttemp = i;
            while(a[i].first == t)
                i ++, sz ++;
            if (sz == 1) {
                if (cnt == 0)
                    ans[id] = 'B';
                else
                    ans[id] = 'A';
                cnt = 1 - cnt;
            }else if (sz == 2) {
                ans[id] = ans[a[ttemp + 1].second] = 'A';
            }else {
                for (int j = 1; j <= sz; ++j)
                    ans[a[ttemp + j - 1].second] = 'B';
            }
        }    
    }
    for (int i = 1; i <= n; ++i)
        cout << ans[i];
    return 0;
}