← 返回题目列表

Codeforces · 2039/H1

H1. 酷交换步行(简单版)

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

这是问题的简单版本。唯一的区别是您可以执行的最大操作数。只有解决了两个版本的问题,你才能进行黑客攻击。

给你一个大小为 $$$n$$$ 的数组 $$$a$$$。

一个很酷的交换行走过程如下:

- 在 $$$n \times n$$$ 网格中,我们将行 $$$i$$$ 和列 $$$j$$$ 中的单元格记为 $$$(i, j)$$$。您需要从 $$$(1,1)$$$ 步行到 $$$(n,n)$$$,仅向右或向下走几步。
- 正式来说,如果您当前位于 $$$(x,y)$$$,则可以步进到 $$$(x+1,y)$$$ 或 $$$(x,y+1)$$$,但不能超出网格边界。
- 当你进入$$$(i,j)$$$时,当$$$i \neq j$$$时,你必须交换$$$a_i$$$和$$$a_j$$$。

你最多可以进行 $$$2n+4$$$ 酷交换行走。按非降序对数组 $$$a_1, a_2, \ldots, a_n$$$ 进行排序。我们可以证明,这样做总是有可能的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 500$$$) — 数组的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots ,a_n$$$ ($$$1 \le a_i \le n$$$) — 数组的元素。

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

输出

对于每个测试用例,您的输出应包含几行:

- 第一行包含一个整数 $$$k$$$ ($$$0 \leq k \leq 2n+4$$$),代表您执行的酷交换行走次数。
- 接下来的 $$$k$$$ 行包含一个长度为 $$$2n-2$$$ 的字符串 $$$s$$$,仅由 R 和 D 组成,表示路径(字母区分大小写)。对于所有 $$$1 \le i \le 2n-2$$$,如果 $$$s_i=$$$ R,则在第 $$$i$$$ 步中向右走,否则在第 $$$i$$$ 步中向下走。

示例

输入 #1

3
2
1 2
3
2 1 3
4
3 2 3 4

输出 #1

0
2
RRDD
DRDR
3
RRDRDD
DRDDRR
DDRRRD

注意

在第一个测试用例中,数组 $$$a$$$ 已经是非递减的,因此您不需要执行任何步行。

在第二个测试用例中,最初 $$$a=[2,1,3]$$$。

第一次行走时:

- 在$$$1$$$-st步骤中,你向右走到$$$(1,2)$$$。那么$$$a=[1,2,3]$$$。请注意,虽然数组 $$$a$$$ 已经是非递减的,但在达到 $$$(n,n)$$$ 之前不能停止。
- 在第 $$$2$$$ 步中,您向右走到 $$$(1,3)$$$。那么$$$a=[3,2,1]$$$。
- 在 $$$3$$$-rd 步骤中,您将下降到 $$$(2,3)$$$。那么$$$a=[3,1,2]$$$。
- 在第 $$$4$$$ 步中,您将下降到 $$$(3,3)$$$。那么$$$a=[3,1,2]$$$。

在第二次行走中:

- 在 $$$1$$$-st 步骤中,您将下降到 $$$(2,1)$$$。那么$$$a=[1,3,2]$$$。
- 在第 $$$2$$$ 步骤中,您向右走到 $$$(2,2)$$$。那么$$$a=[1,3,2]$$$。
- 在 $$$3$$$-rd 步骤中,您将下降到 $$$(3,2)$$$。那么$$$a=[1,2,3]$$$。
- 在第$$$4$$$步骤中,您将下降到$$$(3,3)$$$。那么$$$a=[1,2,3]$$$。

经过上面两次很酷的交换遍历,我们得到 $$$a=[1,2,3]$$$,它是非递减的。