Codeforces Round #309 (Div. 1) B. Kyoya and Permutation 找规律

2024-05-14 11:58

本文主要是介绍Codeforces Round #309 (Div. 1) B. Kyoya and Permutation 找规律,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

B. Kyoya and Permutation
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Let’s define the permutation of length n as an array p = [p1, p2, …, pn] consisting of n distinct integers from range from 1 to n. We say that this permutation maps value 1 into the value p1, value 2 into the value p2 and so on.

Kyota Ootori has just learned about cyclic representation of a permutation. A cycle is a sequence of numbers such that each element of this sequence is being mapped into the next element of this sequence (and the last element of the cycle is being mapped into the first element of the cycle). The cyclic representation is a representation of p as a collection of cycles forming p. For example, permutation p = [4, 1, 6, 2, 5, 3] has a cyclic representation that looks like (142)(36)(5) because 1 is replaced by 4, 4 is replaced by 2, 2 is replaced by 1, 3 and 6 are swapped, and 5 remains in place.

Permutation may have several cyclic representations, so Kyoya defines the standard cyclic representation of a permutation as follows. First, reorder the elements within each cycle so the largest element is first. Then, reorder all of the cycles so they are sorted by their first element. For our example above, the standard cyclic representation of [4, 1, 6, 2, 5, 3] is (421)(5)(63).

Now, Kyoya notices that if we drop the parenthesis in the standard cyclic representation, we get another permutation! For instance, [4, 1, 6, 2, 5, 3] will become [4, 2, 1, 5, 6, 3].

Kyoya notices that some permutations don’t change after applying operation described above at all. He wrote all permutations of length n that do not change in a list in lexicographic order. Unfortunately, his friend Tamaki Suoh lost this list. Kyoya wishes to reproduce the list and he needs your help. Given the integers n and k, print the permutation that was k-th on Kyoya’s list.

Input
The first line will contain two integers n, k (1 ≤ n ≤ 50, 1 ≤ k ≤ min{1018, l} where l is the length of the Kyoya’s list).

Output
Print n space-separated integers, representing the permutation that is the answer for the question.

Sample test(s)
input
4 3
output
1 3 2 4
input
10 1
output
1 2 3 4 5 6 7 8 9 10
Note
The standard cycle representation is (1)(32)(4), which after removing parenthesis gives us the original permutation. The first permutation on the list would be [1, 2, 3, 4], while the second permutation would be [1, 2, 4, 3].
题意不太好理解,题目说,定义cycle为一个1-n的排列,要求从某位映射几次后又回到本身了,比如题中的 1 - 1 2 - 3 - 2 4 - 4 ,其实每个排列都是有这样的规律,如随更说个 4 1 2 3,就是一个cycle 1 - 4 - 3 - 2 - 1,题目又定义合法的cycle为每个循环节内部按从大到小排序,循环节间用从小到大排序之后得到的序列与原来一致才是合法的序列,如 (1)(32)(4)排序后还是 (1)(32)(4),所以是合法的,但4 1 2 3 排序后为4 3 2 1,与原来不一致,所以是不合法的!
好吧,题目有点绕,我先是理解错了题意。把1 2 3 4列出来,我们发现有这些是合法的
1 2 3 4
1 2 4 3
1 3 2 4
2 1 3 4
2 1 4 3
很明显,是不是,只有相邻的两位可以交换,某一位要么不交换,要么只能交换一次,用dp的思想,dp[n] = dp[n-1] +dp[n-2],就是每n位不交换,或都与下一位交换。这不就是斐波那契数列嘛,发现这个规律后,就可以如这一位比dp[n]大,则这一位就要交换,否则不用交换。代码就很简单了。

#define N 60
#define M 100005
#define maxn 205
#define MOD 1000000000000000007
ll dp[N],k;
int n;
int main()
{dp[0] = dp[1] = 1;for(int i = 2;i<N;i++) dp[i] = dp[i-1] + dp[i-2];while(S(n) != EOF){cin>>k;for(int i= n-1;i>=0;i--){if(k > dp[i]){k -= dp[i];printf("%d %d ",n-i + 1,n-i);i--;}elseprintf("%d ",n-i);}}return 0;
}

这篇关于Codeforces Round #309 (Div. 1) B. Kyoya and Permutation 找规律的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/988692

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

计蒜客 Half-consecutive Numbers 暴力打表找规律

The numbers 11, 33, 66, 1010, 1515, 2121, 2828, 3636, 4545 and t_i=\frac{1}{2}i(i+1)t​i​​=​2​​1​​i(i+1), are called half-consecutive. For given NN, find the smallest rr which is no smaller than NN

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor

创建一个大的DIV,里面的包含两个DIV是可以自由移动

创建一个大的DIV,里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>