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. Thet is the case number starting from 1. Then output the answer.
Sample Input
30 1001 105 100
Sample Output
Case #1: 1Case #2: 2Case #3: 13
参考博客：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<stack>#include<vector>#include<set>#include<map>#define L(x) (x<<1)#define R(x) (x<<1|1)#define MID(x,y) ((x+y)>>1)#define eps 1e-8typedef __int64 ll;#define fre(i,a,b) for(i = a; i <b; i++)#define free(i,b,a) for(i = b; i >= a;i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define ssf(n)scanf("%s", n)#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define bugpf("Hi\n")using namespace std;#define INF 0x3f3f3f3f#define N 200000int dp[20][N];int a[30],k;int F(int x){k=0;int temp=0;while(x){temp+=(x%10)*(1<<k);k++;x/=10;}return temp;}void hello(int x){k=0;while(x){a[k++]=x%10;x/=10;}}int dfs(int pos,int va,int flag) //dp[i][j] 表示第i位小于等于va有多少种情况{//flag记录是不是第i位是不是可以从0~9if(pos==-1) return va>=0; if(va<0) return 0;if(!flag&&dp[pos][va]!=-1)return dp[pos][va];int ri=flag ? a[pos]:9;int i;int temp=0;fre(i,0,ri+1){temp+=dfs(pos-1,va-i*(1<<pos),flag&&(i==ri));}if(!flag) dp[pos][va]=temp;return temp;}int main(){int i,t,j,le,ri,ca=0;sf(t);mem(dp,-1);while(t–){sff(le,ri);le=F(le);hello(ri);pf("Case #%d: ",++ca);pf("%d\n",dfs(k-1,le,1));}return 0;}
，只要有信心，人永远不会挫败
