题目描述

难度分:$1500$

输入$n(2 \leq n \leq 100)$和长为$n$的数组$s(1 \leq s[i] \leq 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

算法

动态规划

这个题直接从怎么去分配$s$中的元素来考虑的话不太好做，但如果对$s$中不同的值来考虑就会容易很多。可以先将数组$s$备份一份，并进行去重，设排序去重后的数组为$a$，去重后的元素个数为$m$，对每个值用DP来进行分配。

状态定义

$f[i][t_1][t_2]$表示考虑到第$i$个元素，第一组有$t_1$个不同的元素，第二组有$t_2$个不同的元素的情况下，子数组$[i,n]$上是否能够完成题目所要求的分配，使得最终有$t_1=t_2$成立。

状态转移

1. 如果此时$a[i]$的频数为$1$，那么将它分配给第一组，就会为第一组不同数的个数增加$1$；分配给第二组，就会为第二组不同数的个数增加$1$。此时，状态转移方程为$f[i][t_1][t_2]=f[i+1][t_1+1][t_2] \lor f[i+1][t_1][t_2+1]$。
2. 否则就存在三种情况：$(1)$ $a[i]$全部分配给其中的某一组，这样由于$a[i]$不止一个，对两个组的不同元素个数都不会有贡献（也可以不这样分配，但是肯定存在一种方案，使对两组都没有贡献）。$(2)$ 将一个$a[i]$分配给第一组，其余的分配给第二组，此时肯定会对第一组产生贡献，但只有在$a[i]$的频数为$2$的情况下才会对第二组也产生贡献。$(3)$ 对称的，将一个$a[i]$分配给第二组，其余的分配给第一组，此时肯定会对第二组产生贡献，但只有在$a[i]$的频数为$2$的情况下才会对第一组也产生贡献。以上三种情况有任何一种成立，就可以让$f[i][t_1][t_2]=$true。

动态规划完成之后，只需要利用$f$数组，DFS检查一下每个状态是从哪个状态转移过来的就可以递推出一个合理的方案，每一种转移都对应一种数值的分配策略。

复杂度分析

时间复杂度

状态的数量为$O(n^3)$级别，单次转移的时间复杂度为$O(1)$。DFS还原方案时由于每次只会走一个分支，所以时间复杂度是线性的，最后遍历一遍原数组$s$输出最终方案的时间复杂度也是线性的。因此，算法整体的时间复杂度就是$O(n^3)$。

空间复杂度

空间的瓶颈就在于$f$数组，是$O(n^3)$级别，这也是本解法的额外空间复杂度。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 101;
int n, m, a[N], b[N], cnt[N];
bool st[N];
int f[N][N][N];
int A[N], B[N];

int dfs(int i, int t1, int t2) {
    if(i > m) {
        return f[i][t1][t2] = t1 == t2? 1: 0;
    }
    int &v = f[i][t1][t2];
    if(v != -1) return v;
    if(cnt[a[i]] == 1) {
        // a[i]分给第一组
        int res1 = dfs(i + 1, t1 + 1, t2);
        if(res1 == 1) return v = 1;
        // a[i]分给第二组
        int res2 = dfs(i + 1, t1, t2 + 1);
        return v = res2;
    }else {
        // 所有a[i]分配给某一个组
        int res1 = dfs(i + 1, t1, t2);
        if(res1 == 1) return v = 1;
        // 一个a[i]分配给第一组，剩下的分配给第二组
        int res2 = dfs(i + 1, t1 + 1, t2 + (cnt[a[i]] == 2? 1: 0));
        if(res2 == 1) return v = 1;
        // 一个a[i]分配给第二组，剩下的分配给第一组
        int res3 = dfs(i + 1, t1 + (cnt[a[i]] == 2? 1: 0), t2 + 1);
        return v = res3;
    }
}

void dfs1(int i, int t1, int t2) {
    if(i > m) return;
    if(f[i + 1][t1 + 1][t2] == 1) {
        A[a[i]] = 1;
        B[a[i]] = cnt[a[i]] - 1;
        dfs1(i + 1, t1 + 1, t2);
    }else if(f[i + 1][t1][t2 + 1] == 1) {
        B[a[i]] = 1;
        A[a[i]] = cnt[a[i]] - 1;
        dfs1(i + 1, t1, t2 + 1);
    }else if(f[i + 1][t1 + 1][t2 + 1] == 1) {
        A[a[i]] = 1;
        B[a[i]] = 1;
        dfs1(i + 1, t1 + 1, t2 + 1);
    }else if(f[i + 1][t1][t2] == 1) {
        // a[i]不会做任何贡献，全部分配给一组就行
        A[a[i]] = cnt[a[i]];
        B[a[i]] = 0;
        dfs1(i + 1, t1, t2);
    }
}

int main() {
    scanf("%d", &n);
    memset(cnt, 0, sizeof cnt);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
        cnt[a[i]]++;
    }
    sort(a + 1, a + n + 1);
    m = unique(a + 1, a + n + 1) - a - 1;     // 去重后的数组
    memset(f, -1, sizeof(f));
    int res = dfs(1, 0, 0);
    if(res) {
        puts("YES");
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        dfs1(1, 0, 0);
        memset(st, 0, sizeof(st));
        for(int i = 1; i <= n; i++) {
            if(A[b[i]] > 0) {
                cout << 'A';
                A[b[i]]--;
            }else if(B[b[i]] > 0) {
                cout << 'B';
                B[b[i]]--;
            }
        }
    }else {
        puts("NO");
    }
    return 0;
}