【BZOJ3670】【NOI2014】动物园

然而这道题并不是按顺序刷的

因为这是今天伦boy出的原题 快乐AC了

昨天正好还在跟小机房的人说我刷BZOJ至少刷玩AC人数一千以上的题,到“数学作业”

然后今天这道题就变成一千以上的最后一题了。。AC人数1004

那么这道题怎么做呢

首先显然要用KMP把\(next\)先求出来

那么我们再考虑求一个\(cnt\)数组:表示可重叠的既是前缀又是后缀的子串个数

这个可以用递推求:\(cnt[x]=cnt[next[x]]+1\),想想就明白了

那\(num\)又如何得到呢

\(num\)与\(cnt\)的区别就是不能重叠,也就是那个子串的长度不能超过原串的一半

那么从一个位置\(x\)一直往前跳\(next\),跳到第一个小于等于\(x\)的一半的地方,记为\(pre[x]\),那么有

$$num[x]=cnt[pre[x]]+1$$

显而易见吧

但是如果暴力跳\(next\)的话复杂度就不对了

不过我们注意到有这样的一个关系:\(pre[next[x]]<=pre[x]\)

利用这个单调性从后往前跳就可以了

说点什么

  Subscribe  
提醒