不要62

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 43588    Accepted Submission(s):
16034

Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为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
80
 
Author
qianneng
 

注意::!!

统计答案按位数统计时 若n的第i位是5,那j就循环0~4 如果第一位是5同样如此,那如果n到58呢?超过五十怎么统计?

其实在统计两位数时,就把0~9统计到了,(00,01,02...09),统计一位数,相当于统计了超过50的数(0~8)。

代码在solve里面

 
 
/*
数位dp入门
f[i][j]表示一共有i位且最高位为j的符合条件个数
digit[i]表示从右往左数i个是什么数
*/
#include<iostream>
#include<cstdio>
#include<cstring> using namespace std;
int f[][],digit[],len,ans; void init()
{
memset(f,,sizeof f);
f[][]=;
for(int i=;i<=;i++)//位数
for(int j=;j<;j++)//当前位
for(int k=;k<;k++)//后一位
if(j!= && !(j==&&k==)) f[i][j]+=f[i-][k];
} int solve(int n)//统计1~n中符合条件
{
init();len=;ans=;
while(n>)
{
digit[++len]=n%;
n/=;
}digit[len+]=;
for(int i=len;i;i--)
{
for(int j=;j<digit[i];j++)//important
{
if(j!= && !(digit[i+]==&&j==))
ans+=f[i][j];
}
if(digit[i]== || (digit[i]==&&digit[i+]==)) break;//低位出现4 62高位不再考虑
}
return ans;
} int main()
{
int l,r;
while(scanf("%d%d",&l,&r))
{
if(l+r==) break;
printf("%d\n",solve(r+)-solve(l));
}
return ;
}

最新文章

  1. trim(),正则表达式中文匹配
  2. ARC和MRC混编
  3. iOS阶段学习第14天笔记(NSString与NSMutableString)
  4. 2.3 CMMI2级——项目跟踪和控制(Project Monitoring and Control)
  5. 实验一 Java开发环境的熟悉
  6. [分享]一个String工具类,也许你的项目中会用得到
  7. 关于app的清除缓存的功能
  8. 菜鸟学习Spring Web MVC之二
  9. 设计模式:单例模式(Singleton)
  10. datagridview中combobox类型的cell选中一个下拉列表之后,立即生效的事件
  11. CANBus Determining Network Baud Rate, Automatic bit-rate detection
  12. CXF客户端异常
  13. PNG 文件结构
  14. 大数据系列修炼-Scala课程04
  15. 开篇-我眼中的FPGA
  16. [随笔] 简单操作解决Google chrome颜色显示不正常的情况
  17. Jdbc、Mybatis、Hibernate各自优缺点及区别
  18. Error - The debugger&#39;s worker process (msvsmon.exe) unexpectedly exited.
  19. Eclipse Memory Analyzer
  20. 在IntelliJ IDEA中使用VIM

热门文章

  1. Spring学习_day02_AOP,AspectJ,JdbcTemplate
  2. vmware vSphere client中,选择文件-&gt;部署OVF模板,报错处理方法
  3. BZOJ 2626: JZPFAR KDtree + 堆
  4. 4.Linux的进程
  5. 小白神器 - 一篇博客学会HTML
  6. Dajngo——10 请求与响应 文件上传 GET和POST请求 类视图
  7. paste deploy初探
  8. 接水问题(2010年NOIP全国联赛普及组)
  9. BZOJ1192 鬼谷子的钱袋
  10. 洛谷 P2965 [USACO09NOV]农活比赛The Grand Farm-off