题目传送门

题目大意

题目给了个$f(x)$

$$ f(x) = \sum_{i=1}^{n}A_n \times 2^{n-1} $$

𝐴𝑖是十进制数位，然后给出𝑎、𝑏,求区间[0,𝑏]内满足𝑓(𝑖)<=𝑓(𝑎)的𝑖的个数。其中 $0<=𝐴,𝐵<10^9$

题解

开始做这题的时候是蓝桥杯国赛前一天晚上，当时学长给了我这道题，我写了个最没脑子的数位DP，就是最普通的那种有什么就记录什么的记忆化搜索，当时开了个三维数组f[i][j][k]表示处理到第i位，j记录了数字是否达到最大值，k就是累积的f(x)的值。

乍一看很对，结果TLE，这题的数据组数太多了，正常的数位DP每进行一次就要memset一次（C++初始化数组），memset是O(n)的复杂度，直接爆炸。

学长说是可以通过巧妙的状态设计避开每次都要进行的初始化。

我：？？？？这不可能吧

首先不清空的话，偷懒写的j那一维度就不能用了，因为每次数字都不一样，记录数字是否达到最大值的那一维度不能通用。

然后就只剩f[i][k]两个维度了

之前k表示当前累积的f(x)的值，这个数字和B有关系，所以要memset，现在k表示当前累积的f(x)的值到目标f(A)的差，由于是差，所以和B没有关系。我们开始时把k那里赋值为f(a)，每次搜索让他减去当前的f值就行了。

Code

注释是AI自动生成的，仅供参考（

import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    // 最大输入数字的位数
    static int MAXN = 15;
    // 数字数组，用于存储输入数字的各个位上的数字
    static int a[] = new int[MAXN];
    // 二维数组，用于存储子问题的结果
    static int f[][] = new int[MAXN][20000];
    // 中间计算结果
    static int fa = 0;
    /**
     * 递归函数，实现数位动态规划算法。
     *
     * @param  pos    当前数字数组的位置
     * @param  limit  标志位，表示当前数字是否达到了最大值
     * @param  sum    子问题的当前数字和
     * @return        子问题的有效组合数
     */
    static int dfs(int pos, boolean limit, int sum) {
        // 基本情况：所有数字都已处理完毕
        if (pos == 0)
            return (sum >= 0 ? 1 : 0);
        // 基本情况：数字和变为负数
        if (sum < 0)
            return 0;
        // 基本情况：子问题已经计算过
        if (!limit && f[pos][sum] != -1)
            return f[pos][sum];
        // 确定当前位置的最大数字值
        int max_num = (limit ? a[pos] : 9);
        int ans = 0;
        // 递归计算有效组合数
        for (int i = 0; i <= max_num; i++) {
            ans += dfs(pos - 1, limit && i == max_num, sum - (i << pos - 1));
        }
        // 存储子问题的结果
        if (!limit)
            f[pos][sum] = ans;
        return ans;
    }

    public static void main(String[] args) {
        // 读取测试用例的数量
        int t = sc.nextInt();
        // 初始化结果数组
        for (int i = 0; i < MAXN; i++) {
            Arrays.fill(f[i], -1);
        }
        // 处理每个测试用例
        for (int i = 1; i <= t; i++) {
            // 读取输入数字
            int a = sc.nextInt(), b = sc.nextInt();
            // 重置中间计算结果
            fa = 0;
            // 将第一个输入数字转换为整数
            int cnt = 0;
            while (a != 0) {
                fa += (a % 10) << cnt;
                a /= 10;
                cnt++;
            }
            // 打印当前测试用例的结果
            System.out.println("Case #" + i + ": " + work(b));
        }
    }
    /**
     * 函数将一个整数转换为数字数组，并计算有效组合数。
     *
     * @param  x    输入数字
     * @return      给定数字的有效组合数
     */
    static int work(int x) {
        // 将输入数字转换为数字数组
        int len = 0;
        while (x != 0) {
            a[++len] = x % 10;
            x /= 10;
        }
        return dfs(len, true, fa); // 使用数位动态规划计算有效组合数
    }
}

end