数位DP
数位dp的题目一般会问,某个区间内,满足某种性质的数的个数。
对应的数位dp问题有相应的解题技巧:
- 利用前缀和求某个区间内满足条件的数的个数
- 利用树的结构来考虑(按位分类讨论)
度的数量
原题链接
思路
通过前缀和思想计算出从 0 ~ n的所有方案数,给定区间做差即可
将n分解为B进制数,从高位开始依次考虑每个数。
按照树形结构划分n,左分支为 0~a-1, 右分支为 a
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 40;
int K, B;
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) { // 从 0 ~ n 符合条件的数的个数
if (!n) return 0;
vector<int>nums;
while(n) {
nums.push_back(n % B);
n /= B;
}
// for (int i = 0; i < nums.size(); i ++) cout << nums[i] << ' ';
// puts("");
int res = 0, last = 0;
for (int i = nums.size()-1; i >= 0; i --) {
int x = nums[i]; // x = 0, x = 1, x > 1
// 对x分类讨论
// cout << "x : " << x << endl;
if (x) { // x != 0 即 x > 0
res += f[i][K-last]; // 该位填0, 剩下从i位中选择K-last个位置填1
// cout << res << endl;
// cout << i << ' ' << K-last << endl;
// cout << f[i][K-last] << endl;
if (x > 1) { // 该位可以填1
if (K - last - 1 >= 0)
res += f[i][K-last-1]; // 剩下从i位中选择K-last-1个位置填1
// 对于符合条件的已经处理完成,直接break
break;
} else {
// 对应 x == 1
last ++; // 该位置填 1
if (last > K) break;
}
}
// 最后一个分支,即最后一位,如果为1则已经被上方处理过,如果为0,则方案数加1
if (i == 0 && last == K) res ++;
}
return res;
}
inline int read(){
int num = 0;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == '-') flag = true;
else num = c - '0';
while (isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
int main() {
init();
int x = read(), y =read();
K = read(), B = read();
printf("%d\n", dp(y) - dp(x-1));
return 0;
}
数字游戏
原题链接
思路
状态表示
f[i][j] 表示共有i位,最高位为j的个数
状态计算
f[i][j] = f[i-1][k] (k = j, j+1, j+2, j+3, ... 9)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 40;
int f[N][N];
void init() {
for (int i = 0; i < 10; i ++) f[1][i] = 1;
for (int i = 2; i < N; i ++)
for (int j = 0; j <= 9; j ++)
for (int k = j; k < N; k ++)
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 res = 0, last = 0; // last表示上一位的数字
for (int i = nums.size() - 1; i >= 0; i --) {
int x = nums[i];
// 分支一:考虑从last~x-1
for (int j = last; j < x; j ++) {
res += f[i+1][j];
}
// 不满足条件后退出
if (x < last) break;
// 分支二:x分支
last = x;
if (!i) res ++;
}
return res;
}
int main() {
init();
int a, b;
while(cin >> a >> b) cout << dp(b) - dp(a - 1) << endl;
return 0;
}
Windy数
原题链接
思路
状态表示
f[i][j] 表示考虑前i位,最高位为j 的所有方案数量
状态计算
f[i][j] += f[i-1][k] (k = 0, 1, ..., 9)
abs(j-k) >= 2
前导0问题
枚举的第 i+1
位是最高位,不能填0。如果填0,那么答案就会加上f[i+1][0]
举这样一个例子,
对于数字13,是满足windy数定义的,那么加上前导0之后的 013
就不会被 f[3][0]
加进去,原因就是abs(0-1)<2,这样就导致答案漏掉
因此分两部分来计算答案
-
第一部分考虑长度与
n
等长的数for (int i = len-1; i >= 0; i --) { int x = nums[i]; for (int j = (i == len-1); j < x; j ++) { if (abs(last - j) >= 2) { res += f[i+1][j]; } } if (abs(last-x) < 2) break; else last = x; if (!i) res ++; }
-
第二部分考虑长度小于
n
的数for (int i = 1; i < len; i ++) for (int j = 1; j <= 9; j ++) res += f[i][j];
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int N = 11;
int f[N][N];
void init() {
for (int i = 0; i < 10; i ++) f[1][i] = 1;
for (int i = 2; i < N; i ++)
for (int j = 0; j < 10; j ++)
for (int k = 0; k < 10; k ++)
if (abs(j-k) >= 2) f[i][j] += f[i-1][k];
}
int dp(int n) {
if(!n) return 0;
vector<int> nums;
while(n) nums.push_back(n%10), n/=10;
int res = 0;
int last = -1000;
int len = nums.size();
for (int i = len-1; i >= 0; i --)
{
int x = nums[i];
for (int j = (i == len-1); j < x; j ++) {
if (abs(last - j) >= 2) {
res += f[i+1][j];
}
}
if (abs(last-x) < 2) break;
else last = x;
if (!i) res ++;
}
for (int i = 1; i < len; i ++)
for (int j = 1; j <= 9; j ++)
res += f[i][j];
return res;
}
int main() {
init();
int a, b;
cin >> a >> b;
cout << dp(b) - dp(a-1) << endl;
return 0;
}
数字游戏 II
原题链接
思路
状态转移
f[i][j][k] 表示考虑i位数,最高位为j,k所有位数之和模N后的余数 所有方案数
状态计算
f[i][j][k] += f[i-1][x][mod(k-j, P)] 前i-1位和模P的余数为mod(k-j, P)
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 40, M = 110;
int f[N][10][M];
int P;
int mod(int x, int y) {
return (x % y + y) % y; // 将得到的负余数转化为0~y-1之间
}
void init() {
memset(f, 0, sizeof f);
for (int i = 0; i < 10; i ++) f[1][i][i%P] = 1;
for (int i = 2; i < N; i ++) //位数
for (int j = 0; j < 10; j ++) // 最高位
for (int k = 0; k < P; k ++) // 所有位上的和
for (int x = 0; x < 10; x ++) // 下一位
f[i][j][k] += f[i-1][x][mod(k-j, P)];
}
int dp(int n) {
if (!n) return 1;
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 = 0; j < x; j ++)
res += f[i+1][j][mod(-last, P)]; // 前面位之和为 last, 后面数字的和加上last % N 应为0
last += x;
if (!i && last % P == 0) res ++;
}
return res;
}
int main() {
int a, b;
while(cin >> a >> b >> P) {
init();
cout << dp(b) - dp(a-1) << endl;
}
return 0;
}
不要62
原题链接
思路
状态表示
f[i][j] 表示考虑前i位, 最高位为j的方案数
状态转移
f[i][j] = f[i-1][k]
j != 6 && k != 2
j != 4
k != 4
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 11;
int f[N][10];
inline int read(){
int num = 0;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == '-') flag = true;
else num = c - '0';
while (isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
void init() {
for (int i = 0; i < 10; i ++)
if (i != 4) f[1][i] = 1;
for (int i = 2; i < N; i ++)
for (int j = 0; j < 10; j ++)
{
if (j == 4) continue;
for (int k = 0; k < 10; k ++)
if (k == 4 || j == 6 && k == 2) continue;
else 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 res = 0, 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 || last == 6 && j == 2) continue;
else res += f[i+1][j];
}
if (x == 4 || last == 6 && x == 2) break;
last = x;
if (!i) res ++;
}
return res;
}
int main() {
init();
int n, m;
while(n = read(), m = read(), n || m) {
printf("%d\n", dp(m) - dp(n-1));
}
return 0;
}