Unshuffling a Deck

题意翻译

给出一副 $n$ 张编号为 $1$ 到 $n$ 的卡牌，且不一定按照 $1$ 到 $n$ 的顺序给出，你需要按照以下步骤给卡牌排序： * 任选 $2≤k≤n$ 并将这幅卡牌分为连续非空的 $k$ 个部分 $D_1,D_2,...,D_k$ ，其中 $D_1$ 包含了前 $|D_1|$ 张卡牌（译注： $|D_1|$ 表示 $D_1$ 中卡牌的数量，下同理）， $D_2$ 包含了紧接着的 $|D_2|$ 张卡牌，以此类推。然后将每部分的顺序翻转，将这幅卡牌变为 $D_k,D_{k-1},...,D_2,D_1$ ，操作后的这副卡牌前 $|D_k|$ 张卡牌是属于 $D_k$ 部分的，紧接着的 $|D_{k-1}|$ 张卡牌是属于 $D_{k-1}$ 部分的，以此类推。每部分卡牌内部的顺序不会因此操作而改变。 你需要用至多 $n$ 次操作将卡牌按 $1$ 到 $n$ 的顺序排列好，可以证明必然可以用至多 $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$ ，表示卡牌的数量。 第二行为 $n$ 个整数 $c_1,c_2,...,c_n$ 来描述这幅卡牌。第一张排牌为 $c_1$ ，第二张排牌为 $c_2$ ，以此类推。 保证所有1到n的整数在 $c_1,c_2,...,c_n$ 中恰好出现1次。 ## 输出格式 第一行输出你操作的次数 $q$ （要保证 $0≤q≤n$ ）。 然后输出 $q$ 行来描述你的操作。 要描述你的操作，你需要输出一个整数 $k$ （见题意），并紧接着输出 $k$ 个整数$|D_1|,|D_2|,...,|D_k|$。 要保证 $2≤k≤n$ ，对于任意的 $i=1,2,...,k$ ， $|D_i|≥1$ ，且 $|D_1|+|D_2|+...+|D_k|=n$ 。 可以证明必然可以用至多 $n$ 次操作将卡牌排序，如果存在多种排序卡牌的方式，输出任意一种。

题目描述

You are given a deck of $ n $ cards numbered from $ 1 $ to $ n $ (not necessarily in this order in the deck). You have to sort the deck by repeating the following operation. - Choose $ 2 \le k \le n $ and split the deck in $ k $ nonempty contiguous parts $ D_1, D_2,\dots, D_k $ ( $ D_1 $ contains the first $ |D_1| $ cards of the deck, $ D_2 $ contains the following $ |D_2| $ cards and so on). Then reverse the order of the parts, transforming the deck into $ D_k, D_{k-1}, \dots, D_2, D_1 $ (so, the first $ |D_k| $ cards of the new deck are $ D_k $ , the following $ |D_{k-1}| $ cards are $ D_{k-1} $ and so on). The internal order of each packet of cards $ D_i $ is unchanged by the operation. You have to obtain a sorted deck (i.e., a deck where the first card is $ 1 $ , the second is $ 2 $ and so on) performing at most $ n $ operations. It can be proven that it is always possible to sort the deck performing at most $ n $ operations. Examples of operation: The following are three examples of valid operations (on three decks with different sizes). - If the deck is \[3 6 2 1 4 5 7\] (so $ 3 $ is the first card and $ 7 $ is the last card), we may apply the operation with $ k=4 $ and $ D_1= $ \[3 6\], $ D_2= $ \[2 1 4\], $ D_3= $ \[5\], $ D_4= $ \[7\]. Doing so, the deck becomes \[7 5 2 1 4 3 6\]. - If the deck is \[3 1 2\], we may apply the operation with $ k=3 $ and $ D_1= $ \[3\], $ D_2= $ \[1\], $ D_3= $ \[2\]. Doing so, the deck becomes \[2 1 3\]. - If the deck is \[5 1 2 4 3 6\], we may apply the operation with $ k=2 $ and $ D_1= $ \[5 1\], $ D_2= $ \[2 4 3 6\]. Doing so, the deck becomes \[2 4 3 6 5 1\].

