(数位dp) 算法竞赛入门到进阶 书本题集

前言

本文中的题目来自罗勇军老师和郭卫斌老师的《算法竞赛入门到进阶》 俗称小黑书

有人在vjudge中整理了所有的题目题：《算法竞赛入门到进阶》 题目汇总 - Virtual Judge (csgrandeur.cn)

罗老师的博客：罗勇军_CSDN博客

---

数位dp从题面上来看就是非常有特色的一类题

• 数据范围非常大(不能暴力)
• 和每个数位有关
• 有明显的数学风味
• 喜欢问范围[L, R]中有多少(不)符合的数
• 一般问的比较直白不会出阅读理解型的题

数位dp一般有两种实现方式，递推和记忆化dfs

递推比较重视推到能力，而记忆化dfs也非常好写且模板话程度高。且处理更加复杂的问题时代码量远少于递推，因此更受大家喜爱。

题目

不要62

Problem - 2089 (hdu.edu.cn)

题目描述

统计不存在62和4的数

思路讲解

非常经典的数位dp，问的非常直白

本题用递推和记忆化dfs两种方式实现讲解

定义dp

1. 数位
2. 可以填写的数字

dp[][]当前第i个数位，填写数字j的合格的数量

Code

递推分组累计

递推法就两步

1. 打表 低位贡献给高位
2. 累计 高位决定低位

打表

1. 第一个循环 枚举数位
2. 第二个循环 枚举当前位 (高位)
3. 第三个循环 枚举前一位 (低位)

如果合格，则低位贡献给高位，注意不同题目初始化递推条件不一样

累计

1. 累计长度相等的数值
2. 累计所有长度第的数值

如当前n=12345是个五位数

则①表示累计也是长度为5的数，②表示累计所有长度不足5的数

在长度5的时候，后面的枚举位可以为0；而不足5的时候不能累计有前导0的情况，不然会重复累计

/**
 * https://acm.hdu.edu.cn/showproblem.php?pid=2089
 * 不要62
 * 数位dp
 * 经典数位dp
 */
#include 
using namespace std;

const int M = 1 + 10;
int dp[M][10];

// !!! 注意调用的时候hig和low的前后关系 !!!
// 打表的时候是高位看低位
// 累计的时候是低位看高位
inline bool check(int hig, int low) {
    bool flag = (hig == 6 && low == 2) || hig == 4 || low == 4;
    return !flag;
}

int __init = []() {
    // 1位数视为合法
    for (int i = 0; i <= 9; i += 1) {
        dp[1][i] = 1;
    }
    dp[1][4] = 0;
    // 从两位数开始dp
    for (int bit = 2; bit < M; bit += 1) {
        for (int hig = 0; hig <= 9; hig += 1) {
            for (int low = 0; low <= 9; low += 1) {
                // 合格则累计低一位的状态
                if (check(hig, low)) {
                    dp[bit][hig] += dp[bit - 1][low];
                }
            }
        }
    }
    return 0;
}();

int get62(int n) {
    // 逆序拆分
    vector<int> eachBit;
    while (n) {
        eachBit.push_back(n % 10);
        n /= 10;
    }

    // 考虑位数相等长度的数
    // 这里正对的是原数n
    int sameLen = 0;
    int hig = -2;
    for (int i = eachBit.size() - 1; i >= 0; i += -1) {
        int bit = i + 1;
        int low = eachBit[i];
        // 最高位从1开始，不能是前导零
        // 其余可以从0开始
        for (int j = (bit == eachBit.size() ? 1 : 0); j < low; j += 1) {
            if (check(hig, j)) {
                sameLen += dp[bit][j];
            }
        }
		// 不合格提前截断
        if (!check(hig, low)) {
            break;
        }
        hig = low;
        // 走到最后，表示这个数本身也合格
        if (i == 0) {
            sameLen += 1;
        }
    }

    // 累计低位
    int lowLen = 0;
    for (int bit = 1; bit < eachBit.size(); bit += 1) {
        // 注意这里的数位是[1, 9]没有0
        // 否则会出现重复累计的状态
        for (int i = 1; i <= 9; i += 1) {
            lowLen += dp[bit][i];
        }
    }
    return sameLen + lowLen;
}

