← 返回题目列表

Codeforces · 1427/D

D. 洗牌

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

您将获得一副 $$$n$$$ 牌,编号从 $$$1$$$ 到 $$$n$$$(牌组中不一定按此顺序)。您必须通过重复以下操作对牌组进行排序。

- 选择 $$$2 \le k \le n$$$ 并将牌组分成 $$$k$$$ 非空连续部分 $$$D_1, D_2,\dots, D_k$$$ ($$$D_1$$$ 包含牌组的前 $$$|D_1|$$$ 卡,$$$D_2$$$ 包含以下内容$$$|D_2|$$$ 卡等等)。然后反转各个部分的顺序,将牌组转换为 $$$D_k, D_{k-1}, \dots, D_2, D_1$$$ (因此,新牌组的前 $$$|D_k|$$$ 卡是 $$$D_k$$$,后面的 $$$|D_{k-1}|$$$ 卡是 $$$D_{k-1}$$$ 等等)。每包卡片 $$$D_i$$$ 的内部顺序不会因操作而改变。

您必须获得最多执行 $$$n$$$ 操作的排序牌组(即第一张牌为 $$$1$$$,第二张牌为 $$$2$$$ 等的牌组)。可以证明,总是可以对最多执行 $$$n$$$ 操作的牌组进行排序。

操作示例: 以下是三个有效操作示例(在不同大小的三副牌上)。

- 如果牌组是 [3 6 2 1 4 5 7](因此 $$$3$$$ 是第一张牌,$$$7$$$ 是最后一张牌),我们可以应用 $$$k=4$$$ 和 $$$D_1=$$$[3 6]、$$$D_2=$$$[2 1 4] 的操作, $$$D_3=$$$[5],$$$D_4=$$$[7]。这样,牌组就变成了 [7 5 2 1 4 3 6]。
- 如果牌组是 [3 1 2],我们可以使用 $$$k=3$$$ 和 $$$D_1=$$$[3]、$$$D_2=$$$[1]、$$$D_3=$$$[2]进行运算。这样做的话,牌组就变成了[2 1 3]。
- 如果牌组是 [5 1 2 4 3 6],我们可以使用 $$$k=2$$$ 和 $$$D_1=$$$[5 1]、$$$D_2=$$$[2 4 3 6] 进行运算。这样,牌组就变成了 [2 4 3 6 5 1]。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 52$$$) — 这副牌中的牌数。

第二行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ — 牌组中的牌。第一张牌是$$$c_1$$$,第二张牌是$$$c_2$$$,依此类推。

保证对于所有$$$i=1,\dots,n$$$,在\{1,\dots,n\}$$$中恰好有一个$$$j\使得$$$c_j = i$$$。

输出

在第一行,打印您执行的操作数$$$q$$$(它必须包含$$$0\le q\le n$$$)。

然后,打印 $$$q$$$ 行,每行描述一个操作。

要描述操作,请在一行上打印您要分割牌组的部分的数量 $$$k$$$,后跟 $$$k$$$ 部分的大小:$$$|D_1|、|D_2|、\dots、|D_k|$$$。

对于所有 $$$i=1、\dots、k$$$ 和 $$$|D_1|+|D_2|+\cdots + |D_k|,它必须保存 $$$2\le k\le n$$$ 和 $$$|D_i|\ge 1$$$。 = n$$$。

可以证明,总是可以对最多执行 $$$n$$$ 操作的牌组进行排序。如果有多种方法对牌组进行排序,您可以输出其中任何一种。

示例

输入 #1

4
3 1 2 4

输出 #1

2
3 1 2 1
2 1 3

输入 #2

6
6 5 4 3 2 1

输出 #2

1
6 1 1 1 1 1 1

输入 #3

1
1

输出 #3

0

注意

第一个测试用例的解释:最初牌组是 [3 1 2 4]。

- 第一个操作将牌组分割为 [(3) (1 2) (4)],然后将其转换为 [4 1 2 3]。
- 第二个操作将牌组分割为 [(4) (1 2 3)],然后将其转换为 [1 2 3 4]。

- 第一个(也是唯一的)操作将牌组分割为 [(6) (5) (4) (3) (2) (1)],然后将其转换为 [1 2 3 4 5 6]。