[LOJ3049] [十二省联考 2019] 字符串问题

题目链接

LOJ：https://loj.ac/problem/3049

洛谷：https://www.luogu.org/problemnew/show/P5284

BZOJ：https://www.lydsy.com/JudgeOnline/problem.php?id=5496

Solution

小清新字符串题

不过小样例是真的强，窝调了一小时样例然后1A了

思路还是很清晰的，首先可以得到一个\(O(n^3)\)的暴力，我们直接大力枚举然后匹配连边，然后\(\rm toposort\)求最长连就好了，注意有环就无解。

然后我们大力优化这个暴力就好了，我们用后缀树优化建边，每个子串倍增定位，然后对应到后缀树的点上就好了。

但是这样是不对的，对于\(a\geqslant b\)的情况这样是没有问题的，否则一个点可能有很多\(a,b\)，那么长度大的\(b\)不能连向\(a\)。

所以有两种思路，一是类似虚树的把所有需要用的点都建出来，二是每个点开个\(\rm vector\)然后把子串挂在\(\rm vector\)上，然后\(\rm sort\)之后连边就好了。

复杂度都是\(O(n\log n)\)，下面代码写的是第二种。

#include<bits/stdc++.h>

using namespace std;

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

#define ll long long 

void print(ll x) {

    if(x<0) putchar('-'),x=-x;

    if(!x) return ;print(x/10),putchar(x%10+48);

}

void write(ll x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double

#define pii pair<int,int >

#define vec vector<int >

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

const int maxn = 8e5+10;

const int inf = 1e9;

const lf eps = 1e-8;

ll dis[maxn];

char s[maxn];

vector<int > t[maxn];

int par[maxn],ml[maxn],tr[maxn][26],lstp=1,stot=1,fa[maxn][20];

int pos[maxn],na,nb,posa[maxn],posb[maxn],len[maxn],is[maxn],lst[maxn],d[maxn];

int head[maxn],tot;

struct edge{int to,nxt;}e[maxn<<1];

void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot,d[v]++;}

int append(int x) {

    int p=lstp,np=++stot;lstp=np,ml[np]=ml[p]+1;

    for(;p&&tr[p][x]==0;p=par[p]) tr[p][x]=np;

    if(!p) return par[np]=1,np;

    int q=tr[p][x];

    if(ml[q]>ml[p]+1) {

        int nq=++stot;ml[nq]=ml[p]+1;

        memcpy(tr[nq],tr[q],sizeof tr[nq]);

        par[nq]=par[q],par[q]=par[np]=nq;

        for(;p&&tr[p][x]==q;p=par[p]) tr[p][x]=nq;

    } else par[np]=q;

    return np;

}

int cmp(int x,int y) {return len[x]==len[y]?is[x]<is[y]:len[x]<len[y];}

void build() {

    scanf("%s",s+1);

    for(int n=strlen(s+1),i=n;i;i--) pos[i]=append(s[i]-'a');

    for(int i=2;i<=stot;i++) fa[i][0]=par[i];

    for(int i=1;i<=18;i++)

        for(int j=2;j<=stot;j++)

            fa[j][i]=fa[fa[j][i-1]][i-1];

    read(na);

    for(int i=1;i<=na;i++) {

        int l,r;read(l),read(r);

        int now=pos[l];

        for(int j=18;~j;j--) if(ml[fa[now][j]]>=r-l+1) now=fa[now][j];

        t[now].push_back(posa[i]=++stot);

        len[stot]=r-l+1,is[stot]=1;

    }read(nb);

    for(int i=1;i<=nb;i++) {

        int l,r;read(l),read(r);

        int now=pos[l];

        for(int j=18;~j;j--) if(ml[fa[now][j]]>=r-l+1) now=fa[now][j];

        t[now].push_back(posb[i]=++stot);

        len[stot]=r-l+1;

    }

    for(int x=1;x<=stot;x++) {

        int pre=x,L=t[x].size();sort(t[x].begin(),t[x].end(),cmp);

        for(int v,i=0;i<L;i++) {

            v=t[x][i];add(pre,v);

            if(!is[v]) pre=v,len[v]=0;

        }lst[x]=pre;

    }

    for(int x=2;x<=stot;x++) if(par[x]) add(lst[par[x]],x);

    int q;read(q);for(int i=1,x,y;i<=q;i++) read(x),read(y),add(posa[x],posb[y]);

}

void solve() {

    queue<int > q;ll cnt=0,ans=0;while(!q.empty()) q.pop();

    for(int i=1;i<=stot;i++) if(!d[i]) q.push(i);

    while(!q.empty()) {

        int x=q.front();q.pop();cnt++;

        for(int v,i=head[x];i;i=e[i].nxt) {

            v=e[i].to;dis[v]=max(dis[v],dis[x]+len[v]);

            if(!(--d[v])) q.push(v);ans=max(ans,dis[v]);

        }

    }write(cnt==stot?ans:-1ll);

}

void clear() {

    for(int i=1;i<=stot;i++) {

        memset(tr[i],0,sizeof tr[i]);

        memset(fa[i],0,sizeof fa[i]);

        par[i]=ml[i]=len[i]=dis[i]=d[i]=lst[i]=pos[i]=is[i]=head[i]=0;

        t[i].clear();

    }tot=0;stot=lstp=1;

}

int main() {

    int T;read(T);while(T--) build(),solve(),clear();

    return 0;

}

巴特西

[LOJ3049] [十二省联考 2019] 字符串问题

题目链接

Solution

最新文章

热门文章