int main() {
    int right, left;
    while (cin >> left >> right) {
        if (right == 0 && left == 0) {
            break;
        }
        cout << get62(right) - get62(left - 1) << endl;
    }

    return 0;
}

递推合并累计

那么可不可以将长度相同和长度较低的放在一步中累计呢？其实是可以的

注意下方代码的累计部分，一律从0开始累计，这样可以把长度相等情况全部算入(含前导0的相等)

我们注意到在打表时候，当前位填0可是累计前面所有的状态的，因为前面的数都是位数小于n的，所有都应该有贡献只。

注意这里说的是小于，而不是小于等于。且在第二重循环中是不能到达目标数位的。

因此这里的累计是< n的数

所有在调用时需要fun(n + 1)

/**
 * https://acm.hdu.edu.cn/showproblem.php?pid=2089
 * 不要62
 * 数位dp
 * 合并累计
 */
#include 
using namespace std;

const int M = 1 + 10;
int dp[M][10];

// !!! 注意调用的时候hig和low的前后关系 !!!
// 打表的时候是高位看低位
// 累计的时候是低位看高位
inline bool check(int hig, int low) {
    bool flag = (hig == 6 && low == 2) || hig == 4 || low == 4;
    return !flag;
}

int __init = []() {
    // 1位数视为合法
    for (int i = 0; i <= 9; i += 1) {
        dp[1][i] = 1;
    }
    dp[1][4] = 0;
    // 从两位数开始dp
    for (int bit = 2; bit < M; bit += 1) {
        for (int hig = 0; hig <= 9; hig += 1) {
            for (int low = 0; low <= 9; low += 1) {
                // 合格则累计低一位的状态
                if (check(hig, low)) {
                    dp[bit][hig] += dp[bit - 1][low];
                }
            }
        }
    }
    return 0;
}();

int get62(int n) {
    vector<int> eachBit;
    while (n) {
        eachBit.push_back(n % 10);
        n /= 10;
    }

    int ans = 0;
    int hig = -2;
    for (int i = eachBit.size() - 1; i >= 0; i += -1) {
        int bit = i + 1;
        int low = eachBit[i];
        // 一律从0开始
        for (int j = 0; j < low; j += 1) {
            if (check(hig, j)) {
                ans += dp[bit][j];
            }
        }
        // 不合格就直接截断
        if (!check(hig, low)) {
            break;
        }
        hig = low;
    }
    return ans;
}

int main() {
    int right, left;
    while (cin >> left >> right) {
        if (right == 0 && left == 0) {
            break;
        }
        // ！！！ 注意这里调用的时候的一个坑 ！！！
        // ！！！ 合并的写法不能对应正好的num ！！！
        // ！！！ 因此这里要传入num+1 ！！！
        cout << get62(right + 1) - get62(left - 1 + 1) << endl;
    }

    return 0;
}

记忆化dfs

重头戏来了，记忆化dfs 这是必须掌握的一种写法

我们用数位树的思想，用记忆化搜索，我们用高位去往低位搜索，就像树根去搜索，由最后递归的叶节点贡献值一样

这里出现一个重要条件isLimit 是否是上界

• 上界 true 则[0, 上界]
• 上界 false 则[0， 9] 不受限制

递归的参数

• 下一位
• 当前位 （当前位是下一位的前一位）
• 上界传递判断

关于记忆化为什么要判断是否是上界，其实可以从递归法的打表部分理解

我们dp记录的是填了该数字的状态，是所有状态而不是单独为了一个特例而记录的，因此必须要不是上界才能不受限制的记录

---

注意点：

这种写法一般是算0这个状态的

本题没有处理前导零的情况，处理前导零其实也就是增加dfs的参数和递归的判断条件，这点非常灵活

