数位dpの学习笔记

本文主要是介绍数位dpの学习笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数位dp的题目类型基本都是 “求 \([L,R]\) 之间中满足某个条件的数的个数。”

数据通常都超过了 \(int\) 甚至 \(long\) \(long\) 的范围。我们使用 \(O(n)\) 的算法是完全不能通过的。

于是我们通常使用 “试填法” 的思想，通过DP预处理，再逐位枚举拼凑，或者直接使用记忆化搜索。

P2602 [ZJOI2010]数字计数

状态设计

设 \(f[pos][j][num]为第pos位，最高位为j，num的个数\)。

我们就可以得到一个状态转移方程：\(f[pos][j][num]=f[pos-1][k][num]+num在这一位上出现的次数\) 。

当 \(j<k\) 或 \(j>k\) 时，显然次数为0。

当 \(j=k\) 时，次数就是 \(10^{i-1}\)，就像是 \([10,19]\) 中 \(1\) 出现 \(10\) 次，也就是 \(10^{2-1}\) 次。

也就是 \(f[i][j][j]+=10^{i-1}\) 。

拆数部分：

大概分为 \(4\) 步：

1.把原数进行拆分，存入数组。
2.统计位数比原数小的数字。
3.统计位数和原数相同，但最高位比原数小的数字。
4.统计一般情况下的数字。当当前位是需要统计的数字时，结果要加 \(10^{i-1}\) 。

CODE

这里我们有运用到前缀和的思想，也就是说，统计答案时，是输出 \([R+1,i]-[l,i]\) 。

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<cmath>
#define R register
#define int long long

using namespace std;

typedef unsigned long long ull;

#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read() {
    R char c=getchar();R int x=0;R bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c&15);
    return f?(~x+1):x;
}

inline int ksm(int base,int power) 
{
    int result=1;
    while(power) 
    {
        if(power&1) 
            result=result*base;
        power>>=1;
        base=base*base;
    }
    return result;
}

const int N=15;

int f[N][10][10];
//f[i][j][k]表示第i位，最高位为j，k的个数

inline void dp() {
	for(int i=0;i<=9;i++) {
		f[1][i][i]=1;//数字为1位数时每个数字出现的次数都是1
	}
	for(int pos=2;pos<=13;pos++) {//位数
		for(int j=0;j<=9;j++) {//当前位
			for(int k=0;k<=9;k++) {//上一位
				for(int num=0;num<=9;num++) {//要统计的数字
					f[pos][j][num]+=f[pos-1][k][num];
				}
			}
			f[pos][j][j]+=ksm(10,pos-1);
		}
	}
}

inline int slove(int x,int num) {
	//求0到x中num出现的次数
	int dig[N];
	memset(dig,0,sizeof(dig));
	int len=0;//数的长度
	int cnt=0;//
	while(x) {//分离数字
		dig[++len]=x%10;
		x/=10;
	}
	//----------------------------------
	for(int pos=1;pos<len;pos++) {//位数
		for(int j=1;j<=9;j++) {
			cnt+=f[pos][j][num];
		}
	}
	//统计位数比x小的数字
	//----------------------------------
	
	
	//----------------------------------
	for(int i=1;i<dig[len];i++) {
		cnt+=f[len][i][num];
	}
	//统计数位和x相同，但是最高位比x小的数字
	//----------------------------------
	
	
	//----------------------------------
	for(int pos=len-1;pos>=1;pos--) {
		for(int j=0;j<dig[pos];j++) {
			cnt+=f[pos][j][num];
		}
		for(int j=len;j>pos;j--) {
			if(dig[j]==num) {
				cnt+=dig[pos]*ksm(10,pos-1);
			} 
		}
	}
	//统计一般的情况
	//----------------------------------
	
	return cnt;
}

signed main() {
	int l=read(),r=read();
	dp();
	for(int i=0;i<=9;i++) {
		printf("%lld ",slove(r+1,i)-slove(l,i));
	}
	return 0;
}

这篇关于数位dpの学习笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！