Processing math: 100%

暴力连边的话,对于原图中的 (x,y) ,将 AxBy 给连上,然后如果 BiAj 的前缀的话,将 BiAj 连上。定义点 A 的权值为其长度,点 B 权值为 0 ,显然答案就是图上的最长路,当然如果出现了环意味着 T 可以是无限长的。

求最长路可以拓扑然后存个权值最大值即可,如果还有入度大于 1 的边说明有环。

容易发现第一部分的边是 m 条,第二部分的是 na×nb 级别的,现在考虑如何优化第二部分。

先考虑 |B||A| 的情况,如果一个 B 的左端点是 xA 的右端点是 y ,要使得 BA 的前缀的话,一定满足 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,i1)
假设当前的 B 的左端点为 p ,其排名为 k ,那么因为跟 min 有关,在 rk 数组上,其连边区间一定是一段连续的包含 k 的区间,具体的说,就是:

  • [1,k] 中,一定存在一个 L 使得 i[L,k],lcp(i,k)|B|i[1,L1],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 条件的情况下从这个 BA 连边,但这个连边是错的。

考虑将 A,B 放在一起,以长度为关键字从大到小排序,对于长度一样的 A,B ,将 A 放在前面。

对于每一个 A ,用可持久化线段树维护。

对于每一个 B ,直接连向当前最后出现的 A 所在版本的线段树对应区间即可。因为同样还要连向更大的 A ,所以可持久化线段树上节点要往其上一版本对应节点连边。

剩下的可持久化线段树上的边无非就是线段树优化建图的同样内容:有儿子往儿子连边,叶子节点往对应的 A 连边即可。

然后注意空间和细节,这道题就没了。

码量主要在后缀数组的板子上?其他的不怎么长(

Code :

代码太长,因此只放部分代码。

若剩下部分需要参考请移步提交记录 https://loj.ac/submission/836201

拓扑:

inline ll topsort() {
    for(int i=1;i<=tot;++i) if(!du[i]) que.push(i);
    while(!que.empty()) {
        int u=que.front();que.pop();
        for(auto v:to[u]) {
            chkmax(dp[v],dp[u]+val[u]);
            if(--du[v]==0) que.push(v);
        }
    }
    ll ans=0;
    for(int i=1;i<=tot;++i) if(du[i]) return -1;
    for(int i=1;i<=tot;++i) chkmax(ans,dp[i]+val[i]);
    return ans;
}
C++

可持久化线段树:

int rt[M];
struct Segment_Tree {
    #define mid ((l+r)>>1)
    int lc[N],rc[N];
    void update(int &now,int las,int l,int r,int pos,int tmp) {
        if(!now) now=++tot;
        if(las) addedge(now,las);
        if(l==r) return addedge(now,tmp),void();

        if(pos<=mid) {
            update(lc[now],lc[las],l,mid,pos,tmp);
            addedge(now,lc[now]),rc[now]=rc[las];
        } else {
            update(rc[now],rc[las],mid+1,r,pos,tmp);
            addedge(now,rc[now]),lc[now]=lc[las];
        }
    }
    void Addedge(int now,int l,int r,int L,int R,int id) {
        if(!now) return ;
        if(L<=l&&r<=R) return addedge(id,now),void();
        if(L<=mid) Addedge(lc[now],l,mid,L,R,id);
        if(R>mid) Addedge(rc[now],mid+1,r,L,R,id);
    }
    #undef mid
} seg;
C++

二分:

for(int i=1;i<=cnt;++i) {
    if(q[i].id<=na)
        ++tmp,
        seg.update(rt[tmp],rt[tmp-1],1,n,sa.rk[q[i].pos],q[i].id);
    else {
        k=sa.rk[q[i].pos];
        l=1,r=L=k;
        while(l<=r) (sa.lcp(mid=(l+r)>>1,k)>=q[i].len)?L=mid,r=mid-1:l=mid+1;
        l=R=k,r=n;
        while(l<=r) (sa.lcp(k,mid=(l+r)>>1)>=q[i].len)?R=mid,l=mid+1:r=mid-1;
        if(L<=R) seg.Addedge(rt[tmp],1,n,L,R,q[i].id);
    }
}
C++
分类: 文章

Qiuly

QAQ

0 条评论

发表回复

Avatar placeholder

您的邮箱地址不会被公开。 必填项已用 * 标注