题目描述
对于一个非负整数 $x=\overline{a_na_{n-1}…a_2a_1}$ ，设 $F(x)=a_n·2^{n-1}+a_{n-1}·2^{n-2}+…+a_2·2^1+a_1·2^0=\sum\limits_{i=1}^na_i·2^{i-1}$
多次询问 $[0,B]$ 区间内 $F$ 值小于等于 $F(A)$ 的数的个数。
输入
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)
输出
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.
样例输入
3
0 100
1 10
5 100
样例输出
Case #1: 1
Case #2: 2
Case #3: 13
题解
数位dp
考虑到最大的 $F(x)=F(999999999)=9207$ ，因此可以设 $f[i][j][k]$ 表示 $i$ 位数，最高位为 $j$ ，$F$函数的值为 $k$ 的数的个数。
首先预处理出 $f$ 数组，考虑当前位的贡献来计算。
然后先计算出$F(a)$，然后要求的就是$[0,b+1)$内 $F$值小于等于 $F(a)$ 的数的个数。
按照常规的数位dp思路，先考虑不足总位数的，然后再从高位向低位枚举，考虑以前位的贡献，得出当前的范围，直接计算即可。
由于有多组询问，需要使用前缀和优化转移过程。
这里为了不开long long把询问区间转化为 $[0,b)$ （实际上是 $[1,b)$），因此需要计算 $b$ 对答案的贡献。
#include <cstdio>
int f[10][10][10010] , b[10];
void init()
{
int i , j , k , l;
f[0][0][0] = b[0] = 1;
for(i = 1 ; i < 10 ; i ++ )
{
b[i] = b[i - 1] * 10;
for(j = 0 ; j < 10 ; j ++ )
for(k = 0 ; k < 10 ; k ++ )
for(l = j << (i - 1) ; l <= 10000 ; l ++ )
f[i][j][l] += f[i - 1][k][l - (j << (i - 1))];
}
for(i = 1 ; i < 10 ; i ++ )
for(j = 0 ; j < 10 ; j ++ )
for(k = 1 ; k <= 10000 ; k ++ )
f[i][j][k] += f[i][j][k - 1];
}
int calc(int n)
{
int t = 1 , ans = 0;
while(n) ans += n % 10 * t , n /= 10 , t <<= 1;
return ans;
}
int query(int n , int m)
{
int i , j , p , di = 1 , ans = 1 + (calc(n) <= m);
for(i = 1 ; b[i] <= n ; i ++ )
for(j = 1 ; j < 10 ; j ++ )
ans += f[i][j][m];
for( ; i ; i -- )
{
p = n / b[i - 1] % 10;
for(j = di ; j < p ; j ++ ) ans += f[i][j][m];
m -= p << (i - 1) , di = 0;
if(m < 0) break;
}
return ans;
}
int main()
{
init();
int T , i , a , b;
scanf("%d" , &T);
for(i = 1 ; i <= T ; i ++ ) scanf("%d%d" , &a , &b) , printf("Case #%d: %d\n" , i , query(b , calc(a)));
return 0;
}
