[bzoj4199]-[NOI2015]品酒大会

后缀数组真的很棒……

题目(BZOJ)

题目(LibreOJ)

题目(洛谷)

 

这题其实很好做

根据r相似的定义,我们很容易想到这是俩后缀的LCP,所以只需要建个后缀数组就可以了。

题目中的r相似包含r-1到0相似,所以当找到p和q是r相似时,我们就往下处理。

根据预处理的height数组,我们开一个vector,然后按height值从大到小进行处理。

这个处理可以用并查集解决,只需要合并时维护max,min(美味度可能为负),cnt(集合大小),就可以一次性将两个问题处理完了。

(.,…..然而这题我表示一眼过去就是SAM,然而不会写233)

 

发表评论