P6698-[BalticOI 2020 Day2]病毒

· · 题解

题目链接: https://www.luogu.com.cn/problem/P6698

更好的阅读体验（也许）

题目大意

有一个包含 0\sim G-1 的字符集，其中有 n 种变换，能够将一个字符 a_i(a_i>1) 变为一串字符 b_i ，当一个字符串中只剩下 0 和 1 时变换就结束了。

然后给出 m 个匹配串 c_i 。现在对于每个字符 i\in[2,G-1] ，是否字符 i 无论变化结束时都含有至少一个匹配串，如果不是，求一个最短的不包含任何匹配串的最终串长度。

保证每个在 [2,G-1] 的字符都能进行变化，匹配串中只包含 0/1 。

\sum t_i\leq 50,\sum |b_i|\leq 100,n\leq 100,2<G\leq n+2

解题思路

有匹配的问题，我们先拿所有的 c_i 出来建一棵 AC 自动机 ，然后考虑怎么计算每个字符能从哪个状态跳到哪个状态。

注意我们在 AC 自动机 上走状态时不能走到包含匹配串的状态，这样我们可以将无论如何都包含匹配串视为最短不包含匹配串的长度无穷大。

那么我们考虑 dp 这个最短的长度，设 f_{i,s,t} 表示字符 i 经过变换后，能从状态 s 走到状态 t 的最短长度。

转移时我们考虑枚举一个变换 i ，再枚举一个起点 s ，然后设 g_{j,x} 表示现在走到 b_{i,j} ，在状态 x 时的最短长度，那么转移时就有

g_{j+1,y}=min\{g_{j,x}+f_{b_{i,j},x,y}\}

但是会注意到 f_{i,s,t} 之间的转移并不是一个单向的关系，会发现这是一个和最短路很类似的转移，我们考虑魔改一下 SPFA 。

我们先把 0,1 加入队列，然后每次取出队头 x ，我们把所有包含字符 x 的 b_i 都拿出来跑一次 g ，如果这次跑出来的 g 能够更新 f_{a_i,s,t} ，那么我们就把 a_i 入队（如果之前 a_i 不在队列中）。

我们视 SPFA 的复杂度为 O(n^2) ，记 AC 自动机状态数为 k ，每做一次转移应该是 O(|b_i|k^3) ，那么这题中 SPFA 的复杂度应该就是 O(G\sum |b_i|k^3) ，实际上跑起来常数会很小，可以通过本题。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const ll N=105,inf=1e18;
ll G,n,m,a[N],f[N][N][N],g[N][52];
ll cnt,ch[N][2],fail[N];bool ed[N],v[N];
queue<int> q;vector<int> b[N],T[N];
void ins(ll n){
    ll x=0;
    for(ll i=1,c;i<=n;i++){
        scanf("%lld",&c);
        if(!ch[x][c])ch[x][c]=++cnt;
        x=ch[x][c];
    }
    ed[x]=1;return;
}
void getfail(){
    for(ll i=0;i<2;i++)
        if(ch[0][i])q.push(ch[0][i]);
    while(!q.empty()){
        ll x=q.front();q.pop();
        ed[x]|=ed[fail[x]];
        for(ll i=0;i<2;i++){
            if(ch[x][i]){
                fail[ch[x][i]]=ch[fail[x]][i];
                q.push(ch[x][i]);
            }
            else ch[x][i]=ch[fail[x]][i];
        }
    }
    return;
}
bool solve(int i){
    bool flag=0;
    for(ll s=0;s<=cnt;s++){
        if(ed[s])continue;
        memset(g,0x3f,sizeof(g));g[0][s]=0;
        for(ll j=0;j<b[i].size();j++){
            for(ll x=0;x<=cnt;x++){
                if(g[j][x]>=inf)continue;
                for(ll y=0;y<=cnt;y++)
                    g[j+1][y]=min(g[j+1][y],g[j][x]+f[b[i][j]][x][y]);
            }
        }
        for(ll x=0;x<=cnt;x++){
            flag|=(g[b[i].size()][x]<f[a[i]][s][x]);
            f[a[i]][s][x]=min(f[a[i]][s][x],g[b[i].size()][x]);
        }
    }
    return flag;
} 
void SPFA(){
    q.push(0);q.push(1);v[0]=v[1]=1;
    while(!q.empty()){
        int x=q.front();q.pop();v[x]=0;
        for(int i=0;i<T[x].size();i++){
            int y=T[x][i];
            if(solve(y)&&!v[a[y]])
                q.push(a[y]),v[a[y]]=1;
        }
    }
    return;
}
signed main()
{
    scanf("%lld%lld%lld",&G,&n,&m);
    for(ll i=1,k;i<=n;i++){
        scanf("%lld%lld",&a[i],&k);
        for(ll j=1,x;j<=k;j++){
            scanf("%lld",&x),b[i].push_back(x);
            T[x].push_back(i);
        }
    }
    for(ll i=1,k;i<=m;i++){
        scanf("%lld",&k);
        ins(k);
    }
    getfail();ll k=0;
    memset(f,0x3f,sizeof(f));
    for(ll i=0;i<=cnt;i++){
        if(ed[i])continue;
        if(!ed[ch[i][0]])f[0][i][ch[i][0]]=1;
        if(!ed[ch[i][1]])f[1][i][ch[i][1]]=1;
    }
    SPFA();
    for(ll i=2;i<G;i++){
        ll ans=inf;
        for(ll x=0;x<=cnt;x++)
            ans=min(ans,f[i][0][x]);
        if(ans>=inf)puts("YES");
        else printf("NO %lld\n",ans);
    }
    return 0;
}

题外话

最开始我是直接暴力把所有的变换的转移跑了 G 次发现过了。

但是我证不出来为啥这样是对的（虽然感觉应该和 SPFA 的做法差不多），所以就又写了个 SPFA 的版本。

希望有大佬指点 /kk 。