【NOI2016】优秀的拆分


暴力分析

似乎暴力就有95分啊?

先\(O(n^2)\)预处理双hash,用来判断子串是否相同

然后\(O(n^2)\)处理\(f[i]\),\(f[i]\)表示结尾位置为\(i\),满足\(AA\)的子串数量

然后可以直接根据\(f[i]\)在\(O(n^2)\)的的时间内得到\(g[i]\),\(g[i]\)表示,结尾为i满足\(AABB\)的子串数量

很基础啊?


满分算法分析

当时考场上没打算为了这5分再去思考啊

不过正解的思想还是很不错的

基于上面的思想,我们可以看到$$ans=\sum_{i=1}^{i<n} f[i]*g[i+1]$$其中\(f[i]\)表示以第\(i\)位作为结束位的形如\(AA\)的个数,\(g[i]\)表示以第\(i\)位作为开始位的形如\(AA\)的个数

现在的问题就是怎么快速的求\(f[i]\)和\(g[i]\)

在UOJ群上围观了Claris秒题以后,大概知道了怎么弄QAQ

我们枚举\(AA\)串中\(A\)的长度\(L\)。在原串上,我们每隔\(L\)设置一个关键点,可以发现,若\(A\)的长度为\(L\),\(AA\)必定恰好经过某两个相邻的关键点。于是我们可以枚举\(AA\)经过的关键点

考虑两个相邻的关键点\(a,b\),有\(b=a+L\),我们求出\(a,b\)的最长公共前缀\(p\)和最长公共后缀\(s\)。若\(p+s>L\),\(AA\)串就一定存在,可以画个图来直观理解一下

那么,我们就可以直接得出可行的开始位置的区间为\([a-s+1,a+p-l]\),可行的结束位置为\([b-s+l,b+p-1]\)

直接暴力枚举的时间复杂度是\(T(n)=\sum_{i=1}^{n} \frac{n}{i}=nlogn\)

————

现在还有一个问题是怎么求\(a,b\)的最长公共前缀\(p\)和最长公共后缀\(s\)

首先可以看一下uoj35,他所求的是相邻\(rank\)的LCP

我们假设\(h[i]=LCP\{suffix(sa[i-1]),suffix(sa[i])\}\)

可以得到对于任意的\(j\)和\(k\)(假设\(rank[j]<rank[k]\)),\(LCP\{suffix(j),suffix(k)\}=min\{h[rank[j]+1],h[rank[j]+2],\cdots ,height[rank[k]]\}\)

直接用ST预处理,每次询问都是$O(1)$,对上述复杂度无影响

PS.注意,我的代码使用SAM来构造SA的,由于SAM建立的时候会有新的节点产生,所以数组需要开大一些,不然会gg

——-

然后最后的一份问题就是要进行区间加1的操作,直接差分即可,不要再往复杂度上加无谓log

 

You may also like

【TJOI2015】弦论

【AHOI2013】差异

LEAVE A COMMENT

Statistics

  • 1
  • 8,096

Categories

Archive

Comments