子集mex值（冬季每日一题 29）

给定一组 $n$ 个整数的集合 $a_1,a_2,\dots ,a_n$（可能存在相同元素）。

请你将该集合分为两个子集 $A$ 和 $B$（子集可以为空，也可以包含相同元素）。

要求 $mex(A)+mex(B)$ 的值尽可能大。

一个集合的 $mex$ 值等于集合中不存在的最小非负整数的值，例如：

• $mex(1,4,0,2,2,1)=3$
• $mex(3,3,2,1,3,0,0)=4$
• $mex(\varnothing )=0$

如果集合中的任意整数 $x$ 均满足 $x$ 在该集合中的出现次数等于 $x$ 在 $A$ 中出现的次数与 $x$ 在 $B$ 中出现的次数之和，则我们认为该集合被分成了 $A$ 和 $B$ 两个子集。

输入格式
第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$。

输出格式
每组数据输出一行一个结果，表示 mex(A)+mex(B) 的最大值。

数据范围
$1\le T\le 100,$
$1\le n\le 100,$
$0\le a_i\le 100$
输入样例：

4
6
0 2 1 5 0 1
3
0 1 2
4
0 2 0 1
6
1 2 3 4 5 6

输出样例：

5
3
4
0

样例解释
在第一个测试用例中，$A=0,1,2,B=0,1,5$ 是一个可能的选择。

在第二个测试用例中，$A=0,1,2,B=\varnothing$ 是一个可能的选择。

在第三个测试用例中，$A=0,1,2,B=0$ 是一个可能的选择。

在第四个测试用例中，$A=1,3,5,B=2,4,6$ 是一个可能的选择。

#include<iostream>
#include<cstring>

using namespace std;

const int N = 110;

int n;
bool a[N], b[N];

int main(){
    
    
    int t;
    cin >> t;
    int x;
    while(t--){
        
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        cin >> n;
        for(int i = 0; i < n; i++){
            cin >> x;
            if(a[x]) b[x] = true;
            else a[x] = true;
        }
        
        int sa = 0, sb = 0;
        while(a[sa]) sa++;
        while(b[sb]) sb++;
        cout << sa + sb << endl;
    }
    
    
    return 0;
}

最后

以上就是愤怒大雁为你收集整理的子集mex值（冬季每日一题 29）的全部内容，希望文章能够帮你解决子集mex值（冬季每日一题 29）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。