CF1406A.Subset Mex
入门
通过率:0%
时间限制:1.00s
内存限制:512MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Given a set of integers (it can contain equal elements).
You have to split it into two subsets A and B (both of them can contain equal elements or be empty). You have to maximize the value of mex(A)+mex(B).
Here mex of a set denotes the smallest non-negative integer that doesn't exist in the set. For example:
- mex(1,4,0,2,2,1)=3
- mex(3,3,2,1,3,0,0)=4
- mex(∅)=0 (mex for empty set)
The set is splitted into two subsets A and B if for any integer number x the number of occurrences of x into this set is equal to the sum of the number of occurrences of x into A and the number of occurrences of x into B.
给定一个整数集合(其中可能包含相等的元素)。
你需要将它划分为两个子集 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(∅)=0(空集的 mex 为 0)
当且仅当对任意整数 x,其在整个集合中的出现次数等于其在 A 中的出现次数与在 B 中的出现次数之和时,该集合被划分为子集 A 和 B。
输入格式
The input consists of multiple test cases. The first line contains an integer t (1≤t≤100) — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer n (1≤n≤100) — the size of the set.
The second line of each testcase contains n integers a1,a2,…an (0≤ai≤100) — the numbers in the set.
输入包含多个测试用例。第一行包含一个整数 t(1≤t≤100),表示测试用例的数量。随后是各测试用例的描述。
每个测试用例的第一行包含一个整数 n(1≤n≤100),表示集合的大小。
每个测试用例的第二行包含 n 个整数 a1,a2,…an(0≤ai≤100),表示集合中的数字。
输出格式
For each test case, print the maximum value of mex(A)+mex(B).
对于每个测试用例,输出 mex(A)+mex(B) 的最大值。
输入输出样例
输入#1
4 6 0 2 1 5 0 1 3 0 1 2 4 0 2 0 1 6 1 2 3 4 5 6
输出#1
5 3 4 0
说明/提示
In the first test case, A=\left{0,1,2\right},B=\left{0,1,5\right} is a possible choice.
In the second test case, A=\left{0,1,2\right},B=\varnothing is a possible choice.
In the third test case, A=\left{0,1,2\right},B=\left{0\right} is a possible choice.
In the fourth test case, A=\left{1,3,5\right},B=\left{2,4,6\right} is a possible choice.
在第一个测试用例中,A={0,1,2},B={0,1,5} 是一种可行的选择。
在第二个测试用例中,A={0,1,2},B=∅ 是一种可行的选择。
在第三个测试用例中,A={0,1,2},B={0} 是一种可行的选择。
在第四个测试用例中,A={1,3,5},B={2,4,6} 是一种可行的选择。
输入解题思路,AI测评打分。不知道怎么写?