Skip to content

1280: イレイナ想进城

题目

题目描述

伊蕾娜是一位魔女,因为向往着幼时读过的旅行故事,她踏上了漫长的旅途,与形形色色的国家与人们邂逅。

这一次,她来到了一个被坚固的结界保护的城市,即使强大如她也难以打破。整座城市能进去的地方似乎只有一座紧闭着的古朴的城门,却没有门卫把守着。

城门上刻着一串古老的文字,经过伊蕾娜的研究,已经把它们映射成了一个由小写字母组成的字符串 $S$。伊蕾娜发现,只要能够得到字符串 $S$ 的所有排列中字典序第 $K$ 小的那个字符串,就能够打开城门进城。

伊蕾娜很轻松地解决了谜题进入了城镇,相信你也能做到~

什么是字典序? 字典序即英文单词在字典中的顺序:在英文字典中,排列单词的顺序是先按照第一个字母以升序排列(即`a、b、c、...、 z`的顺序)。如果第一个字母一样,那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长(比如,`sigh` 和 `sight`),那么把短者排在前。
什么是一个字符串的排列? 一个字符串 $A$ 被称为字符串 $B$ 的排列当且仅当任意字母在字符串 $A$ 和 $B$ 中的出现次数都是一样的。

输入格式

一行一个由小写字母组成的字符串 $S$ 和一个整数 $K$。

输出格式

输出字符串 $S$ 的所有排列中字典序第 $K$ 小的那个字符串。

样例输入

样例输入 1

aab 2

样例输入 2

baba 4

样例输入 3

ydxwacbz 40320

样例输出

样例输出 1

aba

样例解释 1

字符串 aab 有三个排列:aab, aba, baa。 字典序第二小的排列是 aba

样例输出 2

baab

样例输出 3

zyxwdcba

数据范围

$1\leq |S| \leq 8$。

保证字符串 $S$ 至少有 $K$ 个不同的排列。

PS:$|S|$ 表示字符串 $S$ 的长度。

提示

请在经过认真思考后仍然没有思路的情况下再查看提示~

Hint1 与全排列的区别在于有重复的元素,在排序并去重之后的第 $K$ 个就是第 $K$ 小的字符串。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!