hdu2089 不要62

2024-05-14 12:08
文章标签 不要 62 hdu2089

本文主要是介绍hdu2089 不要62,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

不要62

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


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
数位dp,试了试,记忆化搜索的方法,确实很简单啊!
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int pri[20],dp[10][3];
int get(int d,int t){if(d==2||t==4||(d==1&&t==2))return 2;if(t==6)return 1;return 0;
}
int dfs(int pos,int d,int flag){if(pos==0)return d==2;if(!flag&&dp[pos][d]!=-1)return dp[pos][d];int u=flag?pri[pos]:9,ans=0;for(int i=0;i<=u;i++)ans+=dfs(pos-1,get(d,i),flag&&(i==u));return flag?ans:dp[pos][d]=ans;
}
int solve(int x){int cnt=0;while(x){pri[++cnt]=x%10;x/=10;}return dfs(cnt,0,1);
}
int main()
{int n,m;memset(dp,-1,sizeof(dp));while(scanf("%d%d",&n,&m)!=EOF&&n+m){printf("%d\n",m-n+1-solve(m)+solve(n-1));}return 0;
}
再来个用完全dp做的,这个就麻烦多了!
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int pri[20],dp[10][3];//dp[0]不含462的个数dp[1]表示不含462的以2开头的个数,dp[2]不正确的数
int init(){dp[0][0]=1;for(int i=1;i<8;i++){dp[i][0]=dp[i-1][0]*9-dp[i-1][1];//在不含462的数,加上不为4的数9个数,减去以2开头的数加了6dp[i][1]=dp[i-1][0];//前面加上2dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];//不正确的数10个数任意加,正确的数加4,以2开头的加上6}
}
int solve(int x){int cnt=0,ans=0;while(x){pri[++cnt]=x%10;x/=10;}bool flag=false;pri[cnt+1]=0;for(int i=cnt;i;i--){ans+=dp[i-1][2]*pri[i];if(flag)ans+=dp[i-1][0]*pri[i];else {if(pri[i]>4)ans+=dp[i-1][0];if(pri[i]>6)ans+=dp[i-1][1];if(pri[i+1]==6&&pri[i]>2)ans+=dp[i][1];}if((pri[i+1]==6&&pri[i]==2)||pri[i]==4)flag=true;}return ans;
}
int main()
{int n,m;init();while(scanf("%d%d",&n,&m)!=EOF&&n+m){printf("%d\n",m-n+1-solve(m+1)+solve(n));}return 0;
}



这篇关于hdu2089 不要62的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/988706

相关文章

模具要不要建设3D打印中心

随着3D打印技术的日益成熟与广泛应用,模具企业迎来了自建3D打印中心的热潮。这一举措不仅为企业带来了前所未有的发展机遇,同时也伴随着一系列需要克服的挑战,如何看待企业引进增材制造,小编为您全面分析。 机遇篇: 加速产品创新:3D打印技术如同一把钥匙,为模具企业解锁了快速迭代产品设计的可能。企业能够迅速将创意转化为实体模型,缩短产品从设计到市场的周期,抢占市场先机。 强化定制化服务:面

大家不要退小黄车的押金了

大家好,首先我不是ofo的任何人,我只是一名小黄车的使用者,从去年开始就一直关注这ofo、摩拜的信息,最近这段时间ofo陷入了囧境,大家都担心自己的押金,全都去退还押金,这样无疑是给ofo有一层打击,因为本来资金已经很紧张了,ofo的用户也不在少数,没有资本的涌入,它也挺可怜的,它去哪里给你们退钱呢。           ofo的诞生,给我们提供了方便我们是毋庸置疑的,不光是

社交平台找旅游搭子一起旅行靠谱吗?答案是不要太爽!

哈喽小伙伴们,今天要跟大家分享一个超级棒的小程序——咕哇找搭子!作为一个热爱自由行的人,最头疼的就是找不到志同道合的小伙伴。但自从用了这个咕哇小程序后,一切都变得简单又充满乐趣啦!🎉 上个月,我计划去云南旅行,就试着在咕哇上发布了我的行程信息。没想到很快就收到了几位朋友的回应,其中一位叫小莲的朋友特别投缘。我们不仅目的地一样,就连兴趣爱好都出奇地相似,于是我们就决定一起出发啦!👭

LeetCode 62 Unique Paths

题意: 一个n*m的棋盘,每次行动只能向下或者向右走1格,求从左上角走到右下角有几种不同的方案数。 思路: 因为行动只能向下向右,所以总步数是一定的,即n - m + 2步。那么问题就变成了这里面的哪几步是向下的,就是组合数了,即从n - m + 2个中选n - 1个的组合数。 题目里说的n和m值太夸张了,因为他的函数返回int……所以肯定很小。 代码: class S

python爬虫: 抓取任意歌手的歌词,简直不要太骚

估计大家对歌词的抓取一般是通过抓取网页内容的方式来进行,今天,LZ就教大家一个简单的方法。对大家进行歌词分析来说,又多了一条捷径。 本篇文章是通过请求qq音乐的某一个文件来进行获取的,这个骚操作恐怕还没什么人发现吧,娃哈哈~ 看完过后你就会觉得,这简直不要太骚~ 二话不说, 先上代码: #!/usr/bin/python# -*- coding:utf-8 -*-import reque

不要替换运行中JVM的相关jar包

文章目录 具体场景具体原因探索总结 在java程序运行时,如果替换classpath下的某个jar包文件,可能会导致程序出现ClassNotFoundException**。 具体场景 我们要升级线上服务时,可能经常只需要替换其中一两个jar包即可完成升级。有时我们为了方便,经常会先替换完jar包再进行重启。其实这样的做法会有一个隐患,如果在你重启之前程序需要从这个jar包

连载:面向对象葵花宝典:思想、技巧与实践(6) - 不要说你懂“类”

方以类聚,物以群分——《周易 易传》。  类是面向对象领域里最基础的一个概念,也是面向对象分析和设计的基石。  然而,如此重要的一个概念,竟然很难找到深入的说明,绝大部分介绍面向对象的书籍或者资料基本上都是这么解释的:“类是一组对象的抽象”,这个解释看起来清晰明了,但实际上犯了一个逻辑上的错误:以未明确的概念来解释待明确的概念,什么是对象,什么是抽象,我们都还不知道,你却用这个概

春节如何带奶娃自驾游?不要忘了儿童安全座椅

春节放假,除了合家团圆,有些平常难得有假的人免不了想出门旅游一趟。而现在,最流行的就是自驾游,特别是对那些带了小孩的年轻爸妈而言,带着大包小包一堆东西和一个嗷嗷待哺的娃去挤客车、火车,怎么想怎么觉得不方便。可是,小朋友毕竟不同于大人,要带他们出门,需要注意什么呢?   我有一次带婴儿(当时11个月)长时间(16天)去云南旅行的经历,而且这个春节还会带孩子(20个月)去海南耍15~16天。所

js 判断是否等于0不要用!

var a = $('#a').val(); // a等于0// 不要用!a,这个可能等于false,因为a可能被认为是字符串if(!a){}// 可以用if(a == 0){}

代码随想录算法训练营第三十四天| 62.不同路径 63. 不同路径 II

62.不同路径 题目: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 示例 1: 输入:m = 3, n = 7输出:28 示例 2: 输入:m = 3, n = 2输出:3解释:从左上