2026 杭电春季联赛 2——1003-竹林清韵

题目大意

题目描述总结

给定一个长度为 $n$ 的数列 $a_1, a_2, \dots, a_n$ 和一个定值 $x$。两名玩家（铃仙和因幡帝）交替从数列中取数，取出的数会立刻从原数列中删除。规则如下：

1. 铃仙先手，每次可以从当前数列中任选一个数。

2. 因幡帝后手，每次必须选择当前数列头部的前 $x$ 个数（即剩下数列的第 $1$ 到第 $x$ 个数）。若当前数列剩余元素不足 $x$ 个，则因幡帝会将剩余的所有数全部取走。

3. 两人交替选数，直到数列为空。

铃仙的目标是最大化自己所取出的所有数字之和。
假设铃仙始终采取最优策略，请对于所有的 $x = 1, 2, 3, \dots, n-1$，分别独立求出铃仙所能获得的数字和的最大值。

输入格式
第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例数量。
每个测试用例包含两行：
第一行是一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示数列长度。
第二行是 $n$ 个正整数 $a_i$（$1 \le a_i \le 10^9$），表示给定的数列。
保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$。

输出格式
对于每个测试用例输出一行，包含 $n-1$ 个正整数。第 $i$ 个整数表示当 $x=i$ 时，铃仙能获得的最大数字和。

样例数据

输入样例：

3
2
1 2
6
1 1 4 5 1 4
11
12 11 10 9 1 2 3 4 5 12 11

输出样例：

2
13 9 9 9 5
54 44 35 35 24 24 24 24 23 12

样例解释
在样例 $2$ 中，初始数列为 $1, 1, 4, 5, 1, 4$。

当 $x=1$ 时，一种使得铃仙获得最大和的方案为：

• 铃仙先选取 $a_4=5$，删除该数，此时数列变为 $1, 1, 4, 1, 4$；

• 因幡帝必须选取头部的 $1$ 个元素 $a_1=1$，此时数列变为 $1, 4, 1, 4$；

• 铃仙再选取 $a_2=4$，此时数列变为 $1, 1, 4$；

• 因幡帝必须选取头部的 $1$ 个元素 $a_1=1$，此时数列变为 $1, 4$；

• 铃仙再选取 $a_2=4$，此时数列变为 $1$；

• 因幡帝必须选取头部的 $1$ 个元素 $a_1=1$，此时数列为空，停止。
  铃仙所选之数的和为 $5+4+4=13$。可以证明，该方案铃仙所选之数的和最大。

当 $x=3$ 时，一种使得铃仙获得最大和的方案为：

• 铃仙先选取 $a_4=5$，删除该数，此时数列变为 $1, 1, 4, 1, 4$；

• 因幡帝必须选取头部的 $3$ 个元素 $a_1=1, a_2=1, a_3=4$，此时数列变为 $1, 4$；

• 铃仙再选取 $a_2=4$，此时数列变为 $1$；

• 因幡帝必须选取头部的 $3$ 个元素，但当前数列大小小于 $3$，全部取完，此时数列为空，停止。
  铃仙所选之数的和为 $5+4=9$。可以证明，该方案铃仙所选之数的和最大。

思路讲解

说实话，看完这道题目，我的感觉是不是特别困难。

AC代码

源代码

心路历程（WA，TLE，MLE……）