不要 62 http://acm.hdu.edu.cn/showproblem.php?pid=2089
- Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
- Total Submission(s): 62279 Accepted Submission(s): 24682
- 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
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- using namespace std;
- int dp[10][3];//dp[i][j],i 表示个十百千万的位数, j 代表三种情况
- //dp[i][0]表示存的是 0 到 i 位数字中的幸运数
- //dp[i][1]表示存的是 0 到 i 位数字中数组以 2 开头的幸运数
- //dp[i][2]表示的是 0 到 i 位数字中的非幸运数, 即包含 4 或者 62 的数字
- void init()
- {
- memset(dp,0,sizeof(dp));
- dp[0][0]=1;
- for(int i=1;i<=8;i++)
- {
- dp[i][0]=dp[i-1][0]*9-dp[i-1][1];// 在不含不吉利数 62 和 4 的首位分别补除了 4 的 9 个数字, 减去在 2 前面补 6 的个数
- dp[i][1]=dp[i-1][0];// 在不含不吉利数在首位补 2
- dp[i][2]=dp[i-1][2]*10/* 不幸运数前面补任何数 */+dp[i-1][0]/* 幸运数前面补 4*/+dp[i-1][1]/* 在数组数位是 2 后面补 6*/;
- }
- }
- int solve(int x)
- {
- int digit[20];
- int cnt=0,temp=x;
- while(temp)
- {
- digit[++cnt]=temp%10;
- temp=temp/10;
- }
- digit[cnt+1]=0;// 前导零
- int flag=0,ans=0;//flag 标记是否出现满足条件的不幸运数字
- for(int i=cnt;i>0;i--)// 从高位开始处理
- {
- ans=ans+digit[i]*dp[i-1][2];// 在不吉利数字前面补 0~digit[i]的任意数字都是不吉利的
- if(flag==1)//digit[i]之前出现不吉利数字
- ans=ans+digit[i]*dp[i-1][0];// 补上 0~digit[i]都为不吉利
- else
- {
- if(digit[i]>4)// 出现 4
- ans=ans+dp[i-1][0];
- if(digit[i]>6)// 出现 6
- ans=ans+dp[i-1][1];
- if(digit[i+1]==6&&digit[i]>2)// 出现 62
- ans=ans+dp[i][1];
- }
- if(digit[i]==4||(digit[i+1]==6&&digit[i]==2))
- flag=1;
- }
- return x-ans;
- }
- int main()
- {
- int l,r;
- init();
- while(~scanf("%d%d",&l,&r))
- {
- if(l==0&&r==0)
- break;
- printf("%d\n",solve(r+1)-solve(l));
- }
- return 0;
- }
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int a, b, shu[20], dp[20][2];//i 是处理的这个数的数位, j 是逻辑变量 (这个数位上的这个数是否是 4),dp[i][j] 是最高位为 i 的范围内, 含 4 或不含 4 的个数
- int dfs(int len, bool if4, bool shangxian)
- {
- if (len == 0)
- return 1;
- if (!shangxian && dp[len][if4]) // 为什么要返回呢? 可以画图理解当我们搜到 3XXX 时, 程序运行到 1XXX 时就已经把 3XXX 之后的搜索完了, 记忆化也是这个用意.
- return dp[len][if4];
- int cnt = 0, maxx = (shangxian ? shu[len] : 9);
- for (int i = 0; i <= maxx; i++)
- {
- if (if4 && i == 9)
- continue;
- cnt += dfs(len - 1, i == 4, shangxian && i == maxx); // 只有之前有限制现在的达到了上限才能构成限制
- }
- return shangxian ? cnt : dp[len][if4] = cnt; // 如果有限制, 那么就不能记忆化, 否则记忆的是个错误的数.
- }
- int solve(int x)
- {
- memset(shu, 0, sizeof(shu));
- int k = 0;
- while (x)
- {
- shu[++k] = x % 10; // 保存 a,b 的数
- x /= 10;
- }
- return dfs(k, false, true);
- }
- int main()
- {
- scanf("%d%d", &a, &b);
- printf("%d\n", solve(b) - solve(a - 1));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2968825.html