数位DP
综述
数位DP的应用范围：
- 在某个区间内
- 有多少个
- 满足一定的性质
数位DP中使用的方法：
- 类似于前缀和。A到B相当于
f[B] - a[A-1]
这一点尤为重要，因为已经弱化了边界，使得考虑的更少 - 分情况讨论
1081. 度的数量
输入样例：
15 20
2
2
输出样例：
3
/*
这一道题目中的数字如果在分解之后出现某一位上的数字不是0或1，那么已订购不符合情况（K
个互不相等）
*/
#include <bits/stdc++.h>
using namespace std;
int X, Y, K, B;
#define N 35
int f[N][N];// 组合数
void init()
{
for(int i = 0; i < N; i++)
{
for(int j = 0; j <= i; j++){
if(!j) f[i][j] = 1;
else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}
}
}
int dp(int n)
{
if(!n) return 0;// 特判必不可少，虽然这里没什么用
vector <int> nums;
while(n)nums.push_back(n%B), n /= B;// 把n拆分
int last = 0, res = 0;// res为返回值，last为走右子树已经囤积了多少个1
for(int i = nums.size() - 1; i >= 0; i--)
{
int x = nums[i];
if(x == 1)// 左右都可以
{
if(K - last >= 0)
res += f[i][K - last];
last ++;
if(last > K) break;
}
else if(x > 1)// 左面就行了。要是走右面，就不满足（K个互不相等）
{
if(K - last >= 0)
res += f[i][K - last];
if(K - last - 1 >= 0) res += f[i][K - last - 1];
break;
}
if(!i && last == K) res ++;// 不要忘了这个
}
return res;
}
int main()
{
scanf("%d%d%d%d", &X, &Y, &K, &B);
init();
cout << dp(Y) - dp(X - 1);
return 0;
}
1082. 数字游戏
科协里最近很流行数字游戏。
某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 123，446。
现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。
输入格式
输入包含多组测试数据。
每组数据占一行，包含两个整数 a 和 b。
输出格式
每行给出一组测试数据的答案，即 [a,b] 之间有多少不降数。
数据范围
1≤a≤b≤\(2^{31} - 1\)
输入样例：
1 9
1 19
输出样例：
9
18
#include <bits/stdc++.h>
using namespace std;
#define N 15
int f[N][N];// f[i][j]状态：最高位是j，共i位的所有数字的个数
void init()
{
for(int i = 0; i <= 9; i++) f[1][i] = 1;//只有一位数，最高位为i的方案数是1
for(int i = 2; i < N; i++){
for(int j = 0; j <=9; j++){
for(int k = j; k <= 9; k++){
f[i][j] += f[i-1][k];
}
}
}
}
int dp(int n)
{
if(!n) return 1;// 由于n == 0的时候，nums.size()为0，不会进入下面的循环，所以特判
vector<int> nums;
while(n) nums.push_back(n%10) , n /= 10;
int res = 0;
int last = 0;
for(int i = nums.size() - 1; i >= 0; i--)
{
int x = nums[i];
for(int j = last; j < x; j++) res += f[i+1][j];// 左边情况
// 右边
if(x < last) break;// 如果没有break，那么自动进入右边
last = x;// 别忘了维护last
if(!i) res++;// 如果安全地没有被break掉，那么就是合法的
}
return res;
}
int main()
{
init();
int A, B;
while(cin >> A >> B)
{
cout << dp(B) - dp(A-1) << "\n";
}
return 0;
}
1083. Windy数
Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 22 的正整数被称为 Windy 数。
Windy 想知道，在 A 和 B 之间，包括 A 和 B，总共有多少个 Windy 数？
输入格式
共一行，包含两个整数 A 和 B。
输出格式
输出一个整数，表示答案。
数据范围
1≤A≤B≤ 2e9
输入样例1：
1 10
输出样例1：
9
输入样例2：
25 50
输出样例2：
20
题解
这一道题目与上一道题目有些许的差别。
数位DP中貌似默认是包含前导0的。但是这道题目并不包含，需要特判
000456在包含前导0的情况下明显不满足！
其实包含前导0也没有什么大不了的，因为当首位取0的时候，后面全部是任意取，所以可以直接枚举一下。
#include <bits/stdc++.h>
using namespace std;
#define N 13
int f[N][N];
void init()// 注意：f[i][j]中，对于j!=0的情况，就是不考虑前导0的情况。
// 事实上，j == 0 并不合法，这一种状态仅仅是为了递推而需要计算的
// 下面需要用到j == 0时，也是前面有非0数字才可以带入计算
{
for(int i = 0; i <= 9; i++) f[1][i] = 1;// 注意：在数位DP的时候是包含前导0的
for(int i = 2; i < N; i++){
for(int j = 0; j <= 9; j++){
for(int k = 0; k <= 9; k++){
if(abs(k - j) >= 2) f[i][j] += f[i - 1][k];
}
}
}
}
int dp(int n)
{
if(!n) return 0;// 返回1或者是返回0都一样，因为作差之后就一毛一样了
vector<int> nums;
while(n) nums.push_back(n%10), n /= 10;
int last = -2;// 让最高位什么都可以取
int ans = 0;
for(int i = nums.size() - 1; i >= 0; i--)
{
int x = nums[i];
// 对于分支：
// 左边（最高位不是0）
for(int j = (i == nums.size() - 1); j < x; j++){
if(abs(last - j) >= 2)ans += f[i + 1][j];// 注意判断是否合理
}
// 走右面
if(abs(x - last) < 2) break;// 不合理，则退出
last = x;// 维护last
if(!i) ans ++;
}
for(int i = 1; i < nums.size(); i++){// 最高位是0的情况
for(int j = 1; j <= 9; j ++){
ans += f[i][j];
}
}
return ans;
}
int main()
{
init();
int A, B;
cin >> A >> B;
cout << dp(B) - dp(A - 1);
return 0;
}
1084. 数字游戏 II
由于科协里最近真的很流行数字游戏。
某人又命名了一种取模数，这种数字必须满足各位数字之和 \(mod \space n\) 为 0。
现在大家又要玩游戏了，指定一个整数闭区间 [a.b]，问这个区间内有多少个取模数。
输入格式
输入包含多组测试数据，每组数据占一行。
每组数据包含三个整数 a,b,N
输出格式
对于每个测试数据输出一行结果，表示区间内各位数字和 \(mod \space n\) 为 0 的数的个数。
数据范围
1≤a,b≤\(2^{31} - 1\)
1≤N<100
输入样例：
1 19 9
输出样例：
2
在 y 总的代码中，定义了三维状态，但是感觉也可以使用两维
我的f[i][j]表示有 i 位数字，并且这i位数字之和mod p 为 j 的所有数字
#include <bits/stdc++.h>
using namespace std;
int p;// 表示题目中的 N
int f[15][105];
inline int mod(int x){// 正数与%相同，负数会转化为正数
return (x % p + p) % p;
}
void init()
{
for(int i = 0; i < 15; i++){// 有多组测试数据
for(int j = 0; j < p; j++)
f[i][j] = 0;
}
f[0][0] = 1;// 0位数字，和为0的情况为起始情况
for(int i = 1; i < 15; i++)
{
for(int j = 0; j <= 9; j++){// 最高位的取值
for(int k = 0; k < p; k++){// 枚举第二维状态
int o = mod(k - j);
f[i][k] += f[i - 1][o];
}
}
}
}
int dp(int n)
{
if(!n) return 1;
int last = 0;// 前面的和mod p
int ans = 0;
vector<int> nums;
while(n) nums.push_back(n % 10), n /= 10;
for(int i = nums.size() - 1; i >= 0; i--){
int x = nums[i];
for(int j = 0; j < x; j++){
ans += f[i][mod(0 - j - last)];
}
last = (last + x) % p;
if(!n && last%p == 0) ans ++;
}
return ans;
}
int main()
{
int a, b;
while(cin >> a >> b >> p){
init();
cout << dp(b) - dp(a - 1) << "\n";
}
return 0;
}
1085. 不要62
杭州人称那些傻乎乎粘嗒嗒的人为 62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有 4 或 62 的号码。例如：62315,73418,88914 都属于不吉利号码。但是，61152 虽然含有 6 和 2，但不是 连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照号区间 [n,m]，推断出交管局今后又要实际上给多少辆新的士车上牌照了。
输入格式
输入包含多组测试数据，每组数据占一行。
每组数据包含一个整数对 n 和 m。
当输入一行为“0 0”时，表示输入结束。
输出格式
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
数据范围
1≤n≤m≤1e9
输入样例：
1 100
0 0
输出样例：
80
题解
这一道题目如果做拓展，就类似于设计密码
但是在这里，简单进行判断就可以了
#include <bits/stdc++.h>
using namespace std;
int f[35][10];
void init()
{
for(int i = 0; i <= 9; i++){
if(i == 4) continue;
f[1][i] = 1;
}
for(int i = 2; i < 15; i++)
{
for(int j = 0; j <= 9; j++){
if(j == 4) continue;
for(int k = 0; k <= 9; k++){
if(k == 4) continue;
if(j == 6 && k == 2) continue;
f[i][j] += f[i - 1][k];
}
}
}
}
int dp(int n)
{
if(!n) return 1;
vector<int> nums;
while(n) nums.push_back(n % 10), n /= 10;
int ans = 0;
int last = 0;
for(int i = nums.size() - 1; i >= 0; i--)
{
int x = nums[i];
for(int j = 0; j < x; j++){
if(j == 4 || (j == 2 && last == 6)) continue;//j == 2 && last == 6不要忘记
ans += f[i + 1][j];
}
if(x == 4 || (x == 2 && last == 6)) break;
last = x;// 修改last需要在判断之后
if(!i) ans ++;
}
return ans;
}
int main()
{
init();
int n, m;
while(scanf("%d%d", &n, &m), n || m){
printf("%d\n", dp(m) - dp(n - 1));
}
// cout << dp(1);
return 0;
}