HDU-4734 F(x)

Posted on | In

题目链接

F(x)
Time Limit: 1000/500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8723 Accepted Submission(s): 3440

Problem Description

For a decimal number x with n digits ($A^{n}A^{n-1}A^{n-2} … A^{2}A^{1}$), we define its weight as $F(x) = A_n * 2^{n-1} + A_{n-1} * 2^{n-2}+…+ A_2 * 2 + A_1 * 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 < 10^9$)

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

题意：

求$\sum_{ i = 0 }^{ B } [F(i) <= F(A)]$

Solution:

一开始我的做法是基于$dp[u][prefix]$的数位dp， 第一维表示当前数位， 第二维表示前部的级数和， 但是数据组数太多，会TLE。
于是考虑将第二维倒过来，变为$dp[u][F(A) - prefix]$， 这样就可以复用前面数据计算过的dp数组， 于是$O(Accepted)$

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

typedef long long ll;

int n, a, b;
int v[12];
int dp[12][9300];

int dfs(int u, bool limits, int pre) {
    if (pre < 0) return 0;
    if (u == -1) return 1;
    if (!limits && dp[u][pre] != -1) {
        return dp[u][pre];
    }
    int res = 0, top = limits ? v[u] : 9;
    for (int i = 0; i <= top; i++) {
        res += dfs(u - 1, limits && (i == top), pre - i * (1 << u));
    }
    if (!limits) dp[u][pre] = res;
    return res;
}

int calc() {
    if (b == 0) return 1;
    for (n = 0; b > 0; b /= 10) {
        v[n++] = b % 10;
    }
    int sum = 0, mul = 1;
    while (a > 0) {
        sum += (a % 10) * mul;
        mul <<= 1;
        a /= 10;
    }
    return dfs(n - 1, true, sum);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    memset(dp, -1, sizeof dp);

    int T, Case = 0; cin >> T;
    while (T--) {
        cin >> a >> b;
        cout << "Case #" << ++Case << ": " << calc() << endl;
    }
}