题意:

将一个十进制数

n = dn dn-1 ... d0

视为二进制. 即

F(n) = dn*2^n + ... + d0*2^0.

给出A, B. 求0 ... B之间, 该值不大于F(A)的数的个数.

思路:

数位DP.

数位DP的优点在于, 你不需要直到这个答案是怎么来的, 只需要知道递推式. 这个答案的生成过程就在递推的过程中.

dp [ i ] [ j ] 表示 i 位的数{ x } 中 F ( x ) 小于 j 的数的个数.

 

#include
    
     #include
     
      #define maxn 16int dp[maxn][111111];int d[maxn];int n;long long tt;long long  dfs(int len ,int pre ,bool fp){    if(pre<0)return 0;//说明上一层枚举的数超过了上限,没有可用的情况    if(!len)return 1;//说明上一层是个位.那么只需要把各个数累加起来就可以    if(!fp&&dp[len][pre]!=-1)return dp[len][pre];//记忆化搜索    int fpmax=fp?d[len]:9;//取该位取值的最大值    int ret=0;    for(int i=0;i<=fpmax;i++){//从最大长度向下,每一个长度的所有取值都要遍历到,        //一旦该位的取值不是紧贴最大值,fp就false.        ret+= dfs(len-1,pre-i*(1<<(len-1)),fp&&i==fpmax);    }    if(!fp)dp[len][pre]=ret;//记录结果    return ret;}long long  calc(long long a){    int len=0;    memset(d,0,sizeof(d));    while(a){        d[++len]=a%10;        a/=10;    }    return dfs(len,tt,true);}int get(int x){    int tmp=1;    int ans=0;    while(x){        ans+=(x%10)*tmp;        x/=10;        tmp<<=1;    }    return ans;}int main(){    long long  a,b;    int nc;    scanf("%d",&nc);    int d=1;    memset(dp,-1,sizeof(dp));    while(nc--){        scanf("%I64d%I64d",&a,&b);        tt=get(a);        printf("Case #%d: %I64d\n",d++,calc(b));    }    return 0;}