Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

05/30
19:20
乱搞

[bzoj 4104] [Thu Summer Camp 2015]解密运算

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

对于一个长度为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”。
请通过加密后的密文求出加密前的字符串。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

6 3
1 1 1 3 0 1 2

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

1 2 3 1 1 1

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

#i (i=1~4)    N=5*(i+1) M<=3

#5~6    N,M<=50 字符串中字符互不相同
#7~8    N,M<=1000 字符串中字符互不相同
#9~12    N,M<=1000
#13~#20    N,M<=200000

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

首先我们可以从0知道第一个数的排名,然后可以通过第1个数知道第2个数的排名....以此类推

我们以给定的串中的字符为第一关键字 它的位置为第二关键字 得到的就是原串的sa数组

然后根据0依次往后找位置就可以了

[bzoj 4104] [Thu Summer Camp 2015]解密运算