首页 > 其他分享 >「学习笔记」数位DP

「学习笔记」数位DP

时间：2024-07-09 21:42:27浏览次数：9  
标签：long return lead int len limit 笔记 DP 数位

虽然叫 DP，但是基本所有数位 DP 题我们都可以用好打好想好理解的 记忆化搜索 来做。

记搜模板

有一个大致的记忆化搜索模板， AK ALL 数位 DP

int dfs(int len, bool lead, bool limit, ...){
	if(!len) return 1; //len = 0,即所有位都搜完
	if(~f[len][lead][limit]...) return f[len][lead][limit]...; //记忆化，搜过当前情况直接返回
	
	int r = limit ? lim[len] : 9, ans = 0; //若有上限搜到当前位的限制，否则搜到9
	for(int i=0; i<=r; i++){
		ans += dfs(len-1, lead&&i==0, limit&&i==r, ...);
	}
	return f[len][lead][limit]... = ans;
}

$ f[][][]... $ 数组用来记忆化，\(lim[i ]\) 表示当前数第 \(i\) 位的上限。

\(dfs 中的变量 lead 和 limit\) 分别表示有无前导零和是否是上限，\(len\) 表示现在搜到第几位（从高位到低位搜）。


预处理 如下：

int work(int x){
	int cnt = 0;
	while(x)
	{
		lim[++cnt] = x % 10;
		x /= 10;
	}
	memset(f, -1, sizeof f);
	return dfs(cnt, -10, true, true);
}

注意

数据范围看清，记得开 long long

对代码的解释

主要用了填数的思想。

\(limit\)

对于很多题，我们都需要求 1~n 中有多少符合条件的数，举个例子，\(n = 866666\)，如果最高位搜的数 \(<8\) 时，好说，后面几位随便是什么都可以，但若最高位搜的数 \(=8\) 时，后一位需要保证搜 \(<=6\) 的数，不然就超出 \(n\) 的范围了。这就是我们记 \(limit\) 的原因。

\(lead\)

有些题保证不能有前导零，需要记一下。

题型

连续3个6

启示录
题意：含有连续 3 个 6 的数为魔鬼数，给定 \(x\)，求第 \(x\) 小的魔鬼数。

该数整除其各位数字之和

记一个 \(sum\) 表示各位数字之和，\(s\) 表示当前模数，\(mod\) 表示当前数 mod s 之后的值。

long long dfs(int len, int sum, int mod, int limit){
	if(!len) return sum == s and !mod ? 1 : 0;
	if(f[len][sum][mod]!=-1 and !limit) return f[len][sum][mod];
	long long ans = 0, m = limit ? lim[len] : 9;

	for(int i=0; i<=m; i++){
		ans += dfs(len-1, sum+i, (mod*10+i)%s, limit and (i == m));
	}
	return limit ? ans : f[len][sum][mod] = ans;
}

long long work(long long x){
	int cnt = 0;
	long long ans = 0;
	while(x)
	{
		lim[++cnt] = x % 10;
		x /= 10;
	}
	for(s=1; s<=cnt*9; s++){
		memset(f, -1, sizeof f);
		ans += dfs(cnt, 0, 0, 1);
	}
	return ans;
}

设有 \(cnt\) 位数，那么 \(sum\) 最大可以到 \(9 * cnt\)，我们将从 \(0 - 9*cnt\) 的所有数作为模数都搜一遍，搜索结束时判断一下 是否有 \(sum == s && mod == 0\) 即可 。

月之谜

有趣的数

code 


#include<bits/stdc++.h>
#define in(n) scanf("%lld", &n)
using namespace std;

long long L, R;
int s, T;
long long f[20][200][200], lim[200];

long long dfs(int len, int sum, int mod, int limit){
	if(!len) return sum == s and !mod ? 1 : 0;
	if(f[len][sum][mod]!=-1 and !limit) return f[len][sum][mod];
	long long ans = 0, m = limit ? lim[len] : 9;

	for(int i=0; i<=m; i++){
		ans += dfs(len-1, sum+i, (mod*10+i)%s, limit and (i == m));
	}
	return limit ? ans : f[len][sum][mod] = ans;
}

long long work(long long x){
	int cnt = 0;
	long long ans = 0;
	while(x)
	{
		lim[++cnt] = x % 10;
		x /= 10;
	}
	for(s=1; s<=cnt*9; s++){
		memset(f, -1, sizeof f);
		ans += dfs(cnt, 0, 0, 1);
	}
	return ans;
}

int main(){
	// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);

	in(R);
	printf("%lld\n", work(R));
    
	return 0;
}

