不要62

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 56193 Accepted Submission(s): 21755

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

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #define debug() puts("++++")#define gcd(a,b) __gcd(a,b)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define fi first#define se second#define pb push_back#define sqr(x) ((x)*(x))#define ms(a,b) memset(a,b,sizeof(a))#define sz size()#define be begin()#define pu push_up#define pd push_down#define cl clear()#define lowbit(x) -x&x#define all 1,n,1#define rep(i,x,n) for(int i=(x); i<=(n); i++)using namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair
                       
                         P;const int INF = 0x3f3f3f3f;const LL LNF = 1e18;const int maxm = 1e6 + 10;const double PI = acos(-1.0);const double eps = 1e-8;const int dx[] = {-1,1,0,0,1,1,-1,-1};const int dy[] = { 0,0,1,-1,1,-1,1,-1};int dir[4][2] = { { 0,1},{ 0,-1},{-1,0},{ 1,0}};const int mon[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int mod = 10056;#define inf 0x3f3f3f3f#define ll long longconst int maxn = 150;int dp[20][12];int a[20];int dfs(int pos,int pre,int sta,bool limit){ if(pos==-1) return 1; if(!limit && dp[pos][sta]!=-1) return dp[pos][sta]; int up=limit?a[pos]:9; int cnt=0; for(int i=0;i<=up;i++) { if(pre==6 && i==2) continue; if(i==4) continue; cnt += dfs(pos-1,i,i==6,limit&&i==a[pos]); } if(!limit) dp[pos][sta]=cnt; return cnt;}int solve(int x){ int pos=0; //记录有多少个数位 while(x) { a[pos++]=x%10; x/=10; } return dfs(pos-1,-1,0,true); //从最高位开始枚举，pre位是-1，sta是0，limit是true //dfs(int pos,int pre,int sta,bool limit)}int main(){ int t; int n,m; while(~scanf("%d%d",&n,&m),n+m) { ms(dp,-1); printf("%d\n",solve(m)-solve(n-1)); }}/*【题意】数位上不能有4也不能有连续的62.给定区间共有多少合法的数。【类型】数位DP入门【分析】没有4的话在枚举的时候判断一下，不枚举4就可以保证状态合法了所以这个约束没有记忆化的必要，而对于62的话涉及到两位，当前一位是6或者不是6这两种不同情况我计数是不相同的，所以要用状态来记录不同的方案数。dp[pos][sta]表示当前第pos位，前一位是否是6的状态，这里sta只需要去0和1两种状态就可以了，不是6的情况可视为同种，不会影响计数。【时间复杂度&&优化】【trick】【数据】*/

转载于:https://www.cnblogs.com/Roni-i/p/9426049.html

你可能感兴趣的文章