链接:hdu4734

Description

For a decimal number x with n digits (AnAn-1An-2 … A2A1), we define its weight as F(x) = An 2n-1 + An-1

2n-2 + … + A2 2 + A1 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 < 109)
Output

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

Then output the answer.
Sample Input
3
0 100
1 10
5 100
Sample Output
Case #1: 1
Case #2: 2
Case #3: 13
题解

模板题

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,l,n) for(register int i=l;i<n;++i)
using namespace std;
const int N=4600;
int a[10],dp[10][N];
int n;

int dfs(int pos,int limit,int sum){
    if(sum<0)return 0;
    if(pos==-1)return 1;
    if(!limit&&dp[pos][sum]!=-1)return dp[pos][sum];
    int up=limit?a[pos]:9;
    int tmp=0;
    rep(i,0,up+1){
        tmp+=dfs(pos-1,limit&&i==a[pos],sum-i*(1<<pos));
    }
    if(!limit)dp[pos][sum]=tmp;
    return tmp;
}

int solve(int x,int y){
    int cnt=0,len=0,ans=0;
    while(y){
        ans+=y%10*(1<<len);
        len++;
        y/=10;
    }
    while(x){
        a[cnt++]=x%10;
        x/=10;
    }
    return dfs(cnt-1,1,ans);
}

int main(){
    scanf("%d",&n);
    memset(dp,-1,sizeof(dp));
    rep(i,0,n){
        int A,B;
        scanf("%d%d",&A,&B);
        printf("Case #%d: %d\n",i+1,solve(B,A));
    }
    return 0;
}