BZOJ1966: [Ahoi2005]VIRUS 病毒检测【Trie + DP】

1966: [Ahoi2005]VIRUS 病毒检测

【题目描述】

传送门

【题解】

在Trie树上DP,但是内存太小了,只能卡一卡过了。

代码如下

#include<queue>
#include<cstdio>
#include<cstring>
#include<bitset>
using namespace std;
const int MOD=1005*305;
int n,hd,tl,cnt,Ans,Son[505*505][5],W[505*505];
char ch[1005],c[505];
struct xcw{int Now,j;};
xcw que[MOD];
bitset<1005> vis[MOD];
int get(char x){
    if(x=='A') return 0;
    if(x=='C') return 1;
    if(x=='G') return 2;
    if(x=='T') return 3;
    return -1;
}
void Insert(char *s){
    int Now=0,Len=strlen(s);
    for(int i=0;i<Len;i++){
        if(!Son[Now][get(s[i])]) Son[Now][get(s[i])]=++cnt;
        Now=Son[Now][get(s[i])];
    }
    W[Now]++;
}
void Push(xcw x){
    if(vis[x.Now][x.j]) return;
    if(++tl>=MOD) tl-=MOD;
    que[tl]=x;vis[x.Now][x.j]=1;
}
void Solve(char *s){
    int Len=strlen(s);hd=tl=0;Push((xcw){0,0});
    while(hd^tl){
        if(++hd>=MOD) hd-=MOD;
        xcw x=que[hd];
        if(x.j-1>=0&&s[x.j-1]=='*') for(int i=0;i<4;i++) if(Son[x.Now][i]) Push((xcw){Son[x.Now][i],x.j});
        if(x.j>=Len){Ans+=W[x.Now],W[x.Now]=0;continue;}
        if(get(s[x.j])!=-1&&Son[x.Now][get(s[x.j])]) Push((xcw){Son[x.Now][get(s[x.j])],x.j+1});
        if(get(s[x.j])==-1){
            for(int i=0;i<4;i++) if(Son[x.Now][i]) Push((xcw){Son[x.Now][i],x.j+1});
            if(s[x.j]=='*') Push((xcw){x.Now,x.j+1});
        }
    }
}
int main(){
    scanf("%s%d",ch,&n);
    for(int i=1;i<=n;i++) scanf("%s",c),Insert(c);
    Solve(ch);
    printf("%d\n",n-Ans);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部