「学习笔记」数位 DP

「学习笔记」数位 DP

意义不大的题不写了。

点击查看目录

概述

数位 DP 一般用来解决「在一个较大的区间内统计具有一定特征的数的数量」的问题。

数位 DP 一般有两种做法:

  • 递推法:首先需要预处理出具有一定条件的数的个数,然后将上限按数位拆分开来考虑贡献。
  • 暴搜法:直接记忆化搜索具有特定条件的数的个数。

例题

P2657 [SCOI2009] windy 数

思路

本题使用递推。

\(f_{i,j}\) 表示最高位为 \(j\)\(i\) 位 windy 数数量(\(j\) 可以为 \(0\)),显然:

\[f_{i, j} =
\begin{cases}
1 &i=1\\
\sum_{k=0}^{9}[\left|j - k\right| \ge 2]f_{i - 1, k} &\text{otherwise}
\end{cases}
\]

然后计算答案,把上限 \(x\) 的每一位拆开(假设 \(x\)\(l\) 位),考虑到第 \(i\) 位时,前 \(l-i\) 位与 \(x\) 相同,后 \(i\) 位的方案数用 \(f_{i,j}\) 计算。

但是有一个问题:\(0001\) 去除前导零后合法,但是 \(10001\) 不合法,因此为了保证之后计算的数依然合法,\(f_{4, 0}\) 不会记录像 \(0001\) 这样去除前导零后合法但在最高位再加上一个数后不合法的数的数量。

此时我们需要一个辅助数组 \(g_{i}\),即被漏算了的首位为 \(0\)\(i\) 位数的数量。当第 \(i-1\) 位大于等于 \(2\) 时,首位为 \(0\)\(i\) 位数不会被漏算(因为此时第 \(i\) 位和第 \(i-1\) 差值大于等于为 \(2\),仍然合法),但是第 \(i-1\) 位小于 \(2\) 的数会被漏算,所以易得:

\[g_{i} = g_{i - 1} + f_{i - 1, 0} + f_{i - 1, 1}
\]

计算答案时加上即可。

代码

点击查看代码
const ll N = 15, inf = 1ll << 40, P = 1e9 + 7;
namespace SOLVE {
	ll a, b, f[N][N], g[N];
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}

	inline ll GetAns (ll x) {
		ll len = 0, num[N] = {0}, sum = 0;
		while (x) num[++len] = x % 10, x /= 10;
		for_ (i, len, 1) {
			if (i == len) {
				_for (j, 0, num[i] - 1) sum += f[i][j];
				sum += g[i];
				continue;
			}
			_for (j, 0, num[i] - 1) {
				if (abs (j - num[i + 1]) < 2) continue;
				sum += f[i][j];
			}
			if (abs (num[i] - num[i + 1]) < 2) break;
		}
		return sum;
	}

	inline void In () {
		a = rnt (), b = rnt ();
		return;
	}
	inline void Solve () {
		_for (i, 0, 9) f[1][i] = 1;
		g[1] = 2;
		_for (i, 2, 10) {
			g[i] = g[i - 1] + f[i - 1][0] + f[i - 1][1];
			_for (j, 0, 9) {
				_for (k, 0, 9) {
					if (abs (j - k) < 2) continue;
					f[i][j] += f[i - 1][k];
				}
			}
		}
		return;
	}
	inline void Out () {
		printf ("%lld\n", GetAns (b + 1) - GetAns (a));
		return;
	}
}

P4317 花神的数论题

思路

使用递推。

\(f_{i, j, k}\) 表示有 \(i\) 位,最高位为 \(j(j\in\{0,1\})\),有 \(k\)\(1\)二进制数。显然:

\[\begin{aligned}
f_{i, 0, j} &=
\begin{cases}
1 &j=0\\
f_{i - 1, 0, j} + f_{i - 1, 1, j} &\text{otherwise}
\end{cases}\\
f_{i, 1, j} &=
\begin{cases}
1 &i=1\\
f_{i - 1, 0, j - 1} + f_{i - 1, 1, j - 1} &\text{otherwise}
\end{cases}
\end{aligned}
\]