/**
 * https://acm.hdu.edu.cn/showproblem.php?pid=2089
 * 不要62
 * 数位dp
 * ===============================================
 * 记忆化dfs
 */
#include 
using namespace std;

const int M = 1 + 20;
int dp[M][10];
int eachBit[M];

int __init__ = []() {
    memset(dp, -1, sizeof(dp));
    return 0;
}();

// 注意分清高位和低位
inline bool check(int hig, int low) {
    bool flag = (hig == 6 && low == 2) || hig == 4 || low == 4;
    return !flag;
}

// 长度，第几位
// 前一位
// 前一位是否是上界
int dfs(int bit, int hig, bool isLimit) {
    // 0位数，表示搜索完毕
    if (bit == 0) {
        return 1;
    }
    // 不是上界并且搜索过
    if (!isLimit && dp[bit][hig] != -1) {
        return dp[bit][hig];
    }

    int ans = 0;
    // 之前是上界，则接下来最多到s[i]
    // 之前不是上界，则可以[0, 9]
    int cur = isLimit ? eachBit[bit] : 9;
    for (int low = 0; low <= cur; low += 1) {
        if (check(hig, low)) {
            // 累计低一位的状态
            // 上界的判断需要保证高位也是上界，才能传递
            ans += dfs(bit - 1, low, isLimit && low == cur);
        }
    }
    // 我们记录的是完全的状态
    // 就是前面不是上界，则低位不受干扰，可以000~999
    // 反之，若是有上界的，则会缺少数量
    if (!isLimit) {
        dp[bit][hig] = ans;
    }
    return ans;
}

// 预处理将数字拆分掉
int digitalDP(int n) {
    int len = 0;
    while (n) {
        eachBit[++len] = n % 10;
        n /= 10;
    }
    return dfs(len, -1, true);
}

int main() {
    int right, left;
    while (cin >> left >> right) {
        if (right == 0 && left == 0) {
            break;
        }
        cout << digitalDP(right) - digitalDP(left - 1) << endl;
    }

    return 0;
}

Bomb

Problem - 3555 (hdu.edu.cn)

题目描述

统计存在49的数

思路讲解

如果逆序思考，不存在49的数怎么做。那答案跟明显了，直接修改’不要62’的check函数就可以瞬间ac

因此这种思路的代码就不放了

这里展示如何直接统计

Code

上面提到dp的第二维是放[0, 9]的数字，但所有题都要这么写吗？并不是

其实从第二维开始，是存储的状态，这个状态正好是0~9的数字，因此可以这样定义

这里我们换一种方式，题目问什么设什么，49这个状态是否存在

则可以定义两个状态，存在和不存在，但这个不存在怎么转化为存在呢，因此我们再进一步分解

• 未知态 (0标记)
• 前一位是1 (1标记)
• 已合格 (2标记)

如何转化需要根据题意判断

• 0
  • 成功转为1
  • 还是未知0
• 1
  • 成功转为2
  • 还是1
  • 变为未知0
• 2
  • 只要合格了，在本题题意下一直合格

最后递归到叶节点的时候，需要根据状态判断返回值

/**
 * https://acm.hdu.edu.cn/showproblem.php?pid=2089
 * Bomb
 * 数位dp
 * ===============================================
 * 直接统计
 */
#include 
using namespace std;
#define int long long

const int M = 1 + 20;
// 数位
// 状态
//  0 未知态
//  1 前面是4
//  2 整体存在49
int dp[M][3];
int eachBit[M];

int __init__ = []() {
    memset(dp, -1, sizeof(dp));
    return 0;
}();

