[洛谷题解] CF553B Kyoya and Permutation

题目链接:CF553B Kyoya and Permutation

该题解主要思路来源于 CodeForces 官方题解


题目描述

定义一个长度为n排列为仅由1..n的元素组成,且每个元素恰好只出现1次的序列。我们称数值i\ (1\leq i \leq |p|)在排列p中的映射为p_i

Kyota Ootori 刚刚学习了排列循环表示法。定义排列p上的一个循环是一个由1..n的一部分元素组成的序列,并且在这个序列中,任意一个元素在p中的映射等于下一个元素(特别地,最后一个元素的映射等于第一个元素)。

显然,我们可以将一个排列划分成多个循环。例如p=[4,1,6,2,5,3]可以被划分成[1,4,2][3,6][5]三个循环。我们在每个循环周围加上括号,然后将它们连起来,得到的就是这个排列的循环表示法。例如[4,1,6,2,5,3]的一种循环表示法是(1\ 4\ 2)(3\ 6)(5)

对于一个长度不为1的排列,其循环表示法不是唯一的。为了使问题得到统一,我们定义一种标准循环表示法。即,对于每个循环,都将其最大值放在最前面,然后将这若干个循环按照最大值从小到大排列。这样,[4,1,6,2,5,3]标准循环表示法就是(4\ 2\ 1)(5)(6\ 3)

现在,Kyota 发现,如果我们去掉一个排列的标准循环表示法中的括号,我们将得到另一个排列。比如,由[4,1,6,2,5,3]可以得到[4,2,1,5,6,3]

他还发现,将某些排列的标准循环表示法中的括号去除后,得到的排列和原排列是一样的。我们称这种排列为“好的排列”。他按字典序递增的顺序在纸上写下了长度为n的所有好的排列,结果他的朋友 Tamaki Suoh 把这个列表搞丢了。Kyota 现在想要恢复这个列表。告诉你排列的长度n以及k,请你输出字典序从小到大k个好的排列。

输入格式

第一行输入两个空格隔开的整数nk

输出格式

一行,n个空格隔开的整数,表示要求的排列。

样例1说明

[1,3,2,4]标准循环表示法(1)(3\ 2)(4),去掉括号后得到的是[1,3,2,4],和原来的排列一样。字典序比其小的两个满足要求的序列是[1,2,3,4][1,2,4,3]

数据范围

1 \leq n \leq 501 \leq k \leq 10^8。保证长度为n的,第k个好的排列一定存在。


解题思路

提示:“好的排列”只能由1..n的顺序排列通过以下操作得来:

  • 在原排列上,选择若干个不相交的,长度为2的区间,然后翻转每个区间。

我们可以通过暴力打表或证明来发现这个规律。

证明如下:

我们考虑包含n的那个循环。因为n是最大值,因此这个循环一定是标准循环表示法中的最后一个,而且n排在这个循环的最前面。

  • 如果这个循环长度为1,显然已经证完了(n在原排列中一定是最后一个,而且在标准循环表示法中也是最后一个)。
  • 如果这个循环长度为2,那么显然构成这个循环的是n-1n
  • 如果这个循环长度为3,我们不妨假设这个循环是(n\ x\ y)。那么,在原排列上,n的位置上是xx的位置上是yy的位置上是n
    • 如果令x\lt y,那么在原排列上n,x,y的顺序是y,n,x,这是不可能与标准循环表示法(n\ x\ y)相同的。
    • 如果令x>y,那么在原排列上n,x,y的顺序是n,y,x,这是也不可能与标准循环表示法(n\ x\ y)相同的。
  • 如果这个循环更长,那么其情况与长度为3的类似,是不可能的。

既然我们已经证明了包含n的循环要么是(n),要么是(n,n-1),那么我们可以去掉n 或者 nn+1,我们发现这变成了一个n更小的问题,仍然符合上面证明出的规律。

然后我们来考虑长度为n的“好的排列”一共有多少种。我们设一共有f(n)种。

对于n=1f(n) = 1

对于n=2f(n) = 2,因为[1,2][2,1]都是合法的。

对于n>2f(n) = f(n-2) + f(n-1)

  • 假设包含n的循环长度为1,此时“好的排列”的个数就是长度为n-1的“好的排列”的个数。

  • 假设包含n的循环长度为2,那么排列的最后两项一定是[n,n-1],此时“好的排列”个数就是长度为n-2的“好的排列”的个数。

规律马上就出来了!长度为n的“好的排列”数量为斐波那契数列的第n+1项(此处提到的数列开头几项是1,1,2,3,5,8),记作fib[n+1]

那么如何构造第k小呢?我们刚才是从后向前考虑。根据开头的“提示”,其实从前向后考虑是等价的。

考虑如果包含1的循环长度为1,那么这个排列以1开头,随后是一个长度为n-1的“好的排列”每一位都加上1的结果。这样的“好的排列”数量为fib[n]。如果k小于等于fib[n],那么问题转化为构造长度为n-1的,第k小的“好的排列”,随后将这个排列每项增加1,再在开头加一个1。这可以递归实现。

如果包含1的循环长度为0,那么这个排列以[2,1]开头,随后是一个长度为n-2的“好的排列”每一位都加上2的结果。如果k大于fib[n],那么问题转化为构造长度为n-2,第k-fib[n]小的“好的排列”,随后将这个排列每项增加2,再在开头加上[2,1]。这也可以递归实现。

递归终止条件:

  • 如果n=1,那么构造出的排列一定是[1]
  • 如果n=0,那么构造出的排列一定是[]

在具体实现时,我们可以使用一些比较优美的写法,以实现简洁的代码和优秀的复杂度(不过这题n50,复杂度不是非常要紧),详见代码。


贴出代码

// status: [Accepted][he]
// oj:     [luogu]

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll

const int MAXN = 51;
// 读入的n和k
int n,k;
// 斐波那契数列预处理
int feiwu[MAXN];
// 构造排列时存入的数组
int arr[MAXN];

// 在arr[l..r]的空间中,构造l..r范围意义下,第rk小的“好的排列”
void buildArr(int l,int r,int rk) {
    // 待构造排列的长度
    int len = r-l+1;
    // 边界条件
    if(len==0) return;
    if(len==1) {arr[l] = l;return;}
    // 此时,第一项置为1,转化为构造n-1
    if(rk <= feiwu[len]) {
        arr[l] = l;
        arr[l+1] = l+1;
        buildArr(l+1,r,rk);
    }
    // 前两项为[2,1],转化为构造n-2
    else {
        arr[l] = l+1;
        arr[l+1] = l;
        // 注意这里rk要减去长度为n-1的“好的排列”数量
        buildArr(l+2,r,rk-feiwu[len]);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;

    // 进行预处理
    feiwu[1] = feiwu[2] = 1;
    for(int i=3;i<=n;i++) {
        feiwu[i] = feiwu[i-1] + feiwu[i-2];
    }

    buildArr(1,n,k);

    for(int i=1;i<=n;i++) {
        if(i>1) cout<<" ";
        cout<<arr[i];
    }
    cout<<endl;
}

评测记录:R24368083

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注