转载：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; }
原文：https://www.cnblogs.com/tonyyy/p/10679809.html