111qqz的小窝

老年咸鱼冲锋!

seerc 2014 Circle of digits (二分+后缀数组)

题目链接

题意:把一个长度为n的只由数字构成的串分成k个不为空的字串,使得最大的串最小(大小是说串所对应的十进制数的大小)

思路:由于长度为x的串肯定大于长度为x-1的串,因此很容易想到,我们要尽可能使得k组串的长度尽可能平均(避免出现某一个串的长度非常大的情况)

我们可以知道,最大值的串的长度一定为 LEN=(n+k-1)/k;

而每一组的长度,只可能是LEN或者LEN-1。

然后build_sa

注意循环串的几个地方记得%n

接下来二分sa数组的下标。

二分check的时候,先枚举断点,断环为链。

由于每部分最长的长度为LEN,所以0..LEN-1中一定存在一个断点。

然后贪心,尽可能取LEN

根据rk值来决定某一段的长度是LEN还是LEN-1(如果rk值比当前的大,那么就只能取LEN-1,否则取LEN)

如果此时k段的长度之和超过了n,说明此时的最大值还可能更小。

于是继续二分区间的前一半。

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz