数位动规——准考证号

数位动规——准考证号

第一次发博客，是个萌新（蒟蒻），如有不对或其他问题请联系。

题目如下：

准考证号(ticket.cpp)

       蒟蒻AACSP2020惨跪，他依稀记得他的准考证号是37，现在AA又将要面临一场比赛，他希望准考证号不出现37（连续），同时他又十分讨厌4，所以也不希望4出现在准考证号中。。。现在他想知道在A和B之间有多少合法的准考证号

输入

包含两个整数，A B

输出

一个整数。

样例输入

【输入样例一】

1 10

【输出样例一】

9

【输入样例二】

25 50

【输出样例二】

14

【数据规模和约定】

20%的数据，满足 1 <= A <= B <= 1000000 。

100%的数据，满足 1 <= A <= B <= 2000000000 。

题目分析:

        这是一道动态规划的题，我们先大致看一下，看到数据范围更确定它是一道数位动规的题目（毕竟你也不可能开出20亿大小的数组）。

        接下来便是做了（蒟蒻的我看到了大佬的题解，写的很好，借鉴了一下，并加上了自己的理解）。

        下面是代码。

//#define LOCAL
#include <bits/stdc++.h>
#define COMMENT
using namespace std;
int a,b;
int f[12][10];
int ten[15]={0,1};//基数数组
inline int read()//快读（丑陋的压行） 
{char ch=getchar();int s=0,w=1;while (ch<'0'||ch>'9'){if (ch=='-') w=-1;ch=getchar();}while (ch>='0'&&ch<='9'){s=s*10+ch-'0',ch=getchar();}return s*w;
}
inline void init()
{for (int i=0;i<=9;++i)	//初始化个位数 if (i!=4) f[1][i]=1;for (int i=2;i<=10;++i)	//枚举位数for (int j=0;j<=9;++j)//第i位的状态for (int k=0;k<=9;++k)	//第i-1位的状态if (j!=4&&k!=4&&(j!=3||k!=7))f[i][j]+=f[i-1][k];
}
inline int dp(int x)
{if (!x) return 0;int ans=0,l=10,last=0,cnt=0;while (ten[l]>x) l--;//l为x的位数 for (int i=1;i<l;++i)//小于x位数的数肯定都可以取到。 for (int j=1;j<=9;++j)ans+=f[i][j];cnt=x/ten[l];x%=ten[l];//后面的位数已经处理完了，不需要再考虑了//只需要考虑剩下的位数上的数即可if (l==1) for (int i=1;i<=cnt;++i)ans+=f[l][i];//如果只有一位，进行处理（之前未处理过）else for (int i=1;i<cnt;++i)//注意'='的有无 ans+=f[l][i];//比cnt小的位数都可以取到last=cnt;for (int i=l-1;i;--i) {if (cnt==4) continue;//如果该位是4就不进行处理(之后也可以有符合的情况) cnt=x/ten[i];x%=ten[i];if (i==1)//处理到了就剩一位的情况{ for (int j=0;j<=cnt;++j)//枚举该位的数值 if (last!=3||j!=7)//也不能有"37"的情况 ans+=f[i][j];}else{for (int j=0;j<cnt;++j)//也要注意'=' if (last!=3||j!=7)ans+=f[i][j];}if (last==3&&cnt==7) break;//因为这种情况下含有"37"，剩下的之后的处理是不成立的 (注意理解!)last=cnt;}return ans;
}
int main()
{
#ifdef LOCALfreopen("ticket.in","r",stdin);freopen("ticket.out","w",stdout);
#endifinit();a=read();b=read();for (int i=2;i<=10;++i) ten[i]=ten[i-1]*10;printf("%dn",dp(b)-dp(a-1));return 0;
}
#ifndef COMMENT
//f(i,j)表示长度为i,开头为j的合法方案数.
//则f(i,j)=Σf(i-1,k) (k!=4,j!=4,k!=7 or j!=3)
#endif

        巨佬勿喷（给点信心，谢谢）。