A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string “13” and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n. Input Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000). Output Print each answer in a single line. Sample Input 13 100 200 1000 Sample Output 1 1 2 2 数位dp题目做了几道后发现有点套路了 数位dp可以解决一些让你找特定范围内满足条件的数字有多少，很难受的是条件很简单，但范围太大，那从数入手不行，从位入呢，1e9不过也就十位数，基本上数位dp（至少我遇到的几道）的最基本思想是记忆化搜索，记忆什么呢，不同题目条件不同，但都是从一点出发，就是如果前面位数没达到最大范围，那么后面位数的可能情况都是相同的，举个例子求范围33333内满足条件的数：那么如果第一位的数是0，后面的可能情况就是个位数，十位数，百位数，千位数的可能情况都是0-9；当第一位是1时，后面的可能情况也同样。为什么是从零开始呢，因为要从1到33333，第一为0，就相当于考虑四位数的情况了
那么有了基本思想后，记忆化搜索具体记忆什么呢，首先前面的位数肯定是未达到最大范围，记忆才有意义（因为你如果达到了，后面的可能性要考虑很多，记忆就失去了意义），第一个记忆是记忆当前位数是第几位（因为相同位数后面才会有相同可能）
所有都需要记录的是当前是第几位，当前位数是否达到上限 具体分析该题： 所求的数是要满足存在“13”，且是13的倍数，自然而然，我们要记录前面是否出现过“13”，如果没出现呢，下一位是不是出现“13”还会受到上一位数是不是1和这一位是不是3，所以还要记录上一位是不是“1”，那现在还差是不是13的倍数，这里用到 如145=（）（（（1）*10+4））*10+5）； 这如果在同样的位数余数相同，则后面满足13倍数的数的个数是相同的；
详见代码
#include<bits/stdc++.h> using namespace std; int dp[12][3][13]; int temp[20]; int sum; int dfs(int pos,bool limlt,int st,int sr ) { //cout<<sr<<endl; //cout<<pos<<" "<<sr<<" "<<st<<endl; if(pos==-1&&sr==2&&st==0) { //cout<<"1"<<endl; return 1; } else if(pos==-1)return 0; if(!limlt&&dp[pos][sr][st])//基本模板，dp具体看题目，pos表示当前位数，sr表示当前位是否为1，st表示到当前位模13等于多少 return dp[pos][sr][st]; int maxx=(limlt?temp[pos+1]:9);//基本模板 //cout<<maxx<<endl; int ant=0; for(int i=0;i<=maxx;i++) { int nxtst=(st*10+i)%13;//这里就相当于我举的145例子，把一个数拆成位数来模。 bool nxtli=(limlt&&(i==maxx)); if(sr==0) ant+=dfs(pos-1,nxtli,nxtst,(i==1)); else if(sr==1) ant+=dfs(pos-1,nxtli,nxtst,(i==3)?2:(i==1)); else ant+=dfs(pos-1,nxtli,nxtst,2); } if(!limlt) return dp[pos][sr][st]=ant; else return ant; } int solve (int x) { int k=0; while(x) { temp[++k]=x%10; x/=10; } return dfs(k-1,true,0,0); } int main() { int x,y; while(~scanf("%d",&y)) cout<<solve(y)<<endl; }在这里插入代码片