int dfs(int bit, int state, bool isLimit) {
    // 0位数，表示搜索完毕
    // 状态=2才是合格
    if (bit == 0) {
        return state == 2;
    }
    if (!isLimit && dp[bit][state] != -1) {
        return dp[bit][state];
    }

    int ans = 0;
    int top = isLimit ? eachBit[bit] : 9;
    for (int cur = 0; cur <= top; cur += 1) {
        // 以当前态state为思考基准
        // 有49，合格后面也合格
        if (state == 2) {
            ans += dfs(bit - 1, 2, isLimit && cur == top);
        }
        // 前面有4
        else if (state == 1) {
            // 凑成49合格
            if (cur == 9) {
                ans += dfs(bit - 1, 2, isLimit && cur == top);
            }
            // 凑不成，前面的4作废
            else {
                // 但是当前是否有4还需要判断
                // 可以贡献一个4
                if (cur == 4) {
                    ans += dfs(bit - 1, 1, isLimit && cur == top);
                }
                // 还是未知态
                else {
                    ans += dfs(bit - 1, 0, isLimit && cur == top);
                }
            }
        }
        // 未知态
        else {
            // 可以贡献一个4
            if (cur == 4) {
                ans += dfs(bit - 1, 1, isLimit && cur == top);
            }
            // 还是未知态
            else {
                ans += dfs(bit - 1, 0, isLimit && cur == top);
            }
        }
    }

    if (!isLimit) {
        dp[bit][state] = ans;
    }
    return ans;
}

int digitalDP(int n) {
    int len = 0;
    while (n) {
        eachBit[++len] = n % 10;
        n /= 10;
    }
    // 长度
    // 未知态
    // 是上限
    return dfs(len, 0, true);
}

signed main() {
    int n;
    cin >> n;
    while (n--) {
        int num;
        cin >> num;
        cout << digitalDP(num) << endl;
    }

    return 0;
}

B-number

Problem - 3652 (hdu.edu.cn)

题目描述

统计存在13且整体是13的余数的数

思路讲解

这是一个既有数位前后关系，又存在整体型判断的题

因此dfs中至少有两个状态判断，并且在dp数组中用两个维度记录两个条件的状态

余数的计算可以用高位 * 10 + 低位来计算

这里dp定义

1. 数位
2. 状态1 是否有13
3. 状态2 是否%13==0

Code

/**
 * https://acm.hdu.edu.cn/showproblem.php?pid=3652
 * B-number
 * ===============================================
 * 数位dp
 * 存在13的字串且能被13整除
 */
#include 
using namespace std;
#define int long long

const int M = 10 + 10;
/**
 * @brief
 * 数位
 * 是否有13, 根据题意和推到多状态
 * 余数
 */
int dp[M][3][13];
int eachBit[M];

int __init__ = []() {
    memset(dp, -1, sizeof(dp));
    return 0;
}();

/**
 * @brief
 *
 * @param bit 数位
 * @param state 是否有13 0 什么都不是， 1前一位是1， 2有13
 * @param remainder 余数
 * @param isLimit 上界
 * @return int
 */
int dfs(int bit, int state, int remainder, bool isLimit) {
    if (bit == 0) {
        return state == 2 && remainder == 0;
    }
    if (!isLimit && dp[bit][state][remainder] != -1) {
        return dp[bit][state][remainder];
    }

    int ans = 0;
    int top = isLimit ? eachBit[bit] : 9;
    for (int cur = 0; cur <= top; cur += 1) {
        // 计算余数
        int nextRemainder = (remainder * 10 + cur) % 13;
        // 以目标态state为思考基准
        if (state == 2 || (state == 1 && cur == 3)) {
            ans += dfs(bit - 1, 2, nextRemainder, isLimit && cur == top);
        } else if (cur == 1) {
            ans += dfs(bit - 1, 1, nextRemainder, isLimit && cur == top);
        } else {
            ans += dfs(bit - 1, 0, nextRemainder, isLimit && cur == top);
        }
    }

    if (!isLimit) {
        dp[bit][state][remainder] = ans;
    }
    return ans;
}

int digitDP(int n) {
    int len = 0;
    while (n) {
        eachBit[++len] = n % 10;
        n /= 10;
    }
    return dfs(len, 0, 0, true);
}

signed main() {
    int num;
    while (cin >> num) {
        cout << digitDP(num) << endl;
    }
    return 0;
}

Valley Numer

Problem - 6148 (hdu.edu.cn)

题目描述

