链接: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<iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef double db;
int shuwei[];
ll dp[][];//dp[i][j],i是当前数位,j是两种情况,j==1表示当前位的这个数为6,j==0表示当前位的这个数不为6
//dp[i][j]表示[0,当前位的数]不含6的个数
ll dfs(int pos,int pre,bool limit)//pos是当前位数,pre是代表两种情况,limit判断是否为上界
{
if(pos==-)//是否超出统计数位
return ;
if(!limit&&dp[pos][pre]!=-)//如果当前数位的数不是6
return dp[pos][pre];
int now=limit?shuwei[pos]:;
ll cnt=;//记录区间内不含6的个数
for(int i=;i<=now;++i)
{
if(i==)
continue;
cnt+=dfs(pos-,i,limit&&(i==now));
}
if(!limit)
dp[pos][pre]=cnt;
return cnt;
}
ll solve(ll x)
{
int d=;
memset(dp,-,sizeof(dp));
while(x)
{
shuwei[d++]=x%;//将数x分解成个十百千位后逆序存进数组
x/=;
}
return dfs(d-,,true);//从最高位开始处理,预留了一个前导零
}
int main()
{
ll n,m;
cin>>n>>m;
ll ans=m-n+-(solve(m)-solve(n-));
cout<<ans<<endl;
return ;
}

 
 

最新文章

  1. Swift3 - String 字符串、Array 数组、Dictionary 字典的使用
  2. redhat 配置本地yum源163yum源epel 源,无需卸载yum!无须拷贝ISO,愿网上少一点垃圾教程误人子弟
  3. windows下docker环境设置
  4. js-DOM,DOM扩展
  5. IOS开发之网络编程--文件压缩和解压缩
  6. Redis附加功能之键过期功能
  7. 关键字 final
  8. noip 2009 细胞分裂
  9. Android Studio的Terminal配置
  10. C实战:项目构建Make,Automake,CMake
  11. C++编程题#1:含k个3的数
  12. 洗礼灵魂,修炼python(66)--爬虫篇—BeauitifulSoup进阶之“我让你忘记那个负心汉,有我就够了”
  13. [No0000124]WPF 扩展控件Behavior的几种方式
  14. Makefile中变量定义中末尾不能有空格
  15. BIEE11G配置Oracle 12c数据源
  16. mysql水平分区
  17. c#基础学习(0806)之可变参数、ref和out关键字的简单使用
  18. MVC Linq动态排序
  19. ios 给键盘上面加上“完成”
  20. 小程序中 function (res)的理解

热门文章

  1. Linux扩展根目录
  2. 3.SELECT 语句
  3. Odometry的发布和发布odom到base_link的tf变换
  4. js 二维数组排序sort()函数
  5. javaweb dom4j解析xml文档
  6. wc.exe指令(C++)
  7. TSQL--SET ANSI_NULLS OFF
  8. 将以太坊封装为 ERC20
  9. c++基类指针指向继承类调用继承类函数
  10. React进阶篇(2) -- Redux