KMnO4y_Fish's Blog

返回

题目链接:CF553B Kyoya and Permutation

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


题目描述#

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

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

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

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

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

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

输入格式#

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

输出格式#

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

样例1说明#

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

数据范围#

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


解题思路#

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

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

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

证明如下:

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

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

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

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

对于n=1n=1f(n)=1f(n) = 1

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

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

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

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

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

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

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

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

递归终止条件:

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

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


贴出代码

// 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;
}
cpp

评测记录:R24368083

[洛谷题解] CF553B Kyoya and Permutation
https://ak-ioi.com/blog/algo-solution/luogu-cf553b
作者 KMnO4y_Fish
发布于 2019年9月26日
评论似乎无法加载。试试刷新?✨