題目鏈接：http://acm.bupt.edu.cn/onlinejudge/newoj/showProblem/show_problem.php?problem_id=652
題意：給定數字A和B，問區間[L,R]之間有多少個數字不包含0且至少包含數字A或B中的一個?
思路：用A和B建立自動機。f[dep][id][allZero][ok]表示深度dep、節點id、之前是否全0、是否包含A或B的個數。
struct node
{
int next[10],fail,flag;
void init()
{
clr(next,0);
fail=0;
flag=0;
}
};
node a[N];
int e;
i64 n,m;
void insert(char s[])
{
int i,k,p=0;
for(i=0;s[i];i++)
{
k=s[i]-'0';
if(a[p].next[k]==0)
{
a[e].init();
a[p].next[k]=e++;
}
p=a[p].next[k];
}
a[p].flag=1;
}
queue<int> Q;
void build()
{
int i,j,k,p,q;
FOR0(i,10) if(a[0].next[i]) Q.push(a[0].next[i]);
while(!Q.empty())
{
k=Q.front();
Q.pop();
for(i=0;i<10;i++)
{
if(a[k].next[i])
{
p=a[k].next[i];
q=a[k].fail;
Q.push(p);
a[p].fail=a[q].next[i];
a[p].flag|=a[a[p].fail].flag;
}
else
{
q=a[k].fail;
a[k].next[i]=a[q].next[i];
}
}
}
}
i64 f[20][205][2][2];
int b[20],bNum;
i64 DFS(int id,int dep,int flag,int ok,int allZero)
{
if(dep==-1) return ok==1;
if(!flag&&f[dep][id][allZero][ok]!=-1) return f[dep][id][allZero][ok];
int R=flag?b[dep]:9;
int i,x;
i64 ans=0;
if(allZero&&dep) ans+=DFS(id,dep-1,flag&&R==0,ok,allZero);
FOR1(i,R)
{
x=a[a[id].next[i]].flag;
ans+=DFS(a[id].next[i],dep-1,flag&&i==R,ok|x,0);
}
if(!flag) f[dep][id][allZero][ok]=ans;
return ans;
}
i64 cal(i64 x)
{
clr(f,-1);
bNum=0;
while(x)
{
b[bNum++]=x%10;
x/=10;
}
return DFS(0,bNum-1,1,0,1);
}
char str[30];
int main()
{
int C;
RD(C);
while(C--)
{
a[0].init();e=1;
int i;
RD(n,m);
RD(str); insert(str);
RD(str); insert(str);
build();
i64 ans=cal(m)-cal(n-1);
PR(ans);
}
return 0;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
