BZOJ 4199 [Noi2015] 品酒大会


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

题意:去 UOJ 或者 LOJ 看吧。


差异 这题的加强版?

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

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

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

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4199 [Noi2015] 品酒大会


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,