582 字
3 分钟
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 longLL 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) ;}