首页 > 代码库 > 不要62
不要62
不要62
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
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 1000 0
Sample Output
80
分析：数位dp基础题；
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, ls[rt]#define Rson mid+1, R, rs[rt]const int maxn=1e5+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline ll read(){ ll x=0;int f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int n,m,k,t,d[10],dp[10][2][2][10];bool vis[10][2][2][10];//第几位，数是否符合要求，是否满足答案，当前位是多少；int dfs(int pos,int ca,int ok,int now){ if(pos<0)return ok; if(ca&&vis[pos][ca][ok][now])return dp[pos][ca][ok][now]; if(ca) { int&ret=dp[pos][ca][ok][now]; vis[pos][ca][ok][now]=true; for(int i=0;i<=9;i++) { if(ok) { ret+=dfs(pos-1,ca,ok,i); } else { if(i==4)ret+=dfs(pos-1,ca,1,4); else if(now==6&&i==2)ret+=dfs(pos-1,ca,1,2); else ret+=dfs(pos-1,ca,ok,i); } } return ret; } else { int ret=0; for(int i=0;i<=d[pos];i++) { if(ok) { ret+=dfs(pos-1,i<d[pos],ok,i); } else { if(i==4)ret+=dfs(pos-1,i<d[pos],1,4); else if(now==6&&i==2)ret+=dfs(pos-1,i<d[pos],1,2); else ret+=dfs(pos-1,i<d[pos],ok,i); } } return ret; }}int solve(int p){ memset(dp,0,sizeof(dp)); memset(vis,false,sizeof(vis)); int num=0; while(p) { d[num++]=p%10; p/=10; } return dfs(num-1,0,0,0);}int main(){ int i,j; while(~scanf("%d%d",&n,&m)) { if(n==0&&m==0)break; printf("%d\n",m-n+1-solve(m)+solve(n-1)); } //system("Pause"); return 0;}
不要62
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。