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 AA and BB (both of them can contain equal elements or be empty). You have to maximize the value of mex(A)+mex(B)mex(A)+mex(B).

Here mexmex 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)=3mex({1,4,0,2,2,1})=3
  • mex(3,3,2,1,3,0,0)=4mex({3,3,2,1,3,0,0})=4
  • mex(∅)=0mex(\varnothing)=0 (mexmex for empty set)

The set is splitted into two subsets AA and BB if for any integer number xx the number of occurrences of xx into this set is equal to the sum of the number of occurrences of xx into AA and the number of occurrences of xx into BB.

给定一个整数集合(其中可能包含相等的元素)。

你需要将它划分为两个子集 AA 和 BB(二者均可包含相等的元素,也可以为空)。你的目标是最大化 mex(A)+mex(B)mex(A)+mex(B) 的值。

此处,集合的 mexmex 表示不在该集合中的最小非负整数。例如:

  • mex(1,4,0,2,2,1)=3mex({1,4,0,2,2,1})=3
  • mex(3,3,2,1,3,0,0)=4mex({3,3,2,1,3,0,0})=4
  • mex(∅)=0mex(\varnothing)=0(空集的 mexmex 为 00)

当且仅当对任意整数 xx,其在整个集合中的出现次数等于其在 AA 中的出现次数与在 BB 中的出现次数之和时,该集合被划分为子集 AA 和 BB。

输入格式

The input consists of multiple test cases. The first line contains an integer tt (1≤t≤1001\leq t\leq 100) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer nn (1≤n≤1001\leq n\leq 100) — the size of the set.

The second line of each testcase contains nn integers a1,a2,…ana_1,a_2,\dots a_n (0≤ai≤1000\leq a_i\leq 100) — the numbers in the set.

输入包含多个测试用例。第一行包含一个整数 tt(1≤t≤1001\leq t\leq 100),表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 nn(1≤n≤1001\leq n\leq 100),表示集合的大小。

每个测试用例的第二行包含 nn 个整数 a1,a2,…ana_1,a_2,\dots a_n(0≤ai≤1000\leq a_i\leq 100),表示集合中的数字。

输出格式

For each test case, print the maximum value of mex(A)+mex(B)mex(A)+mex(B).

对于每个测试用例,输出 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=\left\{0,1,2\right\},B=\left\{0,1,5\right\} 是一种可行的选择。

在第二个测试用例中,A={0,1,2},B=∅A=\left\{0,1,2\right\},B=\varnothing 是一种可行的选择。

在第三个测试用例中,A={0,1,2},B={0}A=\left\{0,1,2\right\},B=\left\{0\right\} 是一种可行的选择。

在第四个测试用例中,A={1,3,5},B={2,4,6}A=\left\{1,3,5\right\},B=\left\{2,4,6\right\} 是一种可行的选择。

输入解题思路,AI测评打分。不知道怎么写?

首页