当一个数字，从左到右依次看过去数字没有出现先递增接着递减的“山峰”现象，就被称作 Valley Number。

它可以递增，也可以递减，还可以先递减再递增。在递增或递减的过程中可以出现相等的情况。

思路讲解

这是一个数值整体状态的问题

并且一般数位dp的整体状态是一个有限状态机可以锻炼下写状态判断的能力

观察相邻数值可以发现只有三种大小状态关系

• 水平
• 递增
• 递减

而题意只限定了不能先递增接着递减，因此只要将这个状态判走就可以了

本题对前导零的处理需要多加细心判断

上面几题中也存在每个数位的前后关系，但这都是绝对关系，比如13，62。

只要定下这些’1’,‘2’,‘3’,'6’即可，前导0没注意到也不会受影响。因为肯定不会判到

本题中的数值前后关系是广泛的，必须考虑前导0的状态

一般来说前导0是需要特判走的，然后再考虑一般情况

在记忆化的时候一般也要和上界一起判断

类似的题有经典的数位dp：P2657 (SCOI2009) windy 数

Code

/**
 * https://acm.hdu.edu.cn/showproblem.php?pid=6148
 * Valley Numer
 * ===============================================
 * 数位dp
 * 没有出现先递增接着递减
 */
#include 
using namespace std;
#define int long long

#define LEAD_ZERO -10

const int mod = 1e9 + 7;
const int M = 100 + 10;
/**
 * @brief
 * 数位
 * 状态
 *  0 水平
 *  1 递增
 *  2 递减
 *  3 不合法
 */
int dp[M][10][4];
string s;

/// @brief
/// @param bit 数位
/// @param pre 前一个数
/// @param state 状态
/// @param isLimit 是否是上界
/// @param leadZero 是否是前导零
/// @return
int dfs(int bit, int pre, int state, bool isLimit, bool leadZero) {
    // 如果递归了3
    // 那么return 时要判断state ?= 3
    if (bit == 0) {
        // return state != 3;
        return 1;
    }
    if (!isLimit && !leadZero && dp[bit][pre][state] != -1) {
        return dp[bit][pre][state];
    }

    int ans = 0;
    int top = isLimit ? s[bit] - '0' : 9;
    for (int cur = 0; cur <= top; cur += 1) {
        int nextState = state;

        // 水平 只有这里才考虑前导零
        if (state == 0) {
            // 前导零或者相等
            if (leadZero || pre == cur) {
                nextState = 0;
            }
            // ↑
            else if (pre < cur) {
                nextState = 1;
            }
            // ↓
            else if (pre > cur) {
                nextState = 2;
            }
        }
        // 上升
        else if (state == 1) {
            // 相等
            if (pre == cur) {
                nextState = state;
            }
            // ↑
            else if (pre < cur) {
                nextState = 1;
            }
            // ↓
            else if (pre > cur) {
                // 先上再下不合格
                // nextState = 3;
                continue;
            }
        }
        // 下降
        else if (state == 2) {
            // 相等
            if (pre == cur) {
                nextState = state;
            }
            // ↑
            else if (pre < cur) {
                nextState = 1;
            }
            // ↓
            else if (pre > cur) {
                nextState = 2;
            }
        }
        // else if (state == 3) {
        //     // nextState = 3;
        //     continue;
        // }

        ans += dfs(bit - 1, cur, nextState, isLimit && cur == top,
                   leadZero && cur == 0);
        ans %= mod;
    }

    if (!isLimit && !leadZero) {
        dp[bit][pre][state] = ans;
    }
    return ans;
}

int digitDP() {
    int len = s.size();
    reverse(s.begin(), s.end());
    s = '*' + s;
    return dfs(len, LEAD_ZERO, 0, true, true);
}

signed main() {
    memset(dp, -1, sizeof(dp));
    int n;
    cin >> n;
    while (n--) {
        cin >> s;
        cout << digitDP() - 1 << endl;
    }
    return 0;
}

吉哥系列故事——恨7不成妻

Problem - 4507 (hdu.edu.cn)

