注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

bzoj3238【AHOI2013】差异解题报告  

2014-04-14 09:15:00|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目链接

大意是对后缀两两求(长度和-2*lcp)

丽洁出的题= =,orz无限……

(WJMZBMR:现在SA早就过时了,要用SAM!!!不,其实SAM也过时了,现在是Suffix BST以及2K Substring BST,但考虑到AH太弱了,同情一下,降低一点难度……)

这题线下测用后缀数组会被卡掉的,正确做法应该是后缀自动机,但是我太弱不会= =||

没关系,反正bzoj上也不会被卡

//其实这题用SA也可以达到O(n)复杂度,但是由于DC3常数过大就……;

PS:丽洁你还让不让人活?!

然后我去网上搜了一下题解(求大神不鄙视)

我就搞不明白为什么大多数题解都是笛卡尔树= =

其实呢,poj上有一道算法类似的题目,poj3415

=============扯淡到此结束===========

首先呢,我们知道两两后缀的长度和是可以O(1)搞出来的对吧。

所以主要难在求两两后缀的lcp。

因为是两两后缀求lcp,所以顺序什么的是无关紧要的对吧,方便起见把后缀造个SA。

方法1:暴力枚举后缀……大约最大的数据要跑40分钟

方法2:

我们从lcp的性质入手。

两个后缀的lcp就是height求一个rmq对吧

我们拿个实例来分析一下

bzoj3238【AHOI2013】差异解题报告 - mxh1999 - 一个蒟蒻的代码回收站

图比较渣= =,求轻喷

abaaab对上面各个后缀的lcp分别是1,1,1,1,2,然后我们发现这个东西是单调不降的!

于是,我们搞一个栈表示前面各个lcp,然后如果height[i]<栈顶元素,就把栈顶元素弹出来,然后加一下就好了。

由于每个height只会入栈一次,所以复杂度是O(n),(额……前提是你后缀数组得用DC3,不然SA建出来就已经T掉了)。

实现的时候比较麻烦= =,大家根据程序理解吧

由于我太弱,SA写了倍增= =,所以跑的非常慢,求大神改成DC3……


#include<cstdio>
  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017