BZOJ 4199 [Noi2015] 品酒大会

发布于 2018-01-04  143 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4199

题意:去 UOJ 或者 LOJ 看吧。


差异 这题的加强版?

考虑到如果一对串 r 相似则 0~r-1 均相似,所以可以直接只考虑一对串的最长相似,最后答案做一下前缀和即可。

一对串的最长相似... 不就是这两个后缀的 lcp 吗...

于是翻转串后建后缀自动机转后缀树,对于树上节点维护 mx 和 mn 即可,因为有负负得正。

另外交完 BZ 建议也去 UOJ 交一发... 被 hack 数据洗礼后的程序将会更强大。

 


一个非常弱的准退役OIER