【笔记】数位DP

数位DP

T1——数数问题

问题：求l ~ r 之间有几个数（没错就是数数）

我们先求0_{r有几个数，再求0}l-1有几个数，所以我们构造一个函数get_num（X）,来求0~X有几个数

我们把X按照10进制一位一位拆开，放到x[]数组里(假设共有k位)，下标从大到小，表示从高位到低位

在搞一个数组y[],也表示一个数Y,这个Y就是0~X的一个数，满足小于等于X

DP状态：f[i][j=0/1]，其中i表示从高到低填到第i位，j表示这一位y[i]与x[i]是否相等，0表示y[k_{i]所表示的数小于x[k}i],1表示y[k~i] = x[k~i]（没有大于，因为这个Y要满足小于等于X），f表示满足这个条件的数的个数

初始化：f[k+1][1] = 1;//x[k+1] = y[k+1] = 0

代码如下：

int f[30][2], x[30]; 
void get_num(int X){
	int k = 1;
	while(X){
		x[k] = X%10;
		X /= 10;
		k++;
	}
	f[k+1][1] = 1;
	for(k+1;k>=2;k--){
		for(int i = 0; i <= 9; i++){
			if(i > x[k-1])	break;//大于的话就不要继续了， 
			f[k-1][0] += f[k][0];//目前小于可以转移到下一位也小于 
			if(i == x[k-1])	f[k-1][1] += f[k][1];//目前等于，可以转移到下一位也等于
			else	f[k-1][0] += f[k][1];	//目前等于，可以转移到下一位小于
		}
	}
	int res = f[1][0] + f[1][1];
	return res; 
}

简单总结

如上就是数位DP了。

一般框架：l~r之间满足条件的数的个数，一般是先做一个类似前缀的东西，然后减出答案

统一状态设计：i表示从高到低填到第i位, j=0/1表示当前我已经填的这些位是小于x还是等于x

然后按位转移

T2 P2602 [ZJOI2010]数字计数

T3

题目描述

a(x)表示x各个数位上的数之和
求a(1)+a(2)+...+a(n-1)
n≤1,000,000,000

解

g[i] 表示所有i位数的数位之和

f[i] 表示0到(10 ^ i - 1)所有数的数位之和

code

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;

int n;
ll g[10], f[10], ans;

int main()
{
	g[0] = 1;
	f[0] = 1;
	g[1] = 45;
	f[1] = 45;
	for(int i = 2; i <= 9; i++){
		g[i] = g[i - 1] * 9 + pow(10, i - 1) * 45;
		f[i] = f[i - 1] + g[i];
	}
	scanf("%d", &n);
	int n0 = n, bits = 0, sum, pw;
	while(n0){
		bits++;
		n0 /= 10;
	}
	pw = pow(10, bits - 1);
	while(n){
		sum = n / pw;
		sum = (sum + 1) * sum / 2;
		ans += sum * f[bits - 1];
		n %= pw;
		bits --;
		pw /= 10;
	}
	printf("%lld
", ans);
	return 0;
}

T4 数位之和

题目描述

求0~n中有多少个数满足：各个数位上的数之和是m。
n≤10^9

T5 CF55D Beautiful numbers

题目描述

Volodya是一个很皮的男♂孩。他认为一个能被它自己的每一位数上的数整除的数是很妙的。我们先忽略他的想法的正确性（如需证明请百度“神奇海螺”），只回答在l到r之间有多少个很妙的数字。

输入输出格式

输入：总共有t个询问：

第一行：t；

接下来t行：每行两个数l和r。

注意：请勿使用%lld读写长整型（虽然我也不知道为什么），请优先使用cin（或者是%I64d）。

输出：t行，每行为一个询问的答案。

输入输出样例

输入 #1

1
1 9

输出 #1

输入 #2

1
12 15

输出 #2