OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【THOI2015】解密运算

【题目描述】

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

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

ABCAAA.

BCAAA.A

CAAA.AB

AAA.ABC

AA.ABCA

A.ABCAA

.ABCAAA

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

.ABCAAA

A.ABCAA

AA.ABCA

AAA.ABC

ABCAAA.

BCAAA.A

CAAA.AB

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

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

【输入】

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

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

【输出】

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

【输入样例】

6 3

1 1 1 3 0 1 2

【输出样例】

1 2 3 1 1 1

【数据范围】

1<=N,M<=200000

【题解】

和JSOI2007字符加密很相似呢,但这是一道简单得不用贴算法标签的题目。

给出的就是一个双关键字排序,所以再把关键字顺序交换排一个序就好了。

【代码】

赛后AC系列……

http://paste.ubuntu.com/11539399/

评论

© OI技术宅 | Powered by LOFTER