不要62

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

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
 
Source
 
Recommend
lcy
原理。
所以i = 4的时候, 是衔接  0~5  和 (0~999  就是预处理dp[3][?][?]里)
所以i = 3的时候, 是衔接  0~1  和 (0~99  就是预处理dp[2][?][?]里)
所以i = 2的时候, 是衔接  0~2  和 (0~9  就是预处理dp[1][?][?]里)
所以i = 1的时候, 是衔接  0~8  和 (-  就是预处理dp[0][?][?]里)
数位DP
递推形式写法理解:
假设对于一个长度为len的数来说,举个例子来说吧,这个数是78589,len=5,
从高位开始,7这一位,我们可以从0枚举到6,后面没有限制,但是如果当前为枚举到7,那么后面的位数就会有限制,怎么办呢?,、
注意到它有一个特性,就是所有数都是以7开头的,我们可以充分利用以7开头的所有数的前缀都是7这一特性,
所以我们如果去掉这一位(好像有些计数问题上,就是利用去掉某个位置上的数,或者都减去相同的数,方案数相同),
这次我们利用去掉前缀的方案数跟这些数含不吉利的数的方案数是相等的,当然了这个问题并不能直接把前缀去掉就完了,
还得考虑到前缀对当前位的影响,如果是62(加个标记,后面的数就全加上)
,或者如果前缀是6(并且这一位大于2)的情况,就不仅要加上dp[i-1][0]*a[i],还要加上dp[i][1](这样可以形成62这个不吉利数)
具体问题,具体对待嘛。
所以我们可以这样计算,(之前好像哪次的省赛,有道DP,就是只要看数字,数个数的的方式,想清楚了,问题就迎刃而解了,好像也是
计算以某个位置开头的所有的方案数,还是以某个位置结尾的所有的方案数,就可以了)。
a:算出分别以0,1,2,3,4,5,6开头的五位数的含有不吉利数(4和62)的数的个数,这个好弄。
b:算7开头的五位数的数的个数,就要算出分别以70,71,72,73,74,75,76,77开头的五位数的个数
,那么我们具体实现的时候,只要算出以0,1,2,3,4,5,6,7,开头的四位数的个数就行,因为前缀都是7。
c:算78开头的五位数的含有不吉利数的数的个数,就要算出分别以780,781,782,783,784开头的五位数的个数
,那么我们具体实现的时候,只要算出以0,1,2,3,4,开头的三位数的个数就行,因为前缀都是78。
d:算785开头的五位数的含有不吉利的数的个数,就要算出分别以7850,7851,7852,7853,7854,7855,7856,7857
开头的五位数的个数,那么我们具体实现的时候,只要算出以0,1,2,3,4,5,6,开头的2位数的个数就行,因为前缀都是785,
e:算7858开头的五位数的含有不吉利数的数的个数,就要算出分别以78580,78581,78582,78583,78584,78585,78586,78587,78588开头的
五位数的个数,那么我们具体实现的时候,只要算出以0,1,2,3,4,5,6,7,8开头的一位数的个数,因为前缀都是7858.
我们没有算78589,因为不能算以9为前缀的数的个数,len已经减到0,所以传参的时候n需要加1。
可能还会有一个疑问就是说,62,062,0062,不是重复计算可嘛,其实不是因为位数都是固定的,都是五位,所以都要补成5位,
如果62出现在低两位,那么其实算的是00062,如果算的是高两位,那么其实算的是62————,62后面会有三个不确定的数字.

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std ;
int dp[][];
//dp[len][0]代表不含4或62的个数
//dp[len][1]代表不含4或62的个数,首位为2
//dp[len][2]代表含4或62的个数
void init()
{
memset(dp,,sizeof(dp));
//dp[1][0]=9;
//dp[1][1]=1;
//dp[1][2]=1;
dp[][]=;
for(int len=;len<=;len++)
{
dp[len][]=dp[len-][]*-dp[len-][];
        //在最高位加上除了4之外的9个数字,但是可能在2之前加了6 
dp[len][]=dp[len-][];
      //就是在原先不含4或62的最高位加2 
dp[len][]=*dp[len-][]+dp[len-][]+dp[len-][];
//在已经有不吉利数字最高位加任意数字,或者在无吉利数字前加4,或者在2前面加4
}
} int solve(int x)
{
int s[],len=,xx=x;
while(x>)
{
s[++len]=x%;
x/=;
}
s[len+]=; //初始化前缀为0,0是没有任何影响的,后面一位可能会用到前面一位
// cout<<len<<endl;
int ans=,flag=;
for(int i=len;i>=;i--)
{
ans+=(s[i]*dp[i-][]);
if(flag) //如果前缀中有出现4或者62的话,那么后面的数就全加上
{
ans+=s[i]*dp[i-][];
} //只考虑以len位置为i的开头的数
if(!flag && s[i]>)
ans+=dp[i-][];
if(!flag && s[i]>)
ans+=dp[i-][];//因为是大于号,所以低一位可以完全枚举 //考虑前缀的影响
if(!flag && s[i+]== && s[i]>)
ans+=dp[i][];
if(s[i]== || (s[i+]== && s[i]==) )
{
flag=;
}
}
return xx-ans;
}
int main()
{
init() ;
int n,m ;
//
while(scanf("%d%d",&n,&m))
{
if(n== && m==)
break ;
// solve(101);
printf("%d\n",solve(m+)-solve(n)) ;//用[0,m]-[0,n)即可得到区间[n,m]
} return ;
}
dfs写法理解:

