Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 2408: 混乱的置换

题目链接

传送门

Description

有n个0~m的数,定义左旋一次为将第一个放在最后一个数之后,
右旋一次为将最后一个数放在第一个数之前,做完 n 次旋转操作(n
次左旋或 n 次右旋)之后,将 n 个数列按字典序排序后可得到一个
n*n 的矩阵,已知矩阵的最后一列,现求矩阵的第一行。

Input

第一行两个数n、m,意义如题中所述
第二行共n 个数,即为矩阵的最后一列

Output

共一行n个数,即矩阵的第一行

Sample Input

5 5

5 1 2 3 4

Sample Output

1 2 3 4 5

HINT

样例解释

1 2 3 4 5

2 3 4 5 1

3 4 5 1 2

4 5 1 2 3

5 1 2 3 4

对于100%的数据 n<=10000,m=9

题解

首先你得知道这个矩阵是什么才能求是吧
他说这n次的操作是一样的
而且按照字典序排了序
那么不就是在说这个矩阵是由BWT转码过程中那些排好序的文本串组成的表格么
有关下面这个表格的来源和BWT算法
大概在这里 传送门

就是由Sorted那一列的所有字符串组成的矩阵
这样的话再回去看题
给你的是最后一列
也就是L那一列
让你求第一行 这就是裸的BWT啊
让你求字典序最小的那个是什么
代码中出现了一个count函数
这是有关count函数的

代码

One Comment

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