题目概述

CF1427D

解题报告

题目中疯狂暗示你做 $n$ 次，往这方面考虑就行了。

假如我们现在已经有了连续的 $1,2,3,\cdots,k$ ，我们想要把 $k+1$ 加到 $k$ 后面一个，举个例子：

5 9 4 6 7 1 2 3 8
    ^     -----

我们现在想把 $4$ 放到 $1,2,3$ 后面一个，那么可以这么分割：

5 9|4 6 7|1 2 3|8
8 1 2 3 4 6 7 5 9

接下来我们想把 $5$ 放到 $1,2,3,4$ 后面一个，但是我们发现 $5$ 在 $4$ 后面而不是 $1$ 前面，因此不能类似上面的分割方法，想要有序，我们必须把 $1,2,3,4$ 全都反过来，然后把 $5$ 加到 $4$ 前面一个：

8|1|2|3|4|6 7 5|9
9 6 7 5 4 3 2 1 8

接下来由于我们将 $1,2,3,4,5$ 反转成了 $5,4,3,2,1$ ，所以判断方式也需要反过来，和上面类似操作就行了。

排成有序最多需要 $n-1$ 次，如果最后是倒序，我们再反转一次就行了，最多 $n$ 次。

示例程序

#include<cstdio>
using namespace std;
const int maxn=52;

int n,a[maxn+5],c[maxn+5],ans,D[maxn+5][maxn+5];bool tp;

#define Push(ID,x) (D[ID][++D[ID][0]]=(x))
void Reverse(int ID){
    for (int i=1,L=1,R=n;i<=D[ID][0];i++){
        for (int j=D[ID][i];j;j--) c[R-j+1]=a[L++];
        R-=D[ID][i];
    }
    for (int i=1;i<=n;i++) a[i]=c[i];
}
int main(){
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    while (true){
        if (!tp){
            int L=1,R,pos=1;
            while (L<=n && a[L]>1) L++;R=L+1;
            while (R<=n && a[R-1]+1==a[R]) R++;R--;
            if (R-L+1==n) break;ans++;
            while (pos<=n && a[pos]!=a[R]+1) pos++;
            if (pos<L){
                if (pos>1) Push(ans,pos-1);
                Push(ans,L-pos);
                Push(ans,R-L+1);
                if (R<n) Push(ans,n-R);
            } else {
                if (L>1) Push(ans,L-1);
                for (int i=L;i<=R;i++) Push(ans,1);
                Push(ans,pos-R);
                if (pos<n) Push(ans,n-pos);
                tp^=1;
            }
        } else {
            int L,R=n,pos=1;
            while (R>=1 && a[R]>1) R--;L=R-1;
            while (L>=1 && a[L+1]+1==a[L]) L--;L++;
            if (R-L+1==n) break;ans++;
            while (pos<=n && a[pos]!=a[L]+1) pos++;
            if (pos>R){
                if (L>1) Push(ans,L-1);
                Push(ans,R-L+1);
                Push(ans,pos-R);
                if (pos<n) Push(ans,n-pos);
            } else {
                if (pos>1) Push(ans,pos-1);
                Push(ans,L-pos);
                for (int i=L;i<=R;i++) Push(ans,1);
                if (R<n) Push(ans,n-R);
                tp^=1;
            }
        }
        Reverse(ans);
    }
    if (tp) {ans++;D[ans][0]=n;for (int i=1;i<=n;i++) D[ans][i]=1;}
    printf("%d\n",ans);
    for (int i=1;i<=ans;i++){
        printf("%d",D[i][0]);
        for (int j=1;j<=D[i][0];j++) printf(" %d",D[i][j]);puts("");
    }
    return 0;
}