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++ ,