menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[贪心+后缀自动机+线段树合并]Codeforces700E【Cool Slogans】题解
apps Codeforces
local_offer 查看标签
comment 0 条评论

题目概述

有一个串,现在要找出这个串的一个子串使得这个子串在原串出现了至少 $2$ 次,接着对这个子串继续操作直到无法操作为止。求最多操作多少次。

解题报告

Div.1好难啊……因为要求最大值,所以贪心,对于每个串,肯定是变成最长的满足条件的串。反过来看这个问题就是从一个串开始不停扩展最多能扩展多少次,一个串能够扩展说明他在除了自己的位置上还有出现的位置。

因为是子串问题所以考虑后缀自动机,那么上述条件就是一个节点的 $Right$ 集合中至少有一个元素在某个区间中,因此我们可以在 $Right$ 集合组成的树上从上往下做贪心,记录 $f_i,pos_i$ 表示从根到 $i$ 的最大扩展次数和 $i$ 从哪个节点转移就好了。

$Right$ 集合怎么求啊?线段树合并大法好!由于 $Right$ 集合有要么包含要么不相交的性质,所以可以直接暴力合并,比主席树方便一些。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=400000,maxi=26,maxt=1e7;

int n,ha[maxn+5],who[maxn+5],ro[maxn+5],len,ls[maxt+5],rs[maxt+5],ans;char s[maxn+5];
int si=1,p=1,son[maxn+5][maxi],fa[maxn+5],MAX[maxn+5],ID[maxn+5],f[maxn+5],pos[maxn+5];

inline void Extend(int w,int i){
    int np=++si;MAX[np]=MAX[p]+1;ID[np]=i;while (p&&!son[p][w]) son[p][w]=np,p=fa[p];
    if (!p) fa[np]=1; else{
        int q=son[p][w];if (MAX[p]+1==MAX[q]) fa[np]=q; else{
            int nq=++si;MAX[nq]=MAX[p]+1;ID[nq]=i;memcpy(son[nq],son[q],sizeof(son[q]));
            fa[nq]=fa[q];fa[np]=fa[q]=nq;while (p&&son[p][w]==q) son[p][w]=nq,p=fa[p];
        }
    }p=np;
}
void Insert(int &p,int pos,int l=1,int r=n){
    if (!p) p=++len;if (l==r) return;int mid=l+(r-l>>1);
    if (pos<=mid) Insert(ls[p],pos,l,mid); else Insert(rs[p],pos,mid+1,r);
}
int Merge(int A,int B) {if (!A||!B) return A+B;int p=++len;ls[p]=Merge(ls[A],ls[B]);rs[p]=Merge(rs[A],rs[B]);return p;}
inline void Make(){
    for (int i=1;i<=si;i++) ha[MAX[i]]++;for (int i=1;i<=n;i++) ha[i]+=ha[i-1];for (int i=1;i<=si;i++) who[ha[MAX[i]]--]=i;
    for (int j=si,i=who[j];j>1;i=who[--j]) Insert(ro[i],ID[i]),ro[fa[i]]=Merge(ro[fa[i]],ro[i]);
}
bool Ask(int p,int L,int R,int l=1,int r=n){
    if (!p) return false;if (L==l&&r==R) return true;int mid=l+(r-l>>1);
    if (R<=mid) return Ask(ls[p],L,R,l,mid);if (L>mid) return Ask(rs[p],L,R,mid+1,r);
    return Ask(ls[p],L,mid,l,mid)||Ask(rs[p],mid+1,R,mid+1,r);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%s",&n,s+1);for (int i=1;i<=n;i++) Extend(s[i]-'a',i);Make();
    for (int j=(f[1]=0,pos[1]=ans=1,2),i=who[j];j<=si;i=who[++j]){
        if (fa[i]==1||Ask(ro[pos[fa[i]]],ID[i]-MAX[i]+MAX[pos[fa[i]]],ID[i]-1)) f[i]=f[fa[i]]+1,pos[i]=i;
        else f[i]=f[fa[i]],pos[i]=pos[fa[i]];ans=max(ans,f[i]);
    }printf("%d\n",ans);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up