YZOJ P2163 [THUSC2015]解密运算

YZOJ P2163 [THUSC2015]解密运算

时间限制:1000MS      内存限制:131072KB

难度:\(7.0\) (自评)

  • 题目描述

对于一个长度为 \(N\) 的字符串,我们在字符串的末尾添加一个特殊的字符 “.” 。之后将字符串视为一个环,从位置 \(1,2,3,\cdots,N+1\) 为起点读出 \(N+1\) 个字符,就能得到 \(N+1\) 个字符串。

比如对于字符串 “ABCAAA”,我们可以得到这 \(N+1\) 个串:

接着我们对得到的这 \(N+1\) 个串按字典序从小到大进行排序(注意特殊字符 “.” 的字典序小于任何其他的字符)结果如下:

最后,将排序好的 \(N+1\) 个串的最后一个字符取出,按照顺序排成一个新的字符串,也就是上面这个表的最后一列,就是加密后的密文 “AAAC.AB” 。

请通过加密后的密文求出加密前的字符串。

  • 输入格式

第一行有两个整数 \(N, M\),分别表示加密前的字符串长度和字符集大小,其中字符用整数 \(1,2,3,\cdots,M\) 编号,添加的特殊字符 “.” 用 \(0\) 编号。

第二行为 \(N+1\) 个整数,表示加密后的字符串。

  • 输出格式

输出仅一行,包含 \(N\) 个整数,用空格隔开,依次表示加密前字符串中每个字符的编号。

  • 样例输入

  • 样例输出

  • 数据规模与约定

\(N,M \leq 200000\) 。

 

 

Source: BZOJ 4104


 

 

 

挺神仙的一道题目,看得懂的人都看得懂,看不懂的人就看不懂。

注意到加密后的字符串其实还是原来字符串里的那几个字符,就是顺序变了一下而已。

由于字符串是循环的,所以知道了当前串中最后一个字符的排名,也相当于知道了这个字符在原串中下一个字符的排名。

所以把加密串拿去排序,这样就知道了某一个字符在原串中的排名。

问题是相同的字符,但是幸好的是输入的数据就已经帮我们排好序了,所以以下标为第二关键字排序即可。

这样就可以根据最小的 ‘.’ ,跳第二关键字,在排好序的序列里找到原串了。

 

 

 

 

发表评论

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