分类
标签
2-SAT AC自动机 BFS CDQ dfs DP fail树 FFT FFT&NTT FWT hash KD-Tree KMP LCA SPFA STL Tarjan Treap Trie 主席树 乱搞 二分 二分图匹配 二分答案 二维SPFA 交互 位运算 其他 最小生成树 分块 区间DP 半平面交 博弈论 可持久化 可持久化Trie树 后缀数组 图库 平衡树 并查集 插头DP 数学 数论 无旋Treap 日记 暴力 权值树状数组 栈 树DP 树套树 树状数组 树贪心 概率DP 模拟 欧拉定理 点分治 状压DP 生成函数 矩阵乘 线性规划 线段树 组合 网络流 群论 莫比乌斯反演 计算几何 贪心 费用流 高斯消元
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 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)
;
}