[BZOJ1717/Luogu2852][Usaco2006 Dec]Milk Patterns 产奶的模式(后缀数组,单调队列)

发布于 2018-03-25  5 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1717/Luogu2852][Usaco2006 Dec]Milk Patterns 产奶的模式(后缀数组,单调队列)

Description

农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查,他发现:虽然他不能预见明天产奶的质量,但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时,这个长度为4。

Tag

后缀数组,单调队列

题目大意

求出现次数大于K的最长子串

解决思路

后缀数组求出Height后,问题转化为求数列中连续长度为K的连续数列中最小值的最大值,这个可以用单调队列维护。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1717/Luogu2852][Usaco2006 Dec]Milk Patterns 产奶的模式(后缀数组,单调队列)


HNCJ OIer 一枚