目录
一、题目
1、题目描述
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).
2、输入格式
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)
3、输出格式
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.
4、原题链接
二、解题报告
1、思路分析
朴素数位dp:
很明显的数位dp题目,由于0 <= A,B < 1e9),故f(x)最大也就不到10000,我们定义f[N][pre],为剩余N位,高位F()值为pre时,满足F() < F(A)的数字数目
N显然不超过10,pre不超过10000,那么有1e5个状态(设为n),每个状态转移为O(logn)
整体nlognn时间复杂度,是可以接受的,但是我们直接这样写数位dp,会TLE,为什么?
样例数目T最大可以到1e4,而对于不同的A,显然f[][]也不同,所以每次都要对f[][]初始化为-1,这样时间复杂度就变为了O(t * nlogn)
这就导致了我们每组样例保存的状态很多时候不能共用,那么如何修改状态定义,使得状态可以共用,从而保证时间复杂度在O(nlogn)呢?
反向思维数位dp:
我们发现每组样例,无论A如何取,最终合法数字x都满足F(x) - F(A) >= 0,那么我们不妨就设计f[N][pre]为剩余N位,高位F - F(A) = pre时的合法数字数目,这样一来,不同组数据,无论A如何取,f[][]保存的状态都是可以公用的,这样保证了每个状态最多计算一次,时间复杂度维持在了O(nlogn)
2、复杂度
时间复杂度: O(nlogn) 空间复杂度:O(n)
3、代码详解
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
#define IOTIE ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define int long long
#define N 32
int f[N][12000], d[N], a, b, endstate = 0, t = 0;
int dfs(int n, int pre, bool lim)
{
if (!n)
return pre >= 0;
if (pre < 0)
return 0;
if (lim && ~f[n][pre])
return f[n][pre];
int ceil = lim ? 9 : d[n], res = 0, nxtstate;
for (int i = 0; i <= ceil; i++)
{
nxtstate = pre - (1 << (n - 1)) * i;
if (nxtstate >= 0)
res += dfs(n - 1, nxtstate, lim || i < ceil);
}
if (lim)
return f[n][pre] = res;
return res;
}
void solve()
{
cin >> a >> b, endstate = 0;
int i = 0;
while (a)
endstate += (a % 10) * (1 << i), i++, a /= 10;
i = 0;
while (b)
d[++i] = b % 10, b /= 10;
cout << "Case #" << ++t << ": " << dfs(i, endstate, false) << '\n';
}
signed main()
{
IOTIE
// freopen("in.txt", "r", stdin);
int _ = 1;
memset(f, -1, sizeof(f)), cin >> _;
while (_--)
solve();
return 0;
}