然后由于要算乘积,要使用快速幂计算有 \(k\)\(1\) 的二进制数的乘积总和。

P4124 [CQOI2016]手机号码

思路

使用暴搜。

定义函数:

ll Dfs (ll p, ll a, ll b, ll sm, ll fr, ll et, ll li)

其中,\(p\) 表示第几位,\(a\) 表示第 \(p\) 位的数,\(b\) 表示第 \(p+1\) 位的数,\(sm\) 表示是否已经存在一样的连续三个数,\(fr\) 是否出现过 \(4\)\(et\) 是否出现过 \(9\)\(li\) 前面几位是否和上限完全一样(这个会影响搜索时下一位的的数,如果完全一样则下一位的的数不能超过上限的这一位,否则可以到 \(9\))。

代码

点击查看代码
ll Dfs (ll p, ll a, ll b, ll sm, ll fr, ll et, ll li) {
	if (fr && et) return 0;
	if (!p) return sm;
	if (!li && f[p][a][b][sm][fr][et] > 0) return f[p][a][b][sm][fr][et];
	ll sum = 0, mx = li ? t[p] : 9;
	_for (i, 0, mx) sum += Dfs (p - 1, i, a, sm || (i == a && i == b), fr || (i == 4), et || (i == 8), li && i == mx);
	if (!li) f[p][a][b][sm][fr][et] = sum;
	return sum;
}
inline ll GetAns (ll x) {
	if (x < 1e10) return 0;
	ll len = 0, sum = 0;
	while (x) t[++len] = x % 10, x /= 10;
	memset (f, -1, sizeof (f));
	_for (i, 1, t[len]) sum += Dfs (len - 1, i, 0, 0, i == 4, i == 8, i == t[len]);
	return sum;
}

haha数

题意

一个正整数,当且仅当在十进制表示下,它的各位非零数字能整除该数本身时(即它的所有非零位的数字都是该数的约数),被称作 haha 数。给定 \(l\)\(r\),求在 \([l, r]\) 范围内 haha 数的个数。

\(1\le l \le r \le9\times10^{18}\)

思路

使用暴搜。

定义函数:

ll Dfs (ll p, ll md, ll sta, ll li)

其中,\(p\) 表示第几位,\(md\) 表示当前的数膜 \(\operatorname{lcm}(1,2,3,4,5,6,7,8,9)=2520\) 的余数,\(sta\) 表示 \(2\sim8\) 的数是否出现过的状态,\(li\) 前面几位是否和上限完全一样。

最后判断合法时,看 \(md\) 是否是 \(sta\) 记录的所有出现过的数的倍数即可。

代码

点击查看代码
inline ll w (ll x) { return (x < 2) ? 0 : (1 << (x - 2)); }
inline bool Check (ll md, ll sta) {
	_for (i, 2, 9) if ((sta & w (i)) && (md % i)) return 0;
	return 1;
}

ll Dfs (ll p, ll md, ll sta, ll li) {
	if (!p) return Check (md, sta);
	if (!li && f[p][md][sta] >= 0) return f[p][md][sta];
	ll sum = 0, mx = li ? t[p] : 9;
	_for (i, 0, mx) sum += Dfs (p - 1, (md * 10 + i) % 2520, sta | w (i), li & (i == mx));
	if (!li) f[p][md][sta] = sum;
	return sum;
}

0和1的熟练

题意

有一个程序员,他使用只有两个按键的键盘打字。这两个按键就是 \(0\)\(1\),只有达到高端境界的人才能出入此境。记住,只有从 \(l\)\(r\) 的所有数都手打过一遍了才能练就如此功夫。作为真正的高手,你一定能快速地回答区间 \([l,r]\) 中有多少数字的二进制表示(不含前导零)中 \(0\) 的个数不少于 \(1\) 的个数,因为你每天都进行一遍这个练习。

