← 返回题目列表

Codeforces · 2176/C

C. 奇怪的过程

中文机器翻译题面 查看原题

您有 $$$n$$$ 硬币,面额为 $$$a_1、a_2、\ldots、a_n$$$ 和自然数 $$$k$$$。您还有一个袋子,最初是空的,您可以在其中放置硬币。您需要准确执行 $$$k$$$ 操作。在每个动作中,您从剩下的硬币中取出一枚硬币并将其放入您的包中。之后,你就不能再拿走那枚硬币了。

同时,你有一只喜欢偶数的猫,所以每当你包里的硬币面额之和变成偶数时,你的猫就会清空包里的东西,这意味着它会把所有的硬币带到一个只有它知道的地方,然后包里又空了。请注意,在添加硬币的过程中,每次金额变为偶数时,袋子都会被清空,而不仅仅是在最后一刻。

让你的分数为袋子里硬币面值的总和。您的任务是执行 $$$k$$$ 操作,以使您的最终得分最大化。找出所有 $$$1 \le k \le n$$$ 的答案。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 您拥有的硬币数量。

每个测试用例的第二行包含 $$$n$$$ 自然数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 硬币的面额。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 数字 — 通过对从 $$$1$$$ 到 $$$n$$$ 的所有 $$$k$$$ 执行精确 $$$k$$$ 操作可以获得的最大可能分数。

示例

输入
复制

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

输出
复制

1 0 1
3 5 0
3 7 9 7 9
3 7 9 7 9
1 5 7
0 0 0

注意

在第一组输入数据中,您有面额为 [$$$1,1,1$$$] 的硬币。

  • $$$k=1$$$:在这种情况下,无论选择哪种硬币,袋子中的面额总和都是 $$$1$$$。最终得分也是$$$1$$$。
  • $$$k=2$$$:在这种情况下,无论选择哪种硬币,袋子中的面额总和最初都是 $$$1$$$。当选择第二个硬币时,无论选择哪种硬币,总和都是$$$2$$$,因此袋子将被清空。最终得分为$$$0$$$。
  • $$$k=3$$$:在这种情况下,当选择前两个硬币时,总和将为$$$2$$$,袋子将被清空,之后总和将为$$$0$$$。当选择第三个硬币时,总和将变为$$$1$$$。

在第二组输入数据中,您有面额为 [$$$1,2,3$$$] 的硬币。

  • $$$k=1$$$:在这种情况下,当选择面额为$$$2$$$的硬币时,袋子将被清空,最终得分为$$$0$$$。当选择面值$$$1$$$或$$$3$$$的硬币时,最终得分将分别为$$$1$$$和$$$3$$$。最终可能的最高得分为 $$$3$$$。
  • $$$k=2$$$:在这种情况下,当以任意顺序选择两个硬币$$$1$$$和$$$3$$$时,它们的总和将为$$$4$$$,之后袋子将被清空,最终分数将为$$$0$$$。然而,当选择 $$$3$$$ 作为第一个硬币时,分数将为 $$$3$$$。然后你可以选择,比如硬币$$$2$$$,最后的分数就会变成$$$5$$$。
  • $$$k=3$$$:在这种情况下,所有硬币的总和将为$$$6$$$,并且由于每次清空袋子时不会改变累积总和的奇偶性,因此最终得分为$$$0$$$。