BZOJ3670(NOI2014)动物园题解

题目传送门
一道水题,据说有O(n)做法,我竟然没想到也没看懂。我的做法是KMP后用next数组搞棵树,然后在树上找一个节点前面最后一个符合条件的节点,一种方法是发现这玩意有单调性,然后用一个point数组记录下其父亲的决策点,再拿个ST表倍增或者Tarjan+二分,也可以利用轻重链搞一搞就可以了。这里用了轻重链。这种方法我只能证明有O(n^2lgn)的上界,但平均效率很高。

还有一种方法是直接倍增,这种方法是严格O(nlgn)的,但平均情况下,时间和空间的开销都比上一种方法要高很多。

0 条评论
发表一条评论