sdnu 1248.B.陆历川玩数位
1248.B.陆历川玩数位
Description
A number X have n digits(A1A2A3......An)
F(x) = A1*2n-1 + A2*2n-1 .....+An-1*21 + An *20
Now, give you two number A, B
You need to calculate how many number's F(x) is no more than F(A) between 0 to B
Input
T(0 < T<= 10000) T is TestCase
A, B (0 <= A, B <= 1000000000)
Output
Answer
Sample Input
11 1
Sample Output
Case #1: 2
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[20][10002];//最大的时候也不是太大~开个10000+的数组就好了
int maxn[20];
int num;
int f(int x)//求他的f(x)是多少
{
if (x == 0)
{
return 0;
}
int ans = f(x / 10);
return ans * 2 + (x % 10);
}
int poww(int x)求这个2的x幂是多少
{
int ans = 1;
while (x--)
{
ans = ans * 2;
}
return ans;
}
int dfs(int pos, int sum, bool limit)进行dfs遍历
{
if (pos == -1)如果f(x)>num;就不加入结果
{
return sum<=num;
}
if (sum > num)同上
{
return 0;
}
if (!limit&&dp[pos][num-sum] != -1)一定要注意边界的limit~所有的dp记忆化都要加上！limit
{
return dp[pos][num-sum];
}
int ans = 0;
int up = limit ? maxn[pos] : 9;//查询上界
for (int s = 0; s <= up; s++)
{
ans += dfs(pos - 1, (sum + poww(pos)*s), limit && (maxn[pos] == s));
}
if (!limit)
{
dp[pos][num-sum] = ans;记忆化
}
return ans;
}
int solve(int x)把边界储存下来；
{
int pos = 0;
while (x)
{
maxn[pos++] = x % 10;
x = x / 10;
}
return dfs(pos - 1, 0, 1);
}
int main()
{
memset(dp, -1, sizeof(dp));
int te;
scanf("%d", &te);
int k = 1;
while (te--)
{
int a, b;
scanf("%d %d", &a, &b);
num = f(a);
printf("Case #%d: %d\n",k++, solve(b));
}
return 0;
}
