武理校赛I题 A New Good Number（数位dp，记忆化dfs）

数位dp，记忆化dfs）"/>

武理校赛I题 A New Good Number（数位dp，记忆化dfs）

武理校赛I题

A New Good Number（数位dp，记忆化dfs）

牛客链接

题意：

计算 l - r 内的满足相邻位数字都是倍数的合法数字有多少种

思路：

基础数位dp， 建立二维数组 dp[pos][pre]，表示前一位为 pre ，后面跟着 pos 长度的数字时，满足题意的数字有几个。

实现细节：

计算 l - r 内所有符合条件的数字其实就是计算 0 - r 内所有合法数字和 0 - （l - 1）内所有合法数字，取其差值。

函数 dfs(pos, pre, limit) ：
pos 表示算上当前位，后面还有几位数字；
pre 表示前一位数字的值；
limit 用来表示当前位数字是否达到最大值（如果未达到代表着这一位之后的数字可以任意取(0 - 999…) ，如果达到意味着之后的数字不一定能任取）；

memset(dp, -1, sizeof(dp)); //初始化
ll dfs(int pos, int pre, bool limit)
{ll ans = 0;if (pos == 0) return 1;//如果算上这一位的总数字位数为0，即搜到一个合法答案if (!limit && dp[pos][pre] != -1) return dp[pos][pre];//如果未达到上限且之前已经搜索过（记忆化dfs），直接返回答案int up;//当前这一位数字上限if (limit) up = f[pos];//f[]数组储存数字每一位的值else up = 9;for (int i = 0;i <= up;i++){if (i == 0 || pre == 0 || i % pre == 0 || pre % i == 0)//如果合法ans += dfs(pos - 1, i, limit && (i == f[pos]));}if (!limit) dp[pos][pre] = ans;//如果此时不是上限，说明此答案可以反复使用，那么就用dp数组记录return ans;
}

完整代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef double dd;
typedef pair<int, int> pii;
typedef pair<dd, dd> pdd;
const int MAXN = 100005;
const int inf = 1e9 + 7;ll l, r, dp[30][30];
ll f[30];ll dfs(int pos, int pre, bool limit)
{ll ans = 0;if (pos == 0) return 1;if (!limit && dp[pos][pre] != -1) return dp[pos][pre];int up;if (limit) up = f[pos];else up = 9;for (int i = 0;i <= up;i++){if (i == 0 || pre == 0 || i % pre == 0 || pre % i == 0)ans += dfs(pos - 1, i, limit && (i == f[pos]));}if (!limit) dp[pos][pre] = ans;return ans;
}ll solve(ll x)
{int cnt = 0;if (x == 0) return 1; //如果数字是0，那么不会进入while循环，因此特判while (x){f[++cnt] = x % 10;x /= 10;}return dfs(cnt, 0, 1);
}int main()
{int t;scanf("%d", &t);memset(dp, -1, sizeof(dp));memset(f, 0, sizeof(f));while (t--){scanf("%lld%lld", &l, &r);if (l == 0)printf("%lld\n", solve(r));elseprintf("%lld\n", solve(r) - solve(l - 1));}
}

总结：

之前数位dp除了看过一道例题之外没有自己上手做过，导致比赛时看出来了是一道数位dp题却不知道如何下手，赛后即便看了很多人的代码和题解，写起来依旧wa了好多次，日后需加强此方面练习。