D - F(x)-白红宇

D - F(x)

阅读量：4445 次

发布时间：2019-06-07

本文共 2187 字，大约阅读时间需要 7 分钟。

For a decimal number x with n digits (A nA n-1A n-2 ... A 2A 1), we define its weight as F(x) = A n * 2 n-1 + A n-1 * 2 n-2 + ... + A 2 * 2 + A 1 * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).

Input

The first line has a number T (T <= 10000) , indicating the number of test cases.

For each test case, there are two numbers A and B (0 <= A,B < 10 9)

Output

For every case,you should output "Case #t: " at first, without quotes. The t is the case number starting from 1. Then output the answer.

Sample Input

0 100

1 10

5 100

Sample Output

Case #1: 1

Case #2: 2

Case #3: 13

计算满足fa的个数，数位dp,终于搞懂怎么做数位dp，自己写出来了

#include
    
     #include
     
      #include
      
       #include 
       
        #include
        
         #include
         
           #include
          
           #include
           
            #define sf scanf#define pf printf#define sca(x) scanf("%d",&x)#define mm(x,b) memset((x),(b),sizeof(x))#include
            
             #include
             
              #include
              #define rep(i,a,n) for (int i=a;i
               
                =n;i--)typedef long long ll;const ll mod=1e9+7;const double eps=1e-8;using namespace std;const double pi=acos(-1.0);const int inf=0xfffffff;const int N=1000005;int p[25];int tt[15][11];int dp[11][4605];void first(){ p[1]=1; rep(i,2,22) p[i]=p[i-1]*2; rep(i,1,11) rep(j,0,10) tt[i][j]=j*p[i]; mm(dp,-1);}int calc(int x){ int ans=0,pos=1; while(x) { ans+=(x%10)*p[pos++]; x/=10; } return ans;}int num1[15],num2[15];int dfs(int pos,int left,bool lead,bool limit)//left是剩下的，lead这里没有用，可舍去，limit是否上限{ if(!pos) return 1; int ans=0; if(!limit&&dp[pos][left]!=-1) return dp[pos][left]; int up=limit?num2[pos]:9; rep(i,0,up+1) { if(tt[pos][i]>left) break; ans+=dfs(pos-1,left-tt[pos][i],lead&&i==num1[pos],limit&&(i==num2[pos])); } if(!limit) dp[pos][left]=ans; return ans;}int solve(int l,int r){ int x=l; mm(num1,0); int pos1=0; while(l) { num1[++pos1]=l%10; l/=10; } int pos=0; while(r) { num2[++pos]=r%10; r/=10; } return dfs(pos,calc(x),true,true);}int main(){ int re,l,r,cas=1; first(); sf("%d",&re); while(re--) { sf("%d%d",&l,&r); pf("Case #%d: %d\n",cas++,solve(l,r)); } return 0;}

转载于:https://www.cnblogs.com/wzl19981116/p/9478320.html

你可能感兴趣的文章