\(1\le l<r\le2\times10^9\)

思路

使用暴搜。

定义函数:

ll Dfs (ll p, ll c1, ll len, ll li)

其中,\(p\) 表示第几位,\(c1\) 表示当前的数有几个 \(1\)\(len\) 当前的数变为二进制后有多少位,\(li\) 前面几位是否和上限完全一样。

代码

点击查看代码
ll Dfs (ll p, ll c1, ll len, ll li) {
	if (!p) return len ? (len - c1 >= c1) : 1;
	if (!li && f[p][c1][len] >= 0) return f[p][c1][len];
	ll sum = 0, mx = li ? t[p] : 1;
	_for (i, 0, mx) sum += Dfs (p - 1, c1 + (i == 1), len + (len || i), li & (i == mx));
	if (!li) f[p][c1][len] = sum;
	return sum;
}

苍与红的试炼

题意

辉煌的时代终将落幕吗,只有时间的车轮滚滚向前。

来自苍空之上的,是点亮前路的希望,是划破阴云的曙光。

为协助天城追回那被铅色未来蒙蔽前路之人,你需要完成天城的试炼以取得天城的认可。

漫樱飞舞的古城中,有一些标有数字 \(0\sim9\) 的御守。现在天城给了你一个正整数 \(d\),你需要按照某种顺序排列一些御守,写下由这些御守拼成的数字 \(x\),并保证 \(x\) 能被 \(d\) 整除。

然而想通过「重樱之鬼谋」的考验哪有这么简单。天城还指定了一个正整数 \(s\),你必须保证你所选择的所有御守上的数字之和等于 \(s\) 才能满足要求。同时为了检验你的能力,天城要求你给出满足要求的最小的 \(x\)。当然如果不存在满足要求的 \(x\),你也必须要向天城指出这一点。

跨越时间之长河,斩断命运之枷锁。挑战者啊,穷尽武略与智谋,迎接来自顶点的试炼吧。

\(1\le d\le500, 1\le s\le 5000\)

思路

没有上限,所以直接深搜会爆掉。

那么考虑广搜,放入队列一个数对 \((a, b)\),表示当前数膜 \(d\) 等于 \(a\),每一位数之和等于 \(b\)。显然当 \(a=0,b=s\) 时搜索结束。

状态只有 \(500\times5000=2500000\) 种,记忆化一下即可。

代码

点击查看代码
namespace SOLVE {
	const ll N = 1e7;
	ll d, s, f[N], g[N], jl[N], ans;
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	void Print (ll p) {
		if (p == 1) return;
		Print (g[p]);
		printf ("%lld", f[p]);
	}
	inline void In () {
		d = rnt (), s = rnt ();
		return;
	}
	inline void Solve () {
		std::queue <ll> q;
		q.push (0);
		jl[0] = 1;
		ll h = 0, t = 1;
		while (!q.empty ()) {
			ll fr = q.front ();
			++h, q.pop ();
			_for (i, 0, 9) {
				ll dd = (fr % 501 * 10 + i) % d;
				ll ss = fr / 501 + i;
				ll num = dd + ss * 501;
				if (ss > s) continue;
				if (jl[num]) continue;
				f[++t] = i, g[t] = h;
				if (!dd && ss == s) {
					ans = t;
					return;
				}
				jl[num] = 1;
				q.push (num);
			}
		}
		return;
	}
	inline void Out () {
		if (ans) Print (ans), puts ("");
		else puts ("-1");
		return;
	}
}

