数位dp
转载：https://www.cnblogs.com/zbtrs/p/6106783.html
一.求a~b中不包含49的数的个数. 0 < a、b < 2*10^9
我们要求[a,b]不包含49的数的个数，可以想到利用前缀和来做，具体来说，就是[a,b] = [0,b] - [0,a),(")"是不包括a),我们先求出给定a,b的每个位置的数，保存在数组s中，例如a = 109,那么a[1] = 9,a[2] = 0,a[3] = 1.然后开始dp，我们可以选择记忆化搜索或者是递推，前一种相对于第二种而言简单和较为容易理解一些，所以我们选择记忆化搜索.那么需要记录些什么呢？首先长度是一定要记录的，然后记录当前的数位是否为4，这样就便于在记忆化搜索中得到答案.
然后进行记忆化搜索，记录上一位是否为4和枚举这一位，如果没有限制的话很好办，直接枚举就可以了，但是这样可能会超空间，因此我们每次都必须要判断是否有最大的限制
#include <bits/stdc++.h> using namespace std; int a,b; int shu[20],dp[20][2]; // if4是记录上一位是否为4 int dfs(int len,bool if4,bool shangxian) { if(len == 0) { return 1; } if( !shangxian && dp[len][if4] ){ return dp[len][if4]; } int cnt = 0,maxx = (shangxian ? shu[len]:9); for(int i=0;i<=maxx;i++) { if(if4 && i==9) continue; cnt += dfs(len-1, i==4 ,shangxian && i == maxx); } return shangxian ? cnt : dp[len][if4] = cnt; } int solve(int x) { memset(shu,0,sizeof(shu)); int k = 0; while(x) { shu[++k] = x%10; x /= 10; } return dfs( k , false , true ); } int main() { scanf("%d %d",&a,&b); cout<<solve(b) - solve(a-1)<<endl; return 0; }
二.求a~b中不包含62和4的数的个数. 0 < a、b < 2*10^9
分析：和上一题一样，只需要再判断一下4是否出现和上一位是否为6即可.
#include <bits/stdc++.h> using namespace std; int a,b; int shu[20],dp[20][2]; int dfs(int len,bool if6,bool shangxian) { if(len == 0) { return 1; } //shangxian == false && if( !shangxian && dp[len][if6] ){ return dp[len][if6]; } int cnt = 0,maxx = (shangxian ? shu[len]:9); for(int i=0;i<=maxx;i++) { if(i== 4|| (if6 && i==2)) continue; cnt += dfs(len-1, i==6 ,shangxian && i == maxx); } return shangxian ? cnt : dp[len][if6] = cnt; } int solve(int x) { memset(shu,0,sizeof(shu)); int k = 0; while(x) { shu[++k] = x%10; x /= 10; } return dfs( k , false , true ); } int main() { scanf("%d %d",&a,&b); cout<<solve(b) - solve(a-1)<<endl; return 0; } //shu 数组里存放的就是个int类型的数 小于二十位的一个超大的数
三.windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？
#include <bits/stdc++.h> using namespace std; int a,b,shu[20],dp[20][12]; int dfs(int len,int last,bool shangxian) { int p; if(len == 0){ return 1; } if(!shangxian && dp[len][last] != -1 && last >= 0){ return dp[len][last]; } int cnt = 0,maxx = (shangxian ? shu[len] : 9); for(int i=0;i<=maxx;i++) { if(abs(i - last) < 2) continue; p = i; if(i == 0 && last == -10) p = last; cnt += dfs( len - 1 , p , shangxian && (i == maxx) ); } if(last >= 0 && !shangxian) dp[len][last] = cnt; return cnt; } int solve(int x) { int k = 0; while(x) { shu[++k] = x%10; x /= 10; } memset(dp,255,sizeof(dp)); return dfs(k , -10 , true); } int main() { cin>>a>>b; cout<<solve(b) - solve(a-1)<<endl; return 0; }
四.找出1~n范围内含有13并且能被13整除的数字的个数.
分析：和例1相比多了一个整除，怎么处理呢？其实只需要在记忆化搜索中增加一个参数mod即可，利用(a * b) % mod = (a % mod) * (b % mod)和（a + b） % mod = （a % mod） + （b % mod）来计算.比如说73 % 10 = ((7 % 10) * 10 + 3) % 10,但要注意本题是要找含有13的数，那么在处理的时候就要进行分类讨论.
#include <bits/stdc++.h> using namespace std; int n; int shu[20],dp[20][20][2]; int dfs(int len,int mod,int zhuangtai,int shangxian) { if(len == 0) return mod==0&&zhuangtai == 2; if(!shangxian &&dp[len][mod][zhuangtai]) { return dp[len][mod][zhuangtai]; } int cnt = 0 ,maxx =(shangxian ? shu[len]:9); for(int i=0;i <= maxx;i++) { int tz = zhuangtai; if(zhuangtai != 2&&i != -1) tz = 0; if(zhuangtai == 1&& i == 3) tz = 2; if(i==1 && zhuangtai != 2) tz = 1; cnt += dfs(len - 1,(mod*10 +i)%13,tz,shangxian&&i == maxx); } if(!shangxian) dp[len][mod][shangxian] = cnt ; return cnt; } int main() { while(scanf("%d",&n)){ memset(shu,0,sizeof(shu)); memset(dp,0,sizeof(dp)); int k = 0; while(n) { shu[++k] = n%10; n/=10; } cout<<dfs(k,0,0,1)<<endl; } return 0; }
五.求区间[a,b]中的数转化为二进制后0比1多的数的个数.
分析：典型的数位dp题，先在二进制上做dp,最后转化到十进制上.求出[0,b]和[0,a-1]的答案，相减就可以了.
一个坑点：二进制数必须要存在，也就是说必须要有一个1开头.
#include <bits/stdc++.h> using namespace std; #define ll long long ll shu[100],a,b; ll dp[100][100][100]; ll dfs(ll len,ll num1,ll num0,bool shangxian,bool can) { if(len == 0) { if(num0 >= num1) return 1; return 0; } if(!shangxian && dp[len][num1][num0]) return dp[len][num1][num0]; ll cnt = 0, k = (shangxian ? shu[len]:1); for(int i=0;i<=k;i++) { if(i==0) { if(can) cnt += dfs(len - 1,num1,num0+1,(shangxian && i==k),can || i == 1); else cnt += dfs(len - 1,num1,num0 ,(shangxian && i==k),can || i == 1); } if(i==1) { cnt += dfs(len-1 , num1+1,num0,(shangxian && i==k),can ||i == 1); } } if(!shangxian) { return dp[len][num1][num0] = cnt; } else return cnt ; } ll solve(ll x) { memset(shu,0,sizeof(shu)); ll k = 0; while(x) { shu[++k] = x%2; x/=2; } return dfs(k,0,0,true,false); } int main() { cin>>a>>b; cout<<solve(b) - solve(a-1)<<endl; return 0; }
总结 数位dp模板
1.如果题目中出现求满足区间[l,r]的符合......性质的数的个数，考虑使用数位dp.
2.思考一下：如果我们只能从前往后一位位枚举当前的数位，要做出这道题，我们需要知道哪些量？利用这些来补充到dfs的调用参数中.
3.套用模板.
#include <bits/stdc++.h> using namespace std; #define ll long long ll dp[100][100][1010]; ll shu[100]; ll dfs(int len, , , bool shangxian) { if(len == 0) return ...; if(!shangxian && dp[len][ ][ ] ) return dp[len][ ][ ]; ll cnt = 0; int maxx = (shangxian ? shu[len] : 9); for(int i=0;i<=maxx ;i++) { ...; cnt += dfs(len - 1, , , shangxian && i==maxx) } if(!shangxian) dp[len][ ][ ] = cnt; return cnt; } ll solve(ll x) { int k = 0; while(x) { shu[++k] = x%10; x /= 10; } return dfs(k, , ,1); } int main() { memset(dp,0,sizeof(dp)); cin>>a>>b; cout<<solve(b) - solve(a-1)<<endl; return 0; }
蔚来一面218人在聊
查看7道真题和解析