处女座和小姐姐（三）-数位dp1.0

链接：https://ac.nowcoder.com/acm/contest/329/G
来源：牛客网

题目描述

经过了选号和漫长的等待，处女座终于拿到了给小姐姐定制的手环，小姐姐看到以后直呼666！

处女座其实也挺喜欢6这个数字的，实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样，想起了小姐姐。

现在你要给处女座展示一系列数字，你想知道他的内心会激动多少次。对于同一个数字，他最多只会激动一次，即如果这个数是66666，他还是只会激动一次。

输入描述:

一行包括两个数字l,r，表示你给处女座展示的数字范围为[l,r]。

输出描述:

一行一个整数，表示处女座内心激动的次数。

示例1

输入

10 20

输出

1

备注:

0≤l≤r≤1018

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

ll dp[][];///dp[i][j]表示i+1位数，且以j为开头，不包含6的数的个数

void init()

{

    memset(dp,,sizeof(dp));

    dp[][]=;

    for(int i=;i<;i++)///i表示从右往左开始第几位，j表示第i位上的数字

    {

        for(int j=;j<;j++)

        {

            for(int k=;k<;k++)

                if(j!=)///不累计第i位上数字为6的个数

                dp[i][j] += dp[i-][k];

        }

    }

}

ll solve(ll x)//求 1到(x-1)里 不包含6的数 的个数

{

    ll temp=x;

    int num[];

    int cnt=;

    while(x)//记录各个位置上的数字

    {

        num[cnt++]=x%;

        x=x/;

    }

    num[cnt]=;

    ll res=;

    for(int i=cnt-;i>;i--)///有多少位

    {

        for(int j=;j<num[i];j++)//如果该位上数字为0的话，是不满足累加要求的

        {

           // if(j!=6) //这一步可以不要的，因为dp[i][6]=0

            res+=dp[i][j];

        }

        if(num[i]==)///比如3650，遇到6，后面直接不用算了

            break;

    }

    return temp-res;//返回不包含6的数字的个数

}

int main()

{

    init();

    ll l,r;

    while( scanf("%lld%lld",&l,&r)!=EOF )

    {

        ll ans;

        ans=solve(r+)-solve(l);

        printf("%lld\n",ans);

    }

    return ;

}

处女座和小姐姐（三）-数位dp1.0的相关教程结束。