(数位dp) 算法竞赛入门到进阶 书本题集
文章目录
- 前言
- 题目
- 不要62
- 题目描述
- 思路讲解
- Code
- 递推分组累计
- 递推合并累计
- 记忆化dfs
- Bomb
- 题目描述
- 思路讲解
- Code
- B-number
- 题目描述
- 思路讲解
- Code
- Valley Numer
- 题目描述
- 思路讲解
- Code
- 吉哥系列故事——恨7不成妻
- 题目描述
- 思路讲解
- Code
- END
前言
本文中的题目来自罗勇军老师和郭卫斌老师的《算法竞赛入门到进阶》
俗称小黑书
有人在vjudge中整理了所有的题目题:《算法竞赛入门到进阶》 题目汇总 - Virtual Judge (csgrandeur.cn)
罗老师的博客:罗勇军_CSDN博客
数位dp从题面上来看就是非常有特色的一类题
- 数据范围非常大(不能暴力)
- 和每个数位有关
- 有明显的数学风味
- 喜欢问范围[L, R]中有多少(不)符合的数
- 一般问的比较直白不会出阅读理解型的题
数位dp一般有两种实现方式,递推和记忆化dfs
递推比较重视推到能力,而记忆化dfs也非常好写且模板话程度高。且处理更加复杂的问题时代码量远少于递推,因此更受大家喜爱。
题目
不要62
Problem - 2089 (hdu.edu.cn)
题目描述
统计不存在62和4的数
思路讲解
非常经典的数位dp,问的非常直白
本题用递推和记忆化dfs两种方式实现讲解
定义dp
- 数位
- 可以填写的数字
dp[][]
当前第i个数位,填写数字j的合格的数量
Code
递推分组累计
递推法就两步
- 打表 低位贡献给高位
- 累计 高位决定低位
打表
- 第一个循环 枚举数位
- 第二个循环 枚举当前位 (高位)
- 第三个循环 枚举前一位 (低位)
如果合格,则低位贡献给高位,注意不同题目初始化递推条件不一样
累计
- 累计长度相等的数值
- 累计所有长度第的数值
如当前n=12345是个五位数
则①表示累计也是长度为5的数,②表示累计所有长度不足5的数
在长度5的时候,后面的枚举位可以为0;而不足5的时候不能累计有前导0的情况,不然会重复累计
/**
* https://acm.hdu.edu.cn/showproblem.php?pid=2089
* 不要62
* 数位dp
* 经典数位dp
*/
#include <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 是否有13
- 状态2 是否%13==0
Code
/**
* https://acm.hdu.edu.cn/showproblem.php?pid=3652
* B-number
* ===============================================
* 数位dp
* 存在13的字串且能被13整除
*/
#include <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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;
}