暴力连边的话,对于原图中的 (x,y) ,将 Ax→By 给连上,然后如果 Bi 是 Aj 的前缀的话,将 Bi→Aj 连上。定义点 A 的权值为其长度,点 B 权值为 0 ,显然答案就是图上的最长路,当然如果出现了环意味着 T 可以是无限长的。
求最长路可以拓扑然后存个权值最大值即可,如果还有入度大于 1 的边说明有环。
容易发现第一部分的边是 m 条,第二部分的是 na×nb 级别的,现在考虑如何优化第二部分。
先考虑 |B|≤|A| 的情况,如果一个 B 的左端点是 x ,A 的右端点是 y ,要使得 B 是 A 的前缀的话,一定满足 lcp(x,y) 的长度大于 |B| ,这里 lcp(x,y) 指的是 str(x,n) 和 str(y,n) 的最长公共前缀。
然后考虑建出后缀数组,然后求出 height 数组,现在令 lcp(x,y) 表示排名为 x 的后缀和排名为 y 的后缀的最长公共前缀,然后显而易见的是:
lcp(l,r)=rmini=l+1lcp(i,i−1)
假设当前的 B 的左端点为 p ,其排名为 k ,那么因为跟 min 有关,在 rk 数组上,其连边区间一定是一段连续的包含 k 的区间,具体的说,就是:
- 在 [1,k] 中,一定存在一个 L 使得 ∀i∈[L,k],lcp(i,k)≥|B| ,∀i∈[1,L−1],lcp(i,k)<|B| 。
- 在 [k,n] 中,一定存在一个 R 使得 ∀i∈[k,R],lcp(k,i)≥|B| ,∀i∈[R+1,n],lcp(k,i)<|B| 。
这样的话只需要以 rk 为下标建立线段树,先处理出原串的 height 数组后,对于一个 |B| ,二分一下 L,R ,然后在线段树优化建图即可。
这个是 80 分做法。
对于满分做法,因为不保证 |A|≥|B| ,所以可能会在 |A|<|B| 但是满足 lcp 条件的情况下从这个 B 往 A 连边,但这个连边是错的。
考虑将 A,B 放在一起,以长度为关键字从大到小排序,对于长度一样的 A,B ,将 A 放在前面。
对于每一个 A ,用可持久化线段树维护。
对于每一个 B ,直接连向当前最后出现的 A 所在版本的线段树对应区间即可。因为同样还要连向更大的 A ,所以可持久化线段树上节点要往其上一版本对应节点连边。
剩下的可持久化线段树上的边无非就是线段树优化建图的同样内容:有儿子往儿子连边,叶子节点往对应的 A 连边即可。
然后注意空间和细节,这道题就没了。
码量主要在后缀数组的板子上?其他的不怎么长(
Code :
代码太长,因此只放部分代码。
若剩下部分需要参考请移步提交记录 https://loj.ac/submission/836201 。
0 条评论