permutation

3.1 题目描述

一个长度为n 的排列p[1..n]
把排列的每个循环拿出来,写成标准循环,再做一次排序
比如[4, 1, 6, 2, 5, 3],有3 个循环(421)(63)(5)
其中第一个循环就是4 要到2 的位置,2 要到1 的位置,1 要到4 的位置

每个循环从任意一个位置开始读都是一样的
比如(412) 也是(124),(241)。n 个循环就一共n 个表达法
我们规定一个标准循环是以循环内最大的数字开头
循环之间排序的关键字就是第一个数字的大小
如(421)(63)(5) 排序后是(421)(5)(63)
如果排序后的拍列和原排列一样,那么就是可行排列
求n 个数的字典序第k 大的排列

3.2 输入格式

两个整数,n,k 保证k 在long long 范围内,保证有解

3.3 输出格式

n 个整数,表示满足条件的排列

3.4 Sample Input1

4 3

3.5 Sample Output1

1 3 2 4

3.6 Sample Input2

10 1

3.7 Sample Output2

1 2 3 4 5 6 7 8 9 10

3.8 数据范围及约定

对于30% 的数据满足:1 <= n <= 10
对于100% 的数据满足,1 <= n <= 50

题解

不要被卡读题

什么是循环

比如说 题目中的例子

4本应在的位置为2在的位置
2本应在的位置为1在的位置
1本应在的位置为4在的位置
这就是一个循环

然后先打一个表找规律

我们会惊讶的发现他好像和斐波那契有关

而且只会有相邻的两个数调换

然后按照规律跑就可以了

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
#define LL long long
LL f[55], Sum[55];
int a[55];
bool mark[55];
int main()
{
    LL n, k;
    scanf("%lld%lld", &n, &k);
    f[0] = f[1] = f[2] = 1;
    Sum[0] = 1, Sum[1] = 2, Sum[2] = 3;
    for (int i = 3; i <= n; i++)
    {
        f[i] = f[i - 1] + f[i - 2];
        Sum[i] = Sum[i - 1] + f[i];
    }
    for (int i = 1; i <= n; i++)
        a[i] = i;
    while (k > 1)
    {
        int j = lower_bound(Sum, Sum + n + 1, k) - Sum -1;
        k -= Sum[j];
        mark[n - j - 1] = mark[n - j] = 1;
    }
    for (int i = 1; i <= n; i++)
        if (mark[i] && mark[i + 1])
            mark[i] = mark[i + 1] = 0, swap(a[i], a[i + 1]);
    for (int i = 1; i <= n; i++)
        printf("%d ", a[i]);
    //while (1)
    ;
}
本文作者 : NekoMio
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接 : https://www.nekomio.com/2017/08/09/81/
上一篇
下一篇