首页 > 其他 > 详细

[uestc oj]H - 邱老师选妹子

时间:2015-05-23 06:24:10      阅读:669      评论:0      收藏:0      [点我收藏+]

H - 邱老师选妹子

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
 

邱老师长得帅这是人尽皆知,于是追他的妹子就会很多。

但是你知道,邱老师是一个很专一的人,所以他心里面只能有一个人。

于是他决定从追他的众多妹子里挑选一个出来。于是酱神给邱老师出来一个主意,已知有一些妹子,恰好可以给她们从l到r排号,使得每一个妹子有单独的数字,而正好有r-l+1个妹子。

酱神说,我们不能要运气不好的女孩,而酱神又给了两个数字62和4,如果妹子的排号里面有62(必须是连续的)或4,那么就排除他现在给你l和r,问有多少妹子可以有幸在第一轮留下。

Input

输入的都是整数对l、r(0<l≤r<1000000),如果遇到都是0的整数对,则输入结束。

Output

 每组数据输出占一行,对于每个l和r 输出有多少个妹子可以在第一轮不被排除

数位dp,会影响当前位决策的是前一位是不是6,于是用sta记录,然后当前位的选择会影响后面数位选择的上界,于是立一个flag。

#include <stdio.h>

int dp[8][2];//j表示是否以6为后缀 dp[i][j]表示长度为i,后缀情况为j时 10^(i+1)以内所有满足条件的数
int vis[8][2];
int dig[8];

int dfs(int len,bool sta,bool flag)
{
if(len==0)return 1;
if(!flag&&vis[len][sta])return dp[len][sta];
int ans=0,up=flag?dig[len]:9;
for(int i=0;i<=up;i++)
{
if(i==4||(sta&&i==2) )//当前位为4或上一位为6这一位为2都应该忽略
continue;
ans+=dfs(len-1,i==6,flag&&i==up);
}
if(!flag)
vis[len][sta]=1,dp[len][sta]=ans;
return ans;
}

int Get(int n)
{
int len = 0;
while(n)
{
dig[++len]=n%10;
n/=10;
}
return dfs(len,0,true);
}

int main()
{
int l,r;
while(scanf("%d%d",&l,&r)==2)
{
if(l==0&&r==0)break;
printf("%d\n",Get(r)-Get(l-1));
}
return 0;
}

[uestc oj]H - 邱老师选妹子

原文:http://www.cnblogs.com/jerryRey/p/4523611.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!