不要62
发布日期:2021-07-14 01:03:49 浏览次数:72 分类:技术文章

本文共 1424 字,大约阅读时间需要 4 分钟。

描述

杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。

杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。

输入

输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。

输出

对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。

样例

  • Input
    1 100
    0 0
  • Output
    80

题解

  • 数位dp,dp[len][0]和dp[len][1]表示长为len,最高位不为6和为6的数以下(包括自身)有多少不是不吉利数,

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
#include
#define LL long long #define INIT(a,b) memset(a,b,sizeof(a)) const int MAX=0x7fffffff; const int MIN=-MAX; const int INF=0x3f3f3f3f; using namespace std; int n,m; int num[10],dp[10][2]; int dfs(int len,bool if6,bool limit){ //当前长度为len,上一位是否为6,这一位是否有最大限制 if(!len)return 1; if(!limit && dp[len][if6]) return dp[len][if6]; int up=limit?num[len]:9; int ans=0; for(int i=0;i<=up;i++){
if((if6&&i==2)||i==4) continue; ans+=dfs(len-1,i==6,limit&&i==up); //当上一位是达到上限且这一位也达到上限时下一位才有比9小的上限 } return limit?ans:dp[len][if6]=ans; //这一位达到上限的话就不能记忆,因为记录的只有最高位是6和不是6(9)的答案 } int solve(int n){
int k=0; while(n){
num[++k]=n%10; n/=10; } return dfs(k,false,true); //第一位当然是有上限的 } int main(){
while(~scanf("%d %d",&n,&m)&&(n||m)){
INIT(num,0);INIT(dp,0); printf("%d\n",solve(m)-solve(n-1)); } return 0; }

转载地址:https://blog.csdn.net/cpongo3/article/details/89334338 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Minimum Inversion Number(逆序数)
下一篇:乘法逆元的具体求法

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月08日 12时26分09秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

c 语言登录系统源代码,c语言源代码---------------个人图书管理系统 2019-04-21
android线程通信方式,Android 主线程和子线程通信问题 2019-04-21
cps1 cps2 android,图文教程:CPS1和CPS2模拟器使用 2019-04-21
在线设计 html5 表单,html5注册表单制作-表单制作-小程序表单制作 2019-04-21
android小闹钟课程设计,《小闹钟》教学设计 2019-04-21
mysql文件系统_MySQL文件系统先睹为快(1) 2019-04-21
nums在python_程序找到一对(i,j),其中nums [i] + nums [j] +(i -j)在Python中最大化?... 2019-04-21
jquery后台内容管理_教育平台项目后台管理系统:课程内容模块 2019-04-21
grouping函数 mysql_sql聚合函数有哪些 2019-04-21
python os.walk如何不遍历隐藏文件_python 获取文件下所有文件或目录os.walk()的实例... 2019-04-21
python 股票估值_【中金固收·固收+】隐藏价值的角落:限售股AAP估值及Python实现方法(上)... 2019-04-21
java文档生成_Java文档自动生成 2019-04-21
java 共享目录_java 操作windows 共享目录方法介绍 2019-04-21
java 监控 宕机_JAVA监测tomcat是否宕机,控制重启 2019-04-21
catch that cow java_POJ3278——Catch That Cow 2019-04-21
java integer 不变模式_Java代码的变与不变 2019-04-21
java guava 使用_Java8-Guava实战示例 2019-04-21
python barrier option pricing_《Python金融数据分析》书内代码实战与讲解(二)金融衍生物定价... 2019-04-21
java自带工具_深入了解Java JDK自带工具,包括javac、jar、jstack等,实用~ 2019-04-21
gnome mysql client_解决MySQLWorkbenchgnome-keyring-daemon错误的方法分享 2019-04-21