← 返回题目列表

Codeforces · 2056/C

C. 回文子序列

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

对于整数序列$$$a = [a_1, a_2, \ldots, a_n]$$$,我们将$$$f(a)$$$定义为$$$a$$$的最长子序列$$$^{\text{*}}$$$的长度,该子序列是回文$$$^{\text{†}}$$$。

让 $$$g(a)$$$ 表示长度为 $$$f(a)$$$ 的回文子序列的数量。换句话说,$$$g(a)$$$ 计算$$$a$$$ 中具有最大长度的回文子序列的数量。

给定一个整数 $$$n$$$,你的任务是找到满足以下条件的 $$$n$$$ 整数的任何序列 $$$a$$$:

- $$$1 \le a_i \le n$$$ 对于所有 $$$1 \le i \le n$$$。
- $$$g(a) > n$$$

可以证明,在给定的约束下,这样的序列总是存在。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$\color{red}{6} \le n \le 100$$$) — 序列的长度。

请注意,所有测试用例的 $$$n$$$ 总和没有限制。

输出

对于每个测试用例,输出 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$,表示满足条件的数组。

如果有多个解,则可以输出其中任何一个。

示例

输入 #1

3
6
9
15

输出 #1

1 1 2 3 1 2
7 3 3 7 5 3 7 7 3
15 8 8 8 15 5 8 1 15 5 8 15 15 15 8

注意

在第一个示例中,一个可能的解决方案是 $$$a = [1, 1, 2, 3, 1, 2]$$$。在这种情况下,$$$f(a) = 3$$$,因为最长回文子序列的长度为 $$$3$$$。有 $$$7$$$ 方法可以选择长度为 $$$3$$$ 的回文子序列,如下所示:

1.$$$[a_1, a_2, a_5] = [1, 1, 1]$$$
2.$$$[a_1, a_3, a_5] = [1, 2, 1]$$$
3.$$$[a_1, a_4, a_5] = [1, 3, 1]$$$
4.$$$[a_2, a_3, a_5] = [1, 2, 1]$$$
5.$$$[a_2, a_4, a_5] = [1, 3, 1]$$$
6.$$$[a_3, a_4, a_6] = [2, 3, 2]$$$
7. $$$[a_3, a_5, a_6] = [2, 1, 2]$$$

因此,$$$g(a) = 7$$$,大于 $$$n = 6$$$。因此,$$$a = [1, 1, 2, 3, 1, 2]$$$ 是一个有效的解决方案。

在第二个示例中,一种可能的解决方案是 $$$a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$$$。在这种情况下,$$$f(a) = 5$$$。有 $$$24$$$ 方法可以选择长度为 $$$5$$$ 的回文子序列。一些示例是 $$$[a_2, a_4, a_5, a_8, a_9] = [3, 7, 5, 7, 3]$$$ 和 $$$[a_1, a_4, a_6, a_7, a_8] = [7, 7, 3, 7, 7]$$$。因此,$$$g(a) = 24$$$,大于$$$n = 9$$$。因此, $$$a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$$$ 是一个有效的解决方案。

在第三个示例中,$$$f(a) = 7$$$ 且 $$$g(a) = 190$$$,大于 $$$n = 15$$$。