二进制

处理 \(lim[]\) 时换成二进制的处理即可。

int dfs(int len, int _0, int _1, bool limit, bool lead){
	if(!len&&!lead)return _0>=_1;
	if(!len)return 0;
	if(~f[len][_0][_1][limit][lead]) return f[len][_0][_1][limit][lead];

	int r = limit ? lim[len] : 1;
	int ans = 0;
	for(int i=0; i<=r; i++){
		ans += dfs(len-1, (i==0&&!lead)?(_0+1):_0, (i==1)?(_1+1):_1, limit&&(i==r), lead&&(i==0));
	}
	return f[len][_0][_1][limit][lead] = ans;
}

int work(int x){
	int cnt=0;
	while(x)lim[++cnt]=x&1,x>>=1;
	memset(f, -1, sizeof f);
	return dfs(cnt,0,0,1,1);
}

0和1的熟练

code 


#include<bits/stdc++.h>
#define int long long 
#define ll long long
using namespace std;

int L, R;
int f[35][35][35][2][2];
int lim[35];

int dfs(int len, int _0, int _1, bool limit, bool lead){
	if(!len&&!lead)return _0>=_1;
	if(!len)return 0;
	if(~f[len][_0][_1][limit][lead]) return f[len][_0][_1][limit][lead];

	int r = limit ? lim[len] : 1;
	int ans = 0;
	for(int i=0; i<=r; i++){
		ans += dfs(len-1, (i==0&&!lead)?(_0+1):_0, (i==1)?(_1+1):_1, limit&&(i==r), lead&&(i==0));
	}
	return f[len][_0][_1][limit][lead] = ans;
}

int work(int x){
	int cnt=0;
	while(x)lim[++cnt]=x&1,x>>=1;
	memset(f, -1, sizeof f);
	return dfs(cnt,0,0,1,1);
}

signed main(){

    scanf("%lld%lld", &L, &R);
    printf("%lld ", work(R) - work(L-1));
    
     return 0;
}

各位数字都被该数本身整除

我们知道 \(0,1,2,3,4,5,6,7,8,9\) 的最小公倍数为 2520，所以记该数本身 mod 2520 的值，再记一个各位数字之和的最小公倍数即可。

inline int get_gvc(int gvc, int now){
	if(!now) return gvc;
	else return gvc * now / __gcd(gvc, now);
}

inline void yuen(){
	int tot = 0;
	for(int i=1; i<=2520; i++){
		if(2520 % i == 0) a[i] = ++tot;
	}
	for(int i=0; i<=18; i++) g[i] = pow(10, i);
}

inline ll dfs(int len, int sum, int gvc, bool limit, bool lead){
	if(!len) return (sum % gvc == 0);
	if(~f[len][sum][a[gvc]] and !limit and !lead) return f[len][sum][a[gvc]];

	int r = limit ? lim[len] : 9;

	ll ans = 0;
	for(int i=0; i<=r; i++){
		ans += dfs(len-1, (sum*10+i)%2520, get_gvc(gvc, i), limit&&(i==r), lead&&(i==0));
	}
	if(limit or lead) return ans;
	return f[len][sum][a[gvc]] = ans;
}

inline ll work(ll x){
	int cnt = 0;
	while(x){ lim[++cnt] = x % 10; x /= 10;}
	return dfs(cnt, 0, 1, true, true);
}

haha数

code 
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll L, R;
int lim[22];
int T, a[2530];
ll f[20][2530][60], g[20];

inline int get_gvc(int gvc, int now){
	if(!now) return gvc;
	else return gvc * now / __gcd(gvc, now);
}

inline void yuen(){
	int tot = 0;
	for(int i=1; i<=2520; i++){
		if(2520 % i == 0) a[i] = ++tot;
	}
	for(int i=0; i<=18; i++) g[i] = pow(10, i);
}

inline ll dfs(int len, int sum, int gvc, bool limit, bool lead){
	if(!len) return (sum % gvc == 0);
	if(~f[len][sum][a[gvc]] and !limit and !lead) return f[len][sum][a[gvc]];

	int r = limit ? lim[len] : 9;

	ll ans = 0;
	for(int i=0; i<=r; i++){
		ans += dfs(len-1, (sum*10+i)%2520, get_gvc(gvc, i), limit&&(i==r), lead&&(i==0));
	}
	if(limit or lead) return ans;
	return f[len][sum][a[gvc]] = ans;
}

inline ll work(ll x){
	int cnt = 0;
	while(x){ lim[++cnt] = x % 10; x /= 10;}
	return dfs(cnt, 0, 1, true, true);
}

