秋招模拟赛第二十二场|柠檬微趣|2023.05.06
- Status
- Done
- Rule
- IOI
- Problem
- 3
- Start at
- 2023-5-26 19:00
- End at
- 2023-5-26 20:30
- Duration
- 1.5 hour(s)
- Host
- Partic.
- 19
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
学校的体育老师今天请假了,但是他提前请了塔子哥去帮他代一节课。塔子哥给同学们从 1 开始进行编号,每一个同学都拿到了自己对应的号码,那么他想知道同学们排队顺序的所有方案,于是他考考屏幕前的你。
有 m 位学生和位置,现用 1 ~ m 表示学生,用一个长度为 m,元素为不重复元素的数组表示排队方案,现在需要给出第 n 个方案的结果。排队方案的选择顺序遵循全排列规则,并按字典序升序排序。
输入第一行为一个整数 m ,表示学生和位置数。(1≤m≤10 )
输入第二行为一个整数 n ,表示排列方案序号。( 1≤n≤109 )
若存在第 n 个方案,输出作为方案,数组间元素用空格隔开。
若不存在该方案,输出 −1。
输入
4
5
输出
1 4 2 3
输入
3
7
输出
-1
题解:全排列+计数
在LeetCode 46题的基础上,多了一个计数,就是在DFS求全排列的时候加一个计数变量cnt
,如果cnt=n
,则表示当前所求到的排列是我们需要的目标排列。
无解特判:如果当前n>m!,则一定无解,没有那么多的排列可以枚举。
C++
本题属于以下题库,请选择所需题库进行购买