不要 62
- Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
- Total Submission(s): 54005 Accepted Submission(s): 20682
- Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为 62(音: laoer).
杭州交通管理局经常会扩充一些的士车牌照, 新近出来一个好消息, 以后上牌照, 不再含有不吉利的数字了, 这样一来, 就可以消除个别的士司机和乘客的心理障碍, 更安全地服务大众.
不吉利的数字为所有含有 4 或 62 的号码. 例如:
62315 73418 88914
都属于不吉利号码. 但是, 61152 虽然含有 6 和 2, 但不是 62 连号, 所以不属于不吉利数字之列.
你的任务是, 对于每次给出的一个牌照区间号, 推断出交管局今次又要实际上给多少辆新的士车上牌照了.
Input
输入的都是整数对 n,m(0<nm<1000000), 如果遇到都是 0 的整数对, 则输入结束.
Output
对于每个整数对, 输出一个不含有不吉利数字的统计个数, 该数值占一行位置.
- Sample Input
- 1 100 0 0
- Sample Output
- 80
- Solution:
话说讲了两星期的数位 $DP$ 了, 入坑已久, 一直没去填坑 (~妄想着打表出奇迹~).
今天高三二模, 学长学姐高考前最后一次模考了, 虽然有点喊口号, 但我还是想说 "高三加油! 麓山必胜!". 然后心血来潮, 早上 $6:30$ 跑到机房刚数据结构 (然而没刚出), 忽觉有坑没填, 于是打了打数位板子题.
数位 $DP$, 其实并不难 (思路好简单啊), 我们只是换个姿态在打暴力, 但套上了记忆化使其大大优化而已.
普通的模拟水分, 一般就是在一段范围内枚举每个数, 将其每位拆开, 然后判断是否符合条件, 计数就 $OK$ 了 (但是这样显然没啥规律可循, 状态无法确定, 难以记忆化).
于是我们换个方式, 首先可以利用差分的思想, 区间 $[l,r]$ 中满足条件的数的个数 $=$ 区间 $[0,r]$ 满足条件的个数 $-$ 区间 $[0,l-1]$ 中满足条件的个数 (这很显然). 然后我们考虑从高位往低位枚举 $0-9$ 判断是否可行, 当数位到了 $0$ 位时说明可行, 那么对于 $[0,n]$ 这个区间, 每一位都会有个限制 $limit$(不能完全枚举 $0-9$ 中的每一个数). 举个栗子:$n=345$, 枚举百位时显然只能从 $0-3$ 中选, 然后当百位为 $3$ 时枚举十位就只能从 $0-4$ 中选 (百位为 $0,1,2$ 时, 十位就可以从 $0-9$ 枚举啦).
粗略的讲下思路, 我们定义状态 $f[i][j],i\in[0,8],j=0/1$, 表示到了第 $i$ 位, 前一位为 $j$ 的方案数 ($j=0$ 表示前一位不为 $6$,$j=1$ 表示前一位不为 $6$, 状态视题目而定, 尽量保证正确性下简化!), 那么对于所有不受限制的情况都记录状态, 事实证明优化贼快~.
代码:
- #include<bits/stdc++.h>
- #define il inline
- #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
- using namespace std;
- int f[20][3],cnt,n,m,ans,p[20];
- il int dfs(int pos,int lst,int sta,int limit){
- if(!pos)return 1;
- if(!limit&&f[pos][sta]!=-1)return f[pos][sta];
- int up=limit?p[pos]:9,tmp=0;
- For(i,0,up)
- if((lst==6&&i==2)||i==4)continue;
- else tmp+=dfs(pos-1,i,i==6,limit&&i==p[pos]);
- if(!limit)f[pos][sta]=tmp;
- return tmp;
- }
- il int solve(int x){
- cnt=0;
- while(x){
- p[++cnt]=x%10;
- x=x/10;
- }
- return dfs(cnt,-1,0,1);
- }
- il int gi(){
- int a=0;char x=getchar();
- while(x<'0'||x>'9')x=getchar();
- while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar();
- return a;
- }
- int main(){
- while(1){
- n=gi(),m=gi();
- if(!n&&!m)return 0;
- memset(f,-1,sizeof(f));
- printf("%d\n",solve(m)-solve(n-1));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2617792.html