原文链接:https://www.cnblogs.com/Keven-He/p/NumberDP.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:「学习笔记」数位 DP - Python技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • Python实现的质因式分解算法示例

    Python实现的质因式分解算法示例 质因式分解是一种将一个正整数分解成若干个质数乘积的方法。在Python中,可以使用多种算法来实现质式分解,包括试除法、分解质因数、Pollard-Rho算法等。本文将详细讲解Python实现的质因式分解算法示例,包括算法原理、实现过程和示例。 算法原理 质因式分解是一种将一个正整数分解成若干个质数乘积方法。具体来说,质因…

    python 2023年5月13日
    00
  • Leetcode Practice — 栈和队列

    目录 155. 最小栈 思路解析 20. 有效的括号 思路解析 1047. 删除字符串中的所有相邻重复项 思路解析 1209. 删除字符串中的所有相邻重复项 II 思路解析 删除字符串中出现次数 >= 2 次的相邻字符 剑指 Offer 09. 用两个栈实现队列 239. 滑动窗口最大值 思路解析 155. 最小栈 设计一个支持 push ,pop ,…

    算法与数据结构 2023年4月17日
    00
  • python算法与数据结构之单链表的实现代码

    下面是详细讲解“Python算法与数据结构之单链表的实现代码”的完整攻略,包括节点类的定义、链表类的定义、节点的插入、删除和查找等操作,以及两个示例说明。 节点类的定义 节点类表示单链表的节点,包括节点值和下一个节点指针。以下是Python实现节点类的示例代码: class ListNode: def __init__(self, val=0, next=N…

    python 2023年5月14日
    00
  • Python猜数字算法题详解

    下面是详细讲解“Python猜数字算法题详解”的完整攻略,包括算法原理、Python实现和两个示例说明。 算法原理 猜数字算法题是一种经典的算法题,其基本思想是通过二分查找的方式,逐步缩小猜测范围,最终猜中目标数字。具体实现过程如下: 首先确定猜测范围,通常为1到100之间的整数。 然后猜测中间的数字,即猜测范围的中间值。 根据猜测结果,如果猜中了目标数字,…

    python 2023年5月14日
    00
  • 神经网络(BP)算法Python实现及应用

    神经网络(BP)算法Python实现及应用 BP神经网络是一种常用的人工神经网络,它可以用于分类、回归等任务。在Python中,可以使用多种库实现BP神经网络包括TensorFlow、Keras、PyTorch等。本文将详细讲解神经网络(BP)算法Python实及应用的完整攻略,包括算法原理、Python实现过程和示例。 算法原理 BP神经网络是一前向反馈神…

    python 2023年5月13日
    00
  • Python实现的三层BP神经网络算法示例

    以下是关于“Python实现的三层BP神经网络算法示例”的完整攻略: 简介 BP神经网络是一种常见的人工神经网络,它可以用于分类和回归问题。本教程将介绍如何使用Python实现三层BP神经网络算法,并讨论如何使用该算法进行分类。 步骤 1.导入库和数据 首先,我们需要导入必要的库,包括numpy和pandas。在Python中,可以使用以下代码导入这些库: …

    python 2023年5月14日
    00
  • C语言如何建立链表并实现增删查改详解

    这是一个比较复杂的问题,需要严谨的思考和详细的解释。下面我将按照以下三个部分,分别介绍: 什么是链表,链表的基本结构和实现方法 如何在C语言中建立链表并实现增删查改 两个示例说明 1. 链表的基本结构和实现方法 链表是一种线性数据结构,每个节点包含两个域:一个数据域和一个指针域。数据域存储节点的数据,指针域存储下一个节点的地址。每个节点都可以独立分配空间,所…

    数据结构 2023年5月17日
    00
  • python实现最大子序和(分治+动态规划)

    下面是详细讲解“Python实现最大子序和(分治+动态规划)”的完整攻略。 1. 什么是最大子序和? 最大子和是指在一个序列中,找到一个连续的子序列,使得该子序列的和最大。 2. Python实现最大子序和的方法 2.1 分治法 下面是Python使用分治法实现最大子序和的示例: def max_subarray(nums): if len(nums) ==…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部