MEX (周练翻译)

MEX (周练翻译),第1张

描述:
Mihai has just learned about the MEX concept and since he liked it so much, he decided to use it right away.

M学习了关于MEX的感念并且因为喜欢它,他决定立刻使用它

Given an array a of n non-negative integers, Mihai wants to create a new array b that is formed in the following way:

While a is not empty:

Choose an integer k (1≤k≤|a|).


Append the MEX of the first k numbers of the array a to the end of array b and erase them from the array a, shifting the positions of the remaining numbers in a.

给一个n个非负元素的数组,M想通过以下方式建立一个新数组b:

当数组非空时 选择一个整数k,将数组a前k个整数取MEX放到数组b后,然后将它们从数组a中删除,移动a中剩余元素的位置。



But, since Mihai loves big arrays as much as the MEX concept, he wants the new array b to be the lexicographically maximum. So, Mihai asks you to tell him what the maximum array b that can be created by constructing the array optimally is.

但是,因为M和喜欢MEX一样,喜欢大数组,他想这个新数组b的字典序最大。


所以M要求你告诉他能从a中创造出来的b的最大数组是什么。




An array x is lexicographically greater than an array y if in the first position where x and y differ xi>yi or if |x|>|y| and y is a prefix of x (where |x| denotes the size of the array x).

当数组x和数组y的第一个不同的位置并且x>y时或者y是x的前缀,x字典序大于y。




The MEX of a set of non-negative integers is the minimal non-negative integer such that it is not in the set. For example, MEX({1,2,3}) =0 and MEX({0,1,2,4,5}) =3.

MEX是一组非负整数中最小的不在这个集合中的整数。




输入:
The first line of the input contains a single integer t (1≤t≤100) — the number of test cases. The description of test cases follows.

第一行输入一个整数t,测试样例的数量。


测试用例的描述如下。



The first line of each test case contains a single integer n (1≤n≤2⋅105) — the number of elements in the array a.

每个样例的第一行包含一个整数n 数组a元素的数量。




The second line of each test case contains n non-negative integers a1,…,an (0≤ai≤n), where ai is the i-th integer from the array a.

第二行包含n个非负数

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

保证所有样例的总和不超过2*1e5

输出:
For each test case print m — the length of the maximum array b Mihai can create, followed by m integers denoting the elements of the array b.

对于每一个样例输出一个m   M\能创作的最大数组b的长度。


后面是数组b元素

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/634324.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-16
下一篇 2022-04-16

发表评论

登录后才能评论

评论列表(0条)

保存