前言
假期最后两天不想做什么太难的，就把数位DP开了吧！正好填之前挖的坑
数位DP看起来貌似都比较裸...而且题目简短，注意一下代码的细节就好
本篇记录里全部使用记忆化搜索
目录
-
A. 【例题1】B数计数
-
B. 【例题2】区间圆数
-
C. 【例题3】数字计数
-
D. 【例题4】数字整除
-
F. 1.幸运数字
题解
A. 【例题1】B数计数
分析：
此题是第一道ybt的数位dp题，引入一些模板的写法
对于所有求1~n，L~R的 xx数 个数的，一般都是从高位到低位搜索，而且记录一个 ok 变量来表示当前数位可不可以随便填数字（每一位数字填完最后不能比 n 大）
由于ok 变量不需要在 dp 数组里记录，可以直接传参到记忆化搜索里，但是ok==0和ok==1时候 dp 数组的记忆化值是不一样的，所以规定只记忆化ok==1（即可以随便填）时的 dp 值，这是因为ok==0的情况很少，所以不用记忆化问题也不大（ps：测试时发现枚举 i 的时候倒序枚举也可以使记忆化不重复，但是过于玄学我就不提了）
实际上，应该也可以在 dp 数组中记录 ok ，理论上空间会变大一倍（ok取值0，1），但是搜索部分会快一点点
那么回归本题，设计dp状态为 dp[pos][res][op]
pos表示第几位，res表示余数，op表示13数出现的状态（op==0没出现过，op==1上一位是1而且之前没出现过完整的13，op==2表示出现过13），maxn表示当前最大能填的数字，ok表示当前这位是否可以随便填
(一开始我想用check表示是否出现过13,其实不需要，可以用op代替)
代码：
A. 【例题1】B数计数
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
int n,dp[11][14][3],dig[11],m,mi[11];
void init()
{
//memset(dp,-1,sizeof(dp));
//memset(dig,0,sizeof(dig));
m=0;
while(n)
{
int x=n%10;
dig[++m]=x;
n/=10;
}
}
//可以有前导零，不用记录zero
//pos表示第几位，res表示余数，op表示13数出现的状态，maxn表示当前最大能填的数字
//(一开始我想用check表示是否出现过13,其实不需要，可以用op代替)
//ok表示当前这位是否可以随便填
int solve(int pos,int res,int op,bool ok)
{
if(pos==0) return dp[pos][res][op]=(op==2&&res==0);
if(dp[pos][res][op]!=-1&&ok) return dp[pos][res][op];
int ret=0,maxn=9;
if(!ok) maxn=dig[pos];
for(int i=maxn;i>=0;i--)
{
int tmp=(res+mi[pos]*i)%13;
//分类讨论当前填的数字大小
if(i<maxn)
{
//if(check) ret+=solve(pos-1,tmp,op,1,1);
if(op==2) {ret+=solve(pos-1,tmp,2,1);continue;}
if(i==1) ret+=solve(pos-1,tmp,1,1);
else if(i==3&&op==1) ret+=solve(pos-1,tmp,2,1);
else ret+=solve(pos-1,tmp,0,1);
}
else
{
if(op==2) {ret+=solve(pos-1,tmp,2,ok);continue;}
if(i==1) ret+=solve(pos-1,tmp,1,ok);
else if(i==3&&op==1) ret+=solve(pos-1,tmp,2,ok);
else ret+=solve(pos-1,tmp,0,ok);
}
}
// printf("dp[%d][%d][%d]=%d\n",pos,res,op,ret);
if(ok) dp[pos][res][op]=ret;
return ret;
}
int main()
{
mi[1]=1;
for(int i=2;i<=10;i++) mi[i]=mi[i-1]*10;
while(scanf("%d",&n)!=EOF)
{
init();
printf("%d\n",solve(m,0,0,0));
}
return 0;
}
/*
input:
131312
131313
13333
13332
13338
output:
550
551
60
60
61
*/
B. 【例题2】区间圆数
分析：