Problem 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 1. Then output the answer.
Sample Input 3 0 100 1 10 5 100
Sample Output Case #1: 1 Case #2: 2 Case #3: 13
大致题意：就是问你0到b的范围中不大于F（a）的值的个数
思路：简单数位dp， dp[i][j]表示第i位不大于j的个数。
代码如下
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<map> using namespace std; int dp[20][200000]; int bit[20]; int a,b; int dfs(int pos,int num,bool flag) { if(pos==-1) return num>=0; if(num<0) return 0; if(!flag&&dp[pos][num]!=-1) return dp[pos][num]; int ans=0; int end=flag?bit[pos]:9; for(int i=0;i<=end;i++) { ans+=dfs(pos-1,num-i*(1<<pos),flag&&i==end); } if(!flag) dp[pos][num]=ans; return ans; } int F(int x) { int ret=0; int len=0; while(x) { ret+=(x%10)*(1<<len); len++; x/=10; } return ret; } int calc() { int len=0; while(b) { bit[len++]=b%10; b/=10; } return dfs(len-1,F(a),1); } int main() { int T; int Icase=0; cin>>T; memset(dp,-1,sizeof(dp)); while(T--) { Icase++; cin>>a>>b; printf("Case #%d: %d\n",Icase,calc()); } return 0; }