一、常见题面
- 求两个数之间的满足特定条件的数的方案数（提高+/省选- 位数为\(10 ^ 6\)；省选/NOI- 位数为\(10 ^{18}\)or有一些奇奇怪怪的操作）
例子：
待完善
- 求两个数之间的满足特定条件的数并对数进行一定操作，得出答案
例子：
待完善
二、 算法详解
1. 本质
将数按位进行拆分，进行记忆化搜索/DP递推的算法
2. 算法来源
对于两个数（例子：12345、33345），后缀(345)相同，且后缀所处”环境“下，相同部分的方案数相同，为避免重复计算相同后缀的方案，故有数位DP
3. 适用范围
-
没有后效性
-
后缀相同的情况下，后缀所对应的方案数相同
-
数可拆分的性质
4.细节
所有的数位dp都非常的套路，一般的形式类似于\(dp[now][…][0/1]\)表示现在从高到低处理到了第\(now\)位，\(0/1\)表示是否顶上届，... 是每个题不同的状态设计
5. code
记忆化搜索：
int dfs(int now,……,bool low){
if(now <= 0) return ……;//当前的数位
if(~dp[now][……][low])return dp[now][……][low];//判断是否搜过
int res = 0,top = low ? 9 : num[now];//确定枚举上界
for(int i = 0; i <= top; ++i){
res += dfs(now-1,……,low || i != top);
}
return dp[now][……][low] = res;
}
int solve(ll x){
ll res = 0;
if(x < 1e10) return 0;
memset(dp,-1,sizeof(dp));
for(len = 0; x; x /= 10)num[++len] = x % 10;//对上界进行拆分
for(int i = 1; i <= num[len]; ++i)
res += dfs(len-1,……,i < num[len]);
return res;
}//预处理数组
递推：
//一开始dp初始化成0
//dp[1~n] 从高到低表示数
for(int now = 1; now <= n; ++cur){
for(int j...){
for(int lim = 0; lim < 2; ++lim){
int up = lim ? num[now] : 9;
for(int i = 0;i <= up; ++i)
dp[now + 1][...][lim & (i == up)] += dp[now][...][lim];
}
}
}
三、如何从切蓝题到切紫题
你需要这些工具：
- 矩阵加速递推：P2657 [SCOI2009] windy 数\(\Rightarrow\)[Sam数](P2106 Sam数)
- 将一个数进行拆分的能力：SDOI2010]代码拍卖会
- ……未完待续(因为本蒟蒻做的数位DP的紫题题不是很多，不能很好地概括，请原谅 (@^_^@))