CF1743B 题解

mutan · 2022-10-21 18:35:08 · 题解

简要翻译

给定一个长度为 n 的正整数，构造一个长度为 n 的排列数。定义一个排列的权值为其中能构成排列的子串数量。形式化来讲，一个长度为 a 的子串需要包含 [1,a] 中的所有数。

输出长度为 n 的排列数中权值最小的一种排列。

题目分析

需要权值最小，也就是其中能构成排列的子串最少。而构成排列需要从 1 开始。所有的排列都需要 1。这样一来，只要把 1 放到最后，其他数依次排列，1 就不能与前面的数组成排列（除了整个排列）。

例如，当 n=6 时，构造排列 \{2,3,4,5,6,1\}，前面的 \{2,3,4,5,6\} 都无法自己组成排列。整个排列的子排列只有 \{1\},\{2,3,4,5,6,1\}，权值 =2。

于是代码很简单，依次输出 2\sim n 的数，最后输出 1 即可。

#include <iostream>
#include <cstdio>

using namespace std;
int T;
int main()
{
    int n,i,j;
    cin>>T;
    for(i=0;i<T;i++)
    {
        cin>>n;
        for(j=2;j<=n;j++)
        printf("%d ",j);
        printf("1\n");
    }
    return 0;
}