ZOJ 3891 K-hash (后缀数组,难)

题意:  给出一个很长的数字,然后求这个数字所有不同的子串%k的结果分别等于0,1,…k-1的个数,如果串相同则视为一样,不进行累加.

题解:  好吧,我是真的不会做,这题的的思维量也不是一点两点.

问题分解成两步解决.

1.不考虑重复的情况,直接计算不同子串%k结果为0-k-1的个数.

2.考虑重复的情况在哪里,这里要用到后缀数字去重,其实是根据后缀数组分组的思想对相邻最接近的前缀进行处理.

这样去重有个问题,就是0的情况无法去重,仔细思考就会发现,例如100000002,中间的0就重复计算很多次无法去重.

其实前导零的情况可以通过第一步和第二不对0进行特判处理,第一步不将0作为前导的数计入,第二步不将0作为前导的去重.

那么接下来详细介绍第一步和第二部的做法

第一步:  因为只要计算0~k-1的结果,所以可以类似dp的做法,ans[i]表示任何数%k之后结果为i时的值.在定义一个变量来记录上次ans[0…k-1]的值,那么每次的转移:  ans[(j * 10 + num) % k] += sum[j];

第二步:  后缀数组求出height数组,然后定义sum[0…k-1]表示每个结果要去重的个数.通过这个例子来说明:

111222111222111232111233

只取一部分的前缀作为说明:

(1) 111222111222111232111233

(2) 111222111232111233

(3) 111232111233

(4) 111233

首先对于(1)和(2)会发现重复的部分是1112221112这个串所有的前缀(因为是对两个前缀处理不用考虑后缀的串,因为其他前缀会枚举到)

接着对于(2)和(3)的去重,其实可以在上一步的基础上添加或者减少,这样时间会更快(就不会超时)

具体实现还是代码比较好说话.

其实无论学什么算法,能够将之当成工具随心所用才是精髓之道.

 

LEAVE A COMMENT