dp[len][0]代表首位不为6,剩余长度为len,不含4和62的数的个数,

dp[len][1]代表首位为6,剩余长度为len,不含4和62的数的个数。

同样是枚举每个位置上的数,但是不同的是对于枚举当当前位置最大值的处理,dfs通过fp(代表是否是n的前缀)

这个参数只是用来告诉下一个状态是枚举到9,还是枚举到自身位置的最大值,如果是上界的前缀就只能枚举当自身位置的最大值,

不是就可以从0枚举到9.还有一个参数是用来表示前缀的最后一位是否为6的状态,

不为6,ret+=dp[len-1][0],

为6,ret+=dp[len][1];

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
LL dp[][];
int digit[]; LL dfs(int len,bool state,bool fp)
{
if(!len)              //len能减到0,说明枚举的这个长度为len的数不含4和62
return ;
if(!fp && dp[len][state] != -) //如果不是前缀,并且已经被计算过
return dp[len][state];
//是前缀的话,说明dp[len][state]不能用,就得重新搜索(枚举)。
LL ret = ;int fpmax = fp ? digit[len] : ;
for(int i=;i<=fpmax;i++) //分别算出以i开头的数的方案数,
//62,062,0062,因为位数是固定的,假设是m位,那么都不足m位,后面肯定有东西
{
if(i== || state && i == )
continue;
//i如果不是6的话,ret+=dp[len][0],如果是6的话,ret+下一位就不能为2的个数
ret += dfs(len-,i == ,fp && i == fpmax);
//第二个参数来保存前缀的最后一位是否为6的状态,如果为6,下一位就不能为2,否则没有限制
//第三个参数表明是否是前缀,如果是前缀,下一位就只能枚举到最大值,否则就没有限制
}
if(!fp) //如果是前缀,当前得到的ret的值,就不能代表dp[len][state]的值
dp[len][state] = ret;
return ret; //ret代表0到n不含4和62的个数
} LL f(LL n)
{
int len = ;
while(n)
{
digit[++len] = n % ;
n /= ;
}
return dfs(len,false,true);
} int main()
{
//freopen("test.txt","r",stdin);
LL a,b;
memset(dp,-,sizeof(dp));
while(cin>>a>>b)
{
if(a== && b==)
break;
cout<<f(b)-f(a-)<<endl;
} return ;
}

比较这两种方式的异同点,递推是利用具有相同前缀的数含4或62的方案数,跟去掉前缀之后的方案数相等这一特性,

而dfs是利用记录是否为前缀这一状态,搜索时,来判断每一位枚举的范围.记忆化搜索得到答案.

dfs纯属按位枚举每一位,然后从最低位回溯进行递推。

最新文章

  1. NAT123内网映射端口
  2. jQuery中关于height,innerWidth与outerWidth的区别
  3. asp.net如何在前台利用jquery Ajax调用后台方法
  4. MFC中对话框类(Dialog)的应用
  5. 一步一步教你如何在linux下配置apache+tomcat(转)
  6. md5sum 生成 经md5加密后的字符串
  7. Telerik 控件事例(鼠标拖动行,拖动列,设置行对齐,行宽,是否显示)
  8. 账户管理命令 useradd、groupadd
  9. Delphi Keycode
  10. java中排序一个字符串数组
  11. NET 2016
  12. Delphi面向对象设计的经验原则(61条)
  13. 实验吧Web-PHP大法
  14. QTP连接MySQL
  15. python入门(2)python的安装
  16. React Native 入门基础知识总结
  17. 【CQOI2012】局部极小值
  18. HDU 4565 So Easy(矩阵解公式)
  19. 使用Robot Framework做接口测试
  20. Jquery动态添加 删除 操作实现

热门文章

  1. 【最长上升子序列记录路径(n^2)】HDU 1160 FatMouse&#39;s Speed
  2. JavaBean映射工具dozer学习
  3. BZOJ1986: [USACO2004 Dec] Dividing the Path 划区灌溉
  4. Rem 字体设置学习一
  5. IE下IFrame引用跨域站点页面时,Session失效问题解决
  6. http_load分析(转)
  7. Ubuntu 16.04安装SQLite Browser操作SQLite数据库
  8. Android消息机制1-Handler(Java层)(转)
  9. rand和srand的用法(转载)
  10. 原始的解释器模式(Interpreter Pattern)