当前位置:编程学习 > C/C++ >>

zoj 3494 BCD Code

题目大意:求a到b之间的数满足翻译成bcd码后没有禁止串的个数。

题目思路:ac自动机加按位dp,需要注意的是,一般在a的长度比b短时,我们会进行加零处理,这样由于0是不存在的,匹配的时候前导0也不能进行匹配,需要特殊判断一下。

[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<string> 
#include<queue> 
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<list> 
#include<iostream> 
#include<map> 
using namespace std; 
#define inf 0x3f3f3f3f 
#define Max 110 
#define mod 1000000009 
int max(int a,int b) 

    return a>b?a:b; 

int min(int a,int b) 

    return a<b?a:b; 

int q[25*110]; 
int cnt; 
char mp[20][10]={"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001"}; 
int up[300],down[300]; 
int dp[220][2][2][22*110]; 
int lena,lenb; 
struct node 

    int cnt,fail; 
    int next[2]; 
    void init() 
    { 
        cnt=fail=0; 
        memset(next,0,sizeof(next)); 
    } 
}tri[25*110]; 
void insert(char *s) 

    int i,p,x; 
    p=0; 
    for(i=0;s[i];i++) 
    { 
        x=s[i]-'0'; 
        if(!tri[p].next[x]) 
        { 
            tri[++cnt].init(); 
            tri[p].next[x]=cnt; 
        } 
        p=tri[p].next[x]; 
    } 
    tri[p].cnt++; 

void bfs() 

    int i,p,head,tail,suf; 
    p=0; 
    head=tail=0; 
    for(i=0;i<2;i++) 
    { 
        if(tri[0].next[i]) 
        { 
            q[tail++]=tri[0].next[i]; 
            tri[q[tail-1]].fail=0; 
        } 
    } 
    while(head<tail) 
    { 
        p=q[head++],suf=tri[p].fail; 
        tri[p].cnt+=tri[suf].cnt; 
        for(i=0;i<2;i++) 
        { 
            if(tri[p].next[i]) 
            { 
                q[tail++]=tri[p].next[i]; 
                tri[q[tail-1]].fail=tri[suf].next[i]; 
            } 
            else 
                tri[p].next[i]=tri[suf].next[i]; 
        } 
    } 

int dfs(int pos,int bg,int sl,int k) 

    if(pos==lenb) return 1; 
    int ans=0,i,j,l,r,x,tmp; 
    if(dp[pos][bg][sl][k]!=-1) 
        return dp[pos][bg][sl][k]; 
    ans=0; 
    l=bg?0:down[pos]; 
    r=sl?9:up[pos]; 
    for(i=l;i<=r;i++) 
    { 
        tmp=k; 
        if(pos>=lenb-lena||bg||i) 
        { 
            for(j=0;j<4;j++) 
            { 
                x=mp[i][j]-'0'; 
                tmp=tri[tmp].next[x]; 
                if(tri[tmp].cnt) 
                    break; 
            } 
        } 
        if(tri[tmp].cnt) continue; 
        ans=(ans+dfs(pos+1,bg|(i>down[pos]),sl|(i<up[pos]),tmp))%mod; 
    } 
    dp[pos][bg][sl][k]=ans; 
    return ans; 

char str[100],a[300],b[300],c[300]; 
int main() 

    int i,t,n; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d",&n); 
        memset(dp,-1,sizeof(dp)); 
        cnt=0; 
        tri[0].init(); 
        while(n--) 
        { 
            scanf("%s",str); 
            insert(str); 
        } 
        bfs(); 
        scanf("%s%s",a,b); 
        lena=strlen(a); 
        lenb=strlen(b); 
        if(lena<lenb) 
        { 
            strcpy(c,a); 
            for(i=0;i<lenb-lena;i++) 
    &nb

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,