signed main(){
	//freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);

	memset(f, -1, sizeof f); yuen();

	cin>>T;
	while(T--)
	{
		scanf("%lld%lld", &L, &R);
    	printf("%lld\n", work(R) - work(L-1));
	}
    
    return 0;
}

标签：long,return,lead,int,len,limit,笔记,DP,数位
From： https://www.cnblogs.com/YuenYouth/p/18292782

相关文章

  • 下降幂学习笔记
    下降幂学习笔记还原精灵还我笔记——来自打完笔记但关电脑前没有保存的某人的呐喊。定义下降幂就是形如\(n^{\underline{m}}\)的式子，表示\[n^{\underline{m}}=\prod_{i=n-m+1}^{n}=\frac{n!}{(n-m)!}\]同理声明一个上升幂\(n^{\overline{m}}\)，表示\[n^{\overline{m}}=\pr......
  • 根本听不懂的也看不懂的上课笔记
    https://qoj.ac/problem/8008不难发现，随机到某些位置，之后最短路先O（nm）预处理出能到的点，考虑最小的随机位置CF741C考虑二分图染色，对于每一对情侣，相互连边，相邻的2i和2i-1也连边，都代表颜色不同，CF1656G限制是只有一个环，先随便造一个回文排列现有一个排列p如果i，j处在同一......
  • 信创学习笔记(二),信创之CPU芯片架构思维导图
    创作不易只因热爱!!热衷分享，一起成长!“你的鼓励就是我努力付出的动力”各架构,操作系统,指令,代表生产商,服务器使用产品主要供应商......
  • 信创学习笔记(一),信创内容思维导图
    创作不易只因热爱!!热衷分享，一起成长!“你的鼓励就是我努力付出的动力”用一张图归纳学习信创内容信创内容思维导图......
  • 快速傅里叶变换复习笔记
    .real()成员函数FFT的本质是快速计算多项式的点值表示对负实数的四舍五入需要-0.5编写函数接收数组地址时，注意不能破坏原数组FFT有较为严重的精度问题，double甚至难以准确计算两个\(10^9\)级别的整数相乘的结果，即使采用longdouble也时常无法得到准确的答案，这或许也是模板题中......
  • Bullet 学习笔记之 软体仿真流程（二） 软体碰撞检测与响应
    简述Bullet中软体的碰撞检测与响应算法，仅针对Soft类型，Deformable类型不包含在这篇文章中。1.软体碰撞检测在BulletPhysics中，软体的碰撞检测采用的是“点-面”的方法，即分别用两个软体的m_ndbvt和m_fdbvt做碰撞检测，两个bvh树之间的遍历方法不在此展开，当Node......
  • 文案板块：5分钟掌握批量创作100条小红书爆款笔记文案（机器人实操训练）
    引言在数字营销的世界里，内容为王。但如何在短时间内制作出大量高质量的内容，以吸引并保持受众的注意力呢？作为普通人，你要有结果，你除非有非常过人的内容制作能力，不然就是批量化，否则大概率很难有办法突破短时间内的流量爆发。这种搞流量的方法确实也适合小白，因为基本上都是重复......
  • 苹果笔记本能玩网页游戏吗 苹果电脑玩steam游戏怎么样 苹果手机可以玩游戏吗 mac电脑
    苹果笔记本无疑是优秀的“办公助手”，但对于游戏爱好者来说，它的游戏性能如何？首先，我们来讨论苹果笔记本在玩网页游戏方面的表现。一、苹果笔记本能玩网页游戏吗苹果笔记本历代都配备了高分辨率的屏幕和优质的显示技术，这使得苹果笔记本相比于Windows电脑，在视觉体验上有着明显的......
  • clean code-代码整洁之道 阅读笔记（第十七章 终章）
    大纲第十七章味道与启发17.1注释C1：不恰当的信息C2：废弃的注释C3：冗余注释C4：糟糕的注释C5：注释掉的代码17.2环境E1：需要多步才能实现的构建E2：需要多步才能做到的测试17.3函数F1：过多的参数F2：输出参数F3：标识参数F4：死函数17.4一般性问题G1：一个源文件中存在多种语......
  • Living-Dream 系列笔记 第61期
    退役选手复活后的第一篇。https://www.luogu.com.cn/problem/SP4033其实只要一个insert.就是插入时没新建节点\(\to\)自己是别人前缀，插入时途经了别人的结束节点\(\to\)别人是自己前缀。code#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+5,M=31;i......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99