B. Permutation Chain

Problem - B - Codeforces

B. 排列链
每次测试的时间限制 2 秒
每个测试的内存限制256 MB
输入标准输入
输出标准输出
长度为 n 的排列是从 1 到 n 的整数序列，使得每个整数在其中恰好出现一次。

令排列 p 的固定性为其中不动点的数量——使得 pj=j 的位置 j 的数量，其中 pj 是排列​​ p 的第 j 个元素。

你被要求构建一系列排列 a1,a2,...，从恒等排列开始（排列 a1=[1,2,...,n]）。我们称其为排列链。因此，ai 是长度为 n 的第 i 个排列。

对于从 2 开始的每个 i，排列 ai 应该通过交换其中的任意两个元素（不一定是相邻的）从排列 ai-1 中获得。排列 ai 的固定性应严格低于排列 ai-1 的固定性。//从上一个排列中

考虑 n=3 的一些链：

a1=[1,2,3], a2=[1,3,2] - 这是一个长度为 2 的有效链。从 a1 到 a2，位置 2 和 3 上的元素交换，固定性从 3 减少到1.
a1=[2,1,3], a2=[3,1,2] — 这不是一个有效的链。对于 n=3，第一个排列应始终为 [1,2,3]。
a1=[1,2,3], a2=[1,3,2], a3=[1,2,3] — 这不是一个有效的链。从 a2 到 a3，位置 2 和 3 上的元素被交换，但固定性从 1 增加到 3。
a1=[1,2,3], a2=[3,2,1], a3=[3,1,2] — 这是一个长度为 3 的有效链。从 a1 到 a2，位置 1 和3 交换，固定性从 3 减少到 1。从 a2 到 a3，位置 2 和 3 的元素交换，固定性从 1 减少到 0。
找到最长的排列链。如果有多个最长的答案，打印其中任何一个。

输入
第一行包含一个整数 t (1≤t≤99)——测试用例的数量。

每个测试用例的唯一一行包含一个整数 n (2≤n≤100)——链中所需的排列长度。

输出
对于每个测试用例，首先，打印排列链 k 的长度。

然后打印 k 个排列 a1,a2,…,ak。 a1 应该是长度为 n ([1,2,…,n]) 的恒等排列。对于从 2 到 k 的每个 i，应该通过交换 ai-1 中的两个元素来获得 ai。它还应该具有比 ai-1 严格更低的固定性。

例子
输入复制
2
2
3
输出复制
2
1 2
2 1
3
1 2 3
3 2 1
3 1 2

#include
#include
using namespace std;
int n,t;
int a[110];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        int m=n;
        cout<
        for(int i=0;i
        {
            a[i]=i+1;
            cout<' ';
        }
        cout<
        int i=-1;
       while (m -- )
       {
           i++;
           if(i==n-1)break;
           swap(a[i],a[i+1]);
           for(int j=0;j
           cout<" ";
           cout<
       }
    }
}

可以改进一点，润了。。