BZOJ 4032 trie树+各种乱搞

思路：

先对b 的所有后缀建立trie树

第一问

暴力枚举a串的起点

在trie树上跑找到最短的

第二问

也是暴力枚举a串的起点

a和b顺着暴力匹配就好

第三问

求出来a在第i个位置加一个字母j 能够到的最近的位置 f[i][j] 到最后就是inf

从f[0][j]DFS 在trie上跟着跑找到最小的deep更新答案

第四问

先按照求f一样同理求出b串的 g

dp[i][j]表示a的前i个位置 b不得不匹配到b的第j个位置

dp[i+1][j]=min(dp[i+1][j],dp[i][j]),

dp[i+1][g[j][a[i]]]=min(dp[i+1][g[j][a[i]]],dp[i][j]+1);

1—>strlen(a)+1 min dp[i][inf]就是答案

这题看起来简单其实感觉在考场根本写不出来...

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=,inf=;

int ch[N*N/][],f[N][],g[N][],dp[N][N],cnt,ans1,ans2,ans3,ans4,vis[];

void insert(char *a){

    int now=;

    for(int i=;a[i];i++){

        if(!ch[now][a[i]])ch[now][a[i]]=++cnt;

        now=ch[now][a[i]];

    }

}

int solve1(char *a){

    int now=,i;

    for(i=;a[i];i++){

        if(!ch[now][a[i]])return i+;

        else now=ch[now][a[i]];

    }return inf;

}

void solve3(int x,int now,int deep){

    if(x==inf)return;

    if(!now&&deep){ans3=min(ans3,deep);return;}

    for(int i=;i<=;i++)solve3(f[x][i],ch[now][i],deep+);

}

char a[N],b[N];

int main(){

    scanf("%s%s",a+,b+);

    int n1=strlen(a+),n2=strlen(b+);

    for(int i=;i<=n1;i++)a[i]=a[i]-'a'+;

    for(int i=;i<=n2;i++)b[i]=b[i]-'a'+;

    for(int i=;i<=n2;i++)insert(b+i);

    ans1=ans2=ans3=ans4=inf;

    for(int i=;i<=n1;i++)ans1=min(ans1,solve1(a+i));

    for(int i=;i<=n1;i++){

        int now=;

        for(int j=;i+j<=n1;now++,j++){

            while(a[i+j]!=b[now]&&now<=n2)now++;

            if(now>n2){ans2=min(ans2,j+);break;}

        }

    }

    for(int i=;i<=n1;i++){

        memset(vis,,sizeof(vis));

        for(int j=i+;j<=n1;j++)if(!vis[a[j]])vis[a[j]]=j;

        for(int j=;j<=;j++)f[i][j]=vis[j]?vis[j]:inf;

    }solve3(,,);

    for(int i=;i<=n2;i++){

        memset(vis,,sizeof(vis));

        for(int j=i+;j<=n2;j++)if(!vis[b[j]])vis[b[j]]=j;

        for(int j=;j<=;j++)g[i][j]=vis[j]?vis[j]:inf;

    }

    memset(dp,0x3f,sizeof(dp)),dp[][]=;

    for(int i=;i<=n1;i++)

        for(int j=;j<=n2;j++)

            dp[i+][j]=min(dp[i+][j],dp[i][j]),

            dp[i+][g[j][a[i]]]=min(dp[i+][g[j][a[i]]],dp[i][j]+);

    for(int i=;i<=n1+;i++)ans4=min(ans4,dp[i][inf]);

    printf("%d\n%d\n%d\n%d\n",ans1==inf?-:ans1,ans2==inf?-:ans2,ans3==inf?-:ans3,ans4==inf?-:ans4);

}

巴特西

BZOJ 4032 trie树+各种乱搞

最新文章

热门文章