输入输出格式

输入格式

The first line of the input contains one integer $ n $ ( $ 1\le n\le 52 $ ) — the number of cards in the deck. The second line contains $ n $ integers $ c_1, c_2, \dots, c_n $ — the cards in the deck. The first card is $ c_1 $ , the second is $ c_2 $ and so on. It is guaranteed that for all $ i=1,\dots,n $ there is exactly one $ j\in\{1,\dots,n\} $ such that $ c_j = i $ .

输出格式

On the first line, print the number $ q $ of operations you perform (it must hold $ 0\le q\le n $ ). Then, print $ q $ lines, each describing one operation. To describe an operation, print on a single line the number $ k $ of parts you are going to split the deck in, followed by the size of the $ k $ parts: $ |D_1|, |D_2|, \dots , |D_k| $ . It must hold $ 2\le k\le n $ , and $ |D_i|\ge 1 $ for all $ i=1,\dots,k $ , and $ |D_1|+|D_2|+\cdots + |D_k| = n $ . It can be proven that it is always possible to sort the deck performing at most $ n $ operations. If there are several ways to sort the deck you can output any of them.

输入输出样例

输入样例 #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

说明

Explanation of the first testcase: Initially the deck is \[3 1 2 4\]. - The first operation splits the deck as \[(3) (1 2) (4)\] and then transforms it into \[4 1 2 3\]. - The second operation splits the deck as \[(4) (1 2 3)\] and then transforms it into \[1 2 3 4\]. Explanation of the second testcase: Initially the deck is \[6 5 4 3 2 1\]. - The first (and only) operation splits the deck as \[(6) (5) (4) (3) (2) (1)\] and then transforms it into \[1 2 3 4 5 6\].

题意翻译

给出一副 $n$ 张编号为 $1$ 到 $n$ 的卡牌，且不一定按照 $1$ 到 $n$ 的顺序给出，你需要按照以下步骤给卡牌排序： * 任选 $2≤k≤n$ 并将这幅卡牌分为连续非空的 $k$ 个部分 $D_1,D_2,...,D_k$ ，其中 $D_1$ 包含了前 $|D_1|$ 张卡牌（译注： $|D_1|$ 表示 $D_1$ 中卡牌的数量，下同理）， $D_2$ 包含了紧接着的 $|D_2|$ 张卡牌，以此类推。然后将每部分的顺序翻转，将这幅卡牌变为 $D_k,D_{k-1},...,D_2,D_1$ ，操作后的这副卡牌前 $|D_k|$ 张卡牌是属于 $D_k$ 部分的，紧接着的 $|D_{k-1}|$ 张卡牌是属于 $D_{k-1}$ 部分的，以此类推。每部分卡牌内部的顺序不会因此操作而改变。 你需要用至多 $n$ 次操作将卡牌按 $1$ 到 $n$ 的顺序排列好，可以证明必然可以用至多 $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$ ，表示卡牌的数量。 第二行为 $n$ 个整数 $c_1,c_2,...,c_n$ 来描述这幅卡牌。第一张排牌为 $c_1$ ，第二张排牌为 $c_2$ ，以此类推。 保证所有1到n的整数在 $c_1,c_2,...,c_n$ 中恰好出现1次。 ## 输出格式 第一行输出你操作的次数 $q$ （要保证 $0≤q≤n$ ）。 然后输出 $q$ 行来描述你的操作。 要描述你的操作，你需要输出一个整数 $k$ （见题意），并紧接着输出 $k$ 个整数$|D_1|,|D_2|,...,|D_k|$。 要保证 $2≤k≤n$ ，对于任意的 $i=1,2,...,k$ ， $|D_i|≥1$ ，且 $|D_1|+|D_2|+...+|D_k|=n$ 。 可以证明必然可以用至多 $n$ 次操作将卡牌排序，如果存在多种排序卡牌的方式，输出任意一种。