[暑假集训--数位dp]hdu2089 不要62

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

Output

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

Sample Input

1 100
0 0

Sample Output

数位dp

要记一下上一位是不是6

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<deque>

 #include<set>

 #include<map>

 #include<ctime>

 #define LL long long

 #define inf 0x7ffffff

 #define pa pair<int,int>

 #define mkp(a,b) make_pair(a,b)

 #define pi 3.1415926535897932384626433832795028841971

 using namespace std;

 inline LL read()

 {

     LL x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 LL l,r,len;

 LL f[][];

 int d[];

 inline int dfs(int now,int lst,int fp)

 {

     if (now==)return ;

     if (!fp&&f[now][lst]!=-)return f[now][lst];

     LL ans=,mx=(fp?d[now-]:);

     for (int i=;i<=mx;i++)

     {

         if (lst==&&i==||i==)continue;

         ans+=dfs(now-,i,fp&&mx==i);

     }

     if (!fp&&f[now][lst]==-)f[now][lst]=ans;

     return ans;

 }

 inline LL calc(LL x)

 {

     if (x==-)return ;

     if (x==)return ;

     LL xxx=x;

     len=;

     while (xxx)

     {

         d[++len]=xxx%;

         xxx/=;

     }

     LL sum=;

     for (int i=;i<=d[len];i++)

     if (i!=)sum+=dfs(len,i,i==d[len]);

     return sum;

 }

 int main()

 {

     memset(f,-,sizeof(f));

     while (~scanf("%d%d",&l,&r)&&l+r)printf("%lld\n",calc(r)-calc(l-));

 }

hdu 2089

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define LL long long
#define inf 0x7ffffff
#define pa pair<int,int>
#define mkp(a,b) make_pair(a,b)
#define pi 3.1415926535897932384626433832795028841971
using namespace std;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
LL n,len;
LL f[20][13][10][2];
int d[20];
inline int dfs(int now,int rest,int dat,int sat,int fp)
{
if (now==1)return !rest&&sat;
if (!fp&&f[now][rest][dat][sat]!=-1)return f[now][rest][dat][sat];
LL ans=0,mx=(fp?d[now-1]:9);
for (int i=0;i<=mx;i++)
{
if (sat||!sat&&dat==1&&i==3)ans+=dfs(now-1,(rest*10+i)%13,i,1,fp&&mx==i);
else ans+=dfs(now-1,(rest*10+i)%13,i,0,fp&&mx==i);
}
if (!fp&&f[now][rest][dat][sat]==-1)f[now][rest][dat][sat]=ans;
return ans;
}
inline LL calc(LL x)
{
LL xxx=x;
len=0;
while (xxx)
{
d[++len]=xxx%10;
xxx/=10;
}
LL sum=0;
for (int i=0;i<=d[len];i++)
sum+=dfs(len,i,i,0,i==d[len]);
return sum;
}
int main()
{
memset(f,-1,sizeof(f));
while (scanf("%d",&n)!=EOF)printf("%lld\n",calc(n));
}

巴特西

[暑假集训--数位dp]hdu2089 不要62

最新文章

热门文章