H - 邱老师选妹子

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

Submit Status

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

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

于是他决定从追他的众多妹子里挑选一个出来。于是酱神给邱老师出来一个主意，已知有一些妹子，恰好可以给她们从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[][];//j表示是否以6为后缀 dp[i][j]表示长度为i,后缀情况为j时 10^(i+1)以内所有满足条件的数

int vis[][];

int dig[];

int dfs(int len,int sta,bool flag)

{

  if(len==)return ;

  if(!flag&&vis[len][sta])return dp[len][sta];

  int ans=,up=flag?dig[len]:;

  for(int i=;i<=up;i++)

  {

    if(i==||(sta&&i==) )//当前位为4或上一位为6这一位为2都应该忽略

      continue;

    ans+=dfs(len-,i==?:,flag&&i==up);

  }

  if(!flag)

    vis[len][sta]=,dp[len][sta]=ans;

  return ans;

}

int Get(int n)

{

  int len = ;

  while(n)

  {

    dig[++len]=n%;

    n/=;

  }

  return dfs(len,,true);

}

int main()

{

    int l,r;

    while(scanf("%d%d",&l,&r)==)

    {

      if(l==&&r==)break;

        printf("%d\n",Get(r)-Get(l-));

    }

    return ;

}

巴特西

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

H - 邱老师选妹子

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

Input

Output

最新文章

热门文章