• 链接：
  来源：牛客网

• 题目描述
  经过了选号和漫长的等待，处女座终于拿到了给小姐姐定制的手环，小姐姐看到以后直呼666！
  处女座其实也挺喜欢6这个数字的，实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样，想起了小姐姐。
  现在你要给处女座展示一系列数字，你想知道他的内心会激动多少次。对于同一个数字，他最多只会激动一次，即如果这个数是66666，他还是只会激动一次。
• 输入描述:
  一行包括两个数字l,r，表示你给处女座展示的数字范围为[l,r]。
• 输出描述:
  一行一个整数，表示处女座内心激动的次数。
• 输入
  10 20
• 输出
  1
• 备注:0≤l≤r≤10¹⁸

数位dp就是dfs+记忆化数组的过程:

i=4(千位) 0 1 2 3 4 5 6 7 8 9

i=3(百位) 0 1 2 3 4 5 6 7 8 9

i=2(十位) 0 1 2 3 4 5 6 7 8 9

i=1(个位) 0 1 2 3 4 5 6 7 8 9

dfs其实就是模拟数数的过程,我们假设上限是20,dfs的时候我们数到十位的2时,此时2后面的数不用再数了,到个位的时候我们数到0即可(见代码)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std; typedef long long LL;const int Max_n=100005;LL dp[20][2];///i表示当前位,j表示上一位是否是6 //dp[i][j]表示当前数位没有6的个数 LL a[20]; //if6上一位是否是6,limit上一位是否是上界LL dfs(int len,bool if6,bool limit){ //没有6的个数 if(len==0) return 1;//枚举到个位 if(!limit&&dp[len][if6]) return dp[len][if6]; //没有到达上限并且当前的数位已经统计过,直接统计已经统计过的即可 LL cnt=0,up=limit?a[len]:9;//上一位是上界,这一位也是上界,否则上界是9 for(int i=0;i<=up;++i){ //去数当前位能够数的数(0-9) if(i==6) continue;//如果当前位是6,剪枝 cnt+=dfs(len-1,i==6,limit&&i==a[len]);//上一位是上限,这一位也是上限,下一位一定只数到上限 //当前位是6说明下一位的上一位是6,(实际这里可以不用记录上一位是否是6(让统计的数只有一位)) } if(!limit) dp[len][if6]=cnt;//不是上界,直接记录数好的即可 return cnt;}LL solve(LL num){ int k=0;//记录有多少数位 while(num){ a[++k]=num%10; num/=10; } return dfs(k,false,true);} int main(){ LL l,r; scanf("%lld%lld",&l,&r); printf("%lld\n",r-l+1-solve(r)+solve(l-1)); //我们需要的是有6的个数 return 0;}