题目描述

求和7无关的数字的平方和

和7有关的定义：(满足其一即可)

1 整数中某一位是7
2 整数的每一位加起来的和是7的整数倍
3 这个整数是7的整数倍

思路讲解

首先说明，楼主本题是妥妥CV的

这题可以说是数位dp中的战斗机

如果仅仅是限制3个条件其实还好，但是题目问的是“平方和”这就一下子拔高了该题的难度

这里需要知道如何累计前一位的数值和和平方和，需要一定的数学功底，楼主数学极差就不做过多解释了

主要学习这里数位dp三个限制条件的写法

Code

/**
 * https://acm.hdu.edu.cn/showproblem.php?pid=4507
 * 吉哥系列故事——恨7不成妻
 * ===============================================
 * 数位dp
 * 数位中的战斗机
 * -----------------------------------------------
 * 与7无关的数 (三个条件)
 * 1、整数中某一位是7；　　
 * 2、整数的每一位加起来的和是7的整数倍；
 * 3、这个整数是7的整数倍；
 */
// 单纯数位dp话没什么，但还要求平方和真的伤不起
// 抄的网上，基本都是一样的解法
#include 
using namespace std;
#define int long long

const int mod = 1e9 + 7;

struct Node {
    int cnt = -1;
    int addSum = 0;
    int squSum = 0;

    Node() {
    }
    Node(int x, int y, int z) : cnt(x), addSum(y), squSum(z) {
    }
};

const int M = 20 + 10;
/**
 * 数位
 * 加和 mod 7
 * 该数本身 mod 7
 */
Node dp[M][7][7];
int eachBit[M];
int POW[M];
int __init__ = []() {
    POW[0] = 1;
    for (int i = 1; i < M; i += 1) {
        POW[i] = POW[i - 1] * 10 % mod;
    }
    return 0;
}();

/// @brief
/// @param bit 数位
/// @param sum 加和 mod 7
/// @param val 该数 mod 7
/// @param isLimit 上界
/// @return
Node dfs(int bit, int sum, int val, bool isLimit) {
    if (bit == 0) {
        return Node((sum != 0 && val != 0), 0, 0);
    }
    if (!isLimit && dp[bit][sum][val].cnt != -1) {
        return dp[bit][sum][val];
    }

    Node ans(0, 0, 0);
    int top = isLimit ? eachBit[bit] : 9;
    for (int cur = 0; cur <= top; cur += 1) {
        // 第一个条件不能有7
        if (cur == 7) {
            continue;
        }
        // 数位dp基操，获取前一位状态
        Node nex = dfs(bit - 1, (sum + cur) % 7, (val * 10 + cur) % 7,
                       isLimit && cur == top);

        ans.cnt += nex.cnt;
        ans.cnt %= mod;

        // 注意前一轮bit-1还是保留原来的数值
        // 但是贡献给bit时，就需要算上POW
        int tmp = cur * POW[bit - 1] % mod;
        // 累计前一轮的和 cnt 要乘上 pow倍
        ans.addSum += (nex.addSum + tmp * nex.cnt % mod) % mod;
        ans.addSum %= mod;
        // (a+b)^2 = a^2 + 2*a*b + b^2
        ans.squSum += (nex.squSum + tmp * tmp % mod * nex.cnt % mod +
                       2 * tmp * nex.addSum % mod) %
                      mod;
        ans.squSum %= mod;
    }

    if (!isLimit) {
        dp[bit][sum][val] = ans;
    }
    return ans;
}

int digitDP(int n) {
    int len = 0;
    while (n) {
        eachBit[++len] = n % 10;
        n /= 10;
    }
    return dfs(len, 0, 0, true).squSum;
}

signed main() {
    memset(dp, -1, sizeof(dp));
    int n;
    cin >> n;
    while (n--) {
        int left, right;
        cin >> left >> right;
        int ans = digitDP(right) - digitDP(left - 1);
        cout << (ans + mod) % mod << endl;
    }
    return 0;
}

---

---

---

END