BZOJ3670/3620 [NOI2014]动物园 / 似乎在梦中见过的样子

Author Avatar
ajcxsu 2018年08月14日
  • 78 次阅读

后一题让我重新审视了一下前一道题我是怎么A掉的...

Problem

Solution

动物园

重新审视一下几个数组的含义:

$nxt_i$ $0$~$i-1$的最长公共前后缀(不包括自身)

$cnt_i$ $0$~$i-1$的公共前后缀数目(可以重叠,包括自身

$num_i$ $0$~$i-1$的不重叠公共前后缀数目

递推式: $$cnt_i=cnt_{nxt_i}+1$$ $$num_i=cnt_{j} \ (\text{0~j-1属于0~i-1的一个最大公共前后缀}, 2j\leq i)$$

似乎在梦中见过的样子

$O(n^2)$复杂度
第一个递推式变一下就行。
第二个复杂度注意一下边界条件。

以及$0$~$i-1$这个条件没有问题。

本文链接:https://acxblog.site/archives/sol-bzoj-3670-3620.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。