hdu2089不要62(数位dp)
2024-08-31 03:41:33
不要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连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315
73418
88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。
Output
对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。
Sample Input
1 100
0 0
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 ;
}
最新文章
- trim(),正则表达式中文匹配
- ARC和MRC混编
- iOS阶段学习第14天笔记(NSString与NSMutableString)
- 2.3 CMMI2级——项目跟踪和控制(Project Monitoring and Control)
- 实验一 Java开发环境的熟悉
- [分享]一个String工具类,也许你的项目中会用得到
- 关于app的清除缓存的功能
- 菜鸟学习Spring Web MVC之二
- 设计模式:单例模式(Singleton)
- datagridview中combobox类型的cell选中一个下拉列表之后,立即生效的事件
- CANBus Determining Network Baud Rate, Automatic bit-rate detection
- CXF客户端异常
- PNG 文件结构
- 大数据系列修炼-Scala课程04
- 开篇-我眼中的FPGA
- [随笔] 简单操作解决Google chrome颜色显示不正常的情况
- Jdbc、Mybatis、Hibernate各自优缺点及区别
- Error - The debugger&#39;s worker process (msvsmon.exe) unexpectedly exited.
- Eclipse Memory Analyzer
- 在IntelliJ IDEA中使用VIM
热门文章
- Spring学习_day02_AOP,AspectJ,JdbcTemplate
- vmware vSphere client中,选择文件->;部署OVF模板,报错处理方法
- BZOJ 2626: JZPFAR KDtree + 堆
- 4.Linux的进程
- 小白神器 - 一篇博客学会HTML
- Dajngo——10 请求与响应 文件上传 GET和POST请求 类视图
- paste deploy初探
- 接水问题(2010年NOIP全国联赛普及组)
- BZOJ1192 鬼谷子的钱袋
- 洛谷 P2965 [USACO09NOV]农活比赛The Grand Farm-off