1， HDU 2089 不要62 :http://acm.hdu.edu.cn/showproblem.php?pid=2089
题意：不能出现4，或者相邻的62，
dp[i][0],表示不存在不吉利数字
dp[i][1],表示不存在不吉利数字，且最高位为2
dp[i][2],表示存在不吉利数字
#include<iostream> #include<cstdio> #include<cstring>using namespace std;int dp[10][3];void Init(){ //预处理，算出所有可能memset(dp,0,sizeof(dp));dp[0][0]=1;for(int i=1;i<=8;i++){dp[i][0]=dp[i-1][0]*9-dp[i-1][1]; //在不含不吉利数62和4的首位分别补除了4的9个数字，减去在2前面补6的个数dp[i][1]=dp[i-1][0]; //在不含不吉利数在首位补2dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1]; //各种出现不吉利数的情况 } }int Solve(int x){int digit[15];int cnt=0,tmp=x;while(tmp){digit[++cnt]=tmp%10;tmp/=10;}digit[cnt+1]=0;int flag=0,ans=0;for(int i=cnt;i>0;i--){ans+=digit[i]*dp[i-1][2]; //由上位所有不吉利数推导if(flag) //之前出现不吉利的数字ans+=digit[i]*dp[i-1][0];else{if(digit[i]>4) //出现4ans+=dp[i-1][0];if(digit[i]>6) //出现6ans+=dp[i-1][1];if(digit[i+1]==6 && digit[i]>2) //出现62ans+=dp[i][1];}if(digit[i]==4 || (digit[i+1]==6 && digit[i]==2))flag=1;}return x-ans; //所有的数减去不吉利的数 }int main(){//freopen("input.txt","r",stdin);int a,b;Init();while(~scanf("%d%d",&a,&b)){if(a==0 && b==0)break;printf("%d\n",Solve(b+1)-Solve(a));}return 0; }
另附一种暴力预处理法：
string 类提供了 6 种查找函数,每种函数以不同形式的 find 命名。这些操作全都返回 string::size_type 类型的值，以下标形式标记查找匹配所发生的位置；或者返回一个名为 string::npos 的特殊值，说明查找没有匹配。string 类将 npos 定义为保证大于任何有效下标的值。
比如：
string str;
pos=str.find_first_of("h");
if(pos!=string::npos)
{..
....
} //npos是一个常数，用来表示不存在的位置，类型一般是std::container_type::size_type
//许多容器都提供这个东西。取值由实现决定，一般是-1，这样做，就不会存在移植的问题了。npos表示string的结束位子，
//是string::type_size 类型的，也就是find（）返回的类型。
#include<iostream> #include<cstdio> #include<cstring> #include<string>using namespace std;int n,m; int lucky[1000010];void Init(){char c[20];string str;for(int i=1;i<1000000;i++){sprintf(c,"%d",i);str=c;if(str.find("62")==string::npos && str.find("4")==string::npos)lucky[i]=1;elselucky[i]=0;} }int main(){//freopen("input.txt","r",stdin);int ans;Init();while(~scanf("%d%d",&n,&m)){if(n==0 && m==0)break;ans=0;for(int i=n;i<=m;i++)ans+=lucky[i];printf("%d\n",ans);}return 0; }
2， HDU 3555 Bomb：http://acm.hdu.edu.cn/showproblem.php?pid=3555
题意就是找0到n有多少个数中含有49。数据范围接近10^20
DP的状态是2维的dp[len][3]
dp[len][0] 代表长度为len不含49的方案数
dp[len][1] 代表长度为len不含49但是以9开头的数字的方案数
dp[len][2] 代表长度为len含有49的方案数
状态转移如下
dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1]; // not include 49 如果不含49且，在前面可以填上0-9 但是要减去dp[i-1][1] 因为4会和9构成49
dp[i][1] = dp[i-1][0]; // not include 49 but starts with 9 这个直接在不含49的数上填个9就行了
dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1]; // include 49 已经含有49的数可以填0-9，或者9开头的填4
接着就是从高位开始统计
在统计到某一位的时候，加上 dp[i-1][2] * digit[i] 是显然对的，因为这一位可以填 0 - (digit[i]-1)
若这一位之前挨着49，那么加上 dp[i-1][0] * digit[i] 也是显然对的。
若这一位之前没有挨着49，但是digit[i]比4大，那么当这一位填4的时候，就得加上dp[i-1][1]
#include<iostream> #include<cstdio> #include<cstring>using namespace std;long long n,dp[25][3];void Init(){memset(dp,0,sizeof(dp));dp[0][0]=1;for(int i=1;i<=20;i++){dp[i][0]=dp[i-1][0]*10-dp[i-1][1];dp[i][1]=dp[i-1][0];dp[i][2]=dp[i-1][2]*10+dp[i-1][1];} }long long Solve(long long x){int digit[25];int cnt=0;while(x){digit[++cnt]=x%10;x/=10;}digit[cnt+1]=0;int flag=0;long long ans=0;for(int i=cnt;i>0;i--){ans+=digit[i]*dp[i-1][2];if(flag)ans+=digit[i]*dp[i-1][0];else{if(digit[i]>4)ans+=dp[i-1][1];}if(digit[i+1]==4 && digit[i]==9)flag=1;}return ans; }int main(){//freopen("input.txt","r",stdin);int t;scanf("%d",&t);Init();while(t--){scanf("%I64d",&n);printf("%I64d\n",Solve(n+1)); //因为包含n，所以n需要+1 }return 0; }
DFS:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm>using namespace std;long long n,dp[25][3]; int digit[25];long long DFS(int pos,int status,int limit){if(pos==-1) // 如果到了已经枚举了最后一位，并且在枚举的过程中有49序列出现 return status==2;if(!limit && dp[pos][status]!=-1) // 对于有限制的询问我们是不能够记忆化的 return dp[pos][status];long long ans=0;int s,end=limit?digit[pos]:9; // 确定这一位的上限是多少for(int i=0;i<=end;i++){ // 每一位有这么多的选择 s=status; // 有点else s = statu 的意思 if(status==1 && i==9)s=2;if(status==0 && i==4)s=1;if(status==1 && i!=4 && i!=9)s=0;ans+=DFS(pos-1,s,limit && i==end);}if(!limit)dp[pos][status]=ans;return ans; }long long Cal(long long x){int cnt=-1;while(x){digit[++cnt]=x%10;x/=10;}return DFS(cnt,0,1); }int main(){//freopen("input.txt","r",stdin);int t;scanf("%d",&t);while(t--){memset(dp,-1,sizeof(dp));scanf("%I64d",&n);printf("%I64d\n",Cal(n));}return 0; }
3, UESTC 1307 windy数 : http://acm.uestc.edu.cn/problem.php?pid=1307
要求相邻的数差大于等于2
#include<iostream> #include<cstdio> #include<cstring>using namespace std;int dp[20][10]; //dp[i][j]表示考虑i位的数中，最高为j的windy数int abs(int x){return x<0?-x:x; }void Init(){memset(dp,0,sizeof(dp));for(int i=0;i<=9;i++)dp[1][i]=1;for(int i=2;i<=10;i++)for(int j=0;j<10;j++)for(int k=0;k<10;k++)if(abs(j-k)>=2)dp[i][j]+=dp[i-1][k]; }int Solve(int x){int digit[20],cnt=0;while(x){digit[++cnt]=x%10;x/=10;}digit[cnt+1]=0;int ans=0;for(int i=1;i<cnt;i++) //先把长度为1至cnt-1计入 for(int j=1;j<10;j++)ans+=dp[i][j];for(int j=1;j<digit[cnt];j++) //确定最高位 ans+=dp[cnt][j];for(int i=cnt-1;i>0;i--){for(int j=0;j<digit[i];j++)if(abs(j-digit[i+1])>=2)ans+=dp[i][j];if(abs(digit[i]-digit[i+1])<2) //如果高位已经出现非法，直接退出 break;}return ans; }int main(){//freopen("input.txt","r",stdin);int a,b;Init();while(~scanf("%d%d",&a,&b)){printf("%d\n",Solve(b+1)-Solve(a));}return 0; }
4, HDU 3652 B-number :http://acm.hdu.edu.cn/showproblem.php?pid=3652
题意：求小于n是13的倍数且含有'13'的数的个数
dp[i][j][k]
i：第i位，j：余数为j
k=0：不含13 1：3开头不含13 2：含13
#include<iostream> #include<cstdio> #include<cstring>using namespace std;const int N=12; int md[N],dp[N][13][3];void Init(){md[0]=1;for(int i=1;i<N;i++)md[i]=md[i-1]*10%13;memset(dp,0,sizeof(dp));dp[0][0][0]=1;for(int i=0;i<N-1;i++)for(int j=0;j<13;j++){for(int k=0;k<10;k++)dp[i+1][(j+md[i]*k)%13][0]+=dp[i][j][0];dp[i+1][(j+md[i])%13][0]-=dp[i][j][1];dp[i+1][(j+md[i]*3)%13][1]+=dp[i][j][0];dp[i+1][(j+md[i])%13][2]+=dp[i][j][1];for(int k=0;k<10;k++)dp[i+1][(j+md[i]*k)%13][2]+=dp[i][j][2];} }int Solve(int x){int digit[15],len=0;while(x){digit[len++]=x%10;x/=10;}digit[len]=0;int flag=0,ans=0,mod=0;for(int i=len-1;i>=0;mod=(mod+digit[i]*md[i])%13,i--){for(int j=0;j<digit[i];j++)ans+=dp[i][(13-(mod+j*md[i])%13)%13][2];if(flag){for(int j=0;j<digit[i];j++)ans+=dp[i][(13-(mod+j*md[i])%13)%13][0];}else{if(digit[i+1]==1 && digit[i]>3)ans+=dp[i+1][(13-mod)%13][1];if(digit[i]>1)ans+=dp[i][(13-(mod+md[i])%13)%13][1];}if(digit[i+1]==1 && digit[i]==3)flag=1;}return ans; }int main(){//freopen("input.txt","r",stdin); Init();int n;while(~scanf("%d",&n)){printf("%d\n",Solve(n+1));}return 0; }
另附DFS：
#include<iostream> #include<cstdio> #include<cstring>using namespace std;int dp[20][13][3]; int n,digit[20];int DFS(int pos,int mod,int status,int limit){ //limit 有上限为1 无上限为0 if(pos<=0)return status==2 && mod==0;if(!limit && dp[pos][mod][status]!=-1) //当前状态访问过，没有上限return dp[pos][mod][status];int end=limit?digit[pos]:9;int ans=0;for(int i=0;i<=end;i++){int nmod=(mod*10+i)%13;int nstatus=status;if(status==0 && i==1) //高位不含13，并且末尾不是1 ，现在末尾添1nstatus=1;if(status==1 && i!=1) //高位不含13，且末位是1，现在末尾添加的不是1返回0状态nstatus=0;if(status==1 && i==3) //高位不含13，且末尾是1，现在末尾添加3返回2状态nstatus=2;ans+=DFS(pos-1,nmod,nstatus,limit && i==end);}if(!limit)dp[pos][mod][status]=ans;return ans; }int main(){//freopen("input.txt","r",stdin); memset(dp,-1,sizeof(dp));while(~scanf("%d",&n)){int len=0;while(n){digit[++len]=n%10;n/=10;}digit[len+1]=0;printf("%d\n",DFS(len,0,0,1));}return 0; }
5，HDU 3943 K-th Nya Number :http://acm.hdu.edu.cn/showproblem.php?pid=3943
用X个4和Y个7的数为规定的数，然后就是区间统计。
先预处理好dp[i][j][k]表示I位的数中有j个4和k个7的数量。
之后就可以通过高位开始枚举，求出区间内有多少个规定的数，如果询问大于总数，则输出"Nya!";
之后是怎么找到第K大数。
首先可以确定出位数，dp[i][x][y]表示i位时的满足数，那么大于dp[len-1][x][y]而小于dp[len][x][y]，len表示目标位数。
确定了位数之后，依旧从高位开始。比如说高位首先是0，而dp[len-1][x][y]小于k，说明0开头的目标说小于所求，所以往后继续找，记得要把之前的减掉。
还得注意一些细节，出现了4和7的情况。
貌似有题解说的是二分查找，没有过多的了解。
另外坑的是 这里的区间是左开右闭。
#include<iostream> #include<cstdio> #include<cstring>using namespace std;long long dp[25][25][25]; //dp[i][j][k]表示i位的数，有j个4，k个7的数量 long long p,q; int x,y;void Init(){memset(dp,0,sizeof(dp));dp[0][0][0]=1;for(int i=1;i<21;i++)for(int j=0;j<=i;j++)for(int k=0;k<=i;k++)if(j+k<=i){dp[i][j][k+1]+=dp[i-1][j][k];dp[i][j+1][k]+=dp[i-1][j][k];dp[i][j][k]+=dp[i-1][j][k]*8; //在高位加上除了4、7以外的8个数字 } }long long getCount(long long n){int digit[25],len=0;while(n){digit[++len]=n%10;n/=10;}digit[len+1]=0;long long ans=0;int cx=x,cy=y;for(int i=len;i>0;i--){ //从高位开始枚举for(int j=0;j<digit[i];j++){if(j==4){if(cx)ans+=dp[i-1][cx-1][cy];}else if(j==7){if(cy)ans+=dp[i-1][cx][cy-1];}elseans+=dp[i-1][cx][cy];}if(digit[i]==4)cx--;if(digit[i]==7)cy--;if(cx<0 || cy<0) //如果高位出现的4、7数量已经超过要求，则退出break;}return ans; }long long Solve(long long k){int len=1;while(1){if(dp[len-1][x][y]<k && dp[len][x][y]>=k) //找到目标数的长度break;len++;}long long res=0;int cx=x,cy=y;for(int i=len;i>0;i--) //从高位开始从小枚举for(int j=0;j<10;j++){int tx=cx,ty=cy;if(j==4){tx--;if(tx<0)continue;}if(j==7){ty--;if(ty<0)continue;}if(dp[i-1][tx][ty]>=k){res=res*10+j;cx=tx;cy=ty;break;}k-=dp[i-1][tx][ty];}return res; }int main(){//freopen("input.txt","r",stdin);int t,cases=0;scanf("%d",&t);Init();while(t--){scanf("%I64d%I64d%d%d",&p,&q,&x,&y);long long a=getCount(q+1);long long b=getCount(p+1); //注意是左开区间，int n;long long k;scanf("%d",&n);printf("Case #%d:\n",++cases);while(n--){scanf("%I64d",&k);if(k>a-b)puts("Nya!");elseprintf("%I64d\n",Solve(k+b));}}return 0; }
6, HDU 3709 Balance Number : http://acm.hdu.edu.cn/showproblem.php?pid=3709
平衡数，枚举支点，然后其它的类似。加一维表示当前的力矩，注意当力矩为负时，就要返回，否则会出现下标为负，也算是个剪枝。
题目大意: 题目先给出平衡数的概念：数n以数n中的某个位为支点，每个位上的数权值为（数字xi*（posi - 支点的posi）），如果数n里有一个支点使得所有数权值之和为0那么她就是平衡数。比如4139，以3为支点，左边 = 4 * (4 - 2) + 1 * (3 - 2) = 9，右边 = 9 * (1 - 2) = -9，左边加右边为0，所以4139是平衡数。现在给出一个区间[l,r]，问区间内平衡数有多少个？
解题思路：
这类题目用逆推要比正推好做，方法是记忆化搜索。每次向下传递目前的状态，下面每次都返回通过这些状态后面能得到的结果。
因为要权值之和为0，我们枚举每个支点o，然后从高位往地位搜索并记录状态，这里的状态为当前的位置pos，之前的权值之和pre、支点o，这三个组合起来就可以表示一个状态。每种状态都至多遍历一次，如果第二次遍历到某个状态，就直接返回前一次往下遍历的结果。
上一段已经解释了Dfs中的三个参数，那还剩下一个参数limit是干什么的？limit表示是否有上界，如果我们要找的是[0，12345,现在找到123，这时limit还是1，如果下一个枚举到的数是3，limit就变成0，以后都可以枚举到9而不是到5.
#include<iostream> #include<cstdio> #include<cstring>using namespace std;long long dp[20][20][2010]; //dp记忆化搜索用 ,dp[i][j][k]表示考虑i位数字，支点为j，力矩和为k int digit[20];long long DFS(int pos,int central,int pre,int limit){ //pos表示当前位置，central表示支点，pre表示从最高位到pos的力矩之和，limit表示是否有上限 1有 0无 if(pos<=0) //已经全部组合 return pre==0;if(pre<0) //前面组合而成的力矩之和已经小于0，后面的也都是负数 return 0;if(!limit && dp[pos][central][pre]!=-1) //没有上限且当前的状态之前已经搜索过return dp[pos][central][pre];int end=limit?digit[pos]:9; //有上限就设为上限，否则最高到9long long ans=0;for(int i=0;i<=end;i++)ans+=DFS(pos-1,central,pre+i*(pos-central),limit && (i==end));if(!limit)dp[pos][central][pre]=ans;return ans; }long long Solve(long long x){int len=0;while(x){digit[++len]=x%10;x/=10;}digit[len+1]=0;long long ans=0;for(int i=1;i<=len;i++) //枚举支点ans+=DFS(len,i,0,1);return ans-(len-1); //除掉全0的情况，00，0000满足条件，但是重复了 }int main(){//freopen("input.txt","r",stdin);long long a,b;int t;scanf("%d",&t);memset(dp,-1,sizeof(dp));while(t--){scanf("%I64d%I64d",&a,&b);printf("%I64d\n",Solve(b)-Solve(a-1));}return 0; }
7, HDU 3709 SNIBB : http://acm.hdu.edu.cn/showproblem.php?pid=3271
题意：将一个数转化成B进制后，他的val表示的是各位上的数字和。
首先还是预处理，dp[i][j]表示转化成B进制后，长度为i的数中，数字和为j的数字有多少个，感觉越来越像数位DP。。。
对于询问1：压根就是数位DP，从高位开始枚举，记录之前已经出现的位数和，然后枚举当前位。注意区间的开闭问题，边界处理好
对于询问2：首先通过询问1得出的数目，判断是否存在第K大，然后就是二分答案，判断[l,mid]中和为m的数有多少个。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm>using namespace std;int dp[32][310];void Init(int b,int m){ //转换成B进制后，长度为i的数中各位和为j的个数 memset(dp,0,sizeof(dp));dp[0][0]=1;for(int i=1;i<32;i++)for(int j=0;j<=m;j++)for(int k=0;k<b && k+j<=m;k++)dp[i][j+k]+=dp[i-1][j]; }int Cal(int n,int b,int m){ //统计[0,n]中转换成b进制，和为m的个数 int digit[35],len=0;while(n){digit[++len]=n%b;n/=b;}digit[len+1]=0;int ans=0,tot=0;for(int i=len;i>0;i--){for(int j=0;j<digit[i] && m-tot-j>=0;j++)ans+=dp[i-1][m-tot-j];tot+=digit[i];if(tot>m)break;}if(tot==m) //本身的和就是m，注意别落下ans++;return ans; }int main(){//freopen("input.txt","r",stdin);int cases=0;int op,x,y,b,m,k;while(~scanf("%d%d%d%d%d",&op,&x,&y,&b,&m)){Init(b,m);if(x>y)swap(x,y);printf("Case %d:\n",++cases);int ans=Cal(y,b,m)-Cal(x-1,b,m);if(op==1){printf("%d\n",ans);continue;}scanf("%d",&k);if(k>ans){puts("Could not find the Number!");continue;}int low=x,high=y,mid;while(low<high){//二分答案，判断在[l,mid]中和为m的个数mid=(int)((((long long)low+(long long)high))/2);int now=Cal(mid,b,m)-Cal(x-1,b,m);if(now<k)low=mid+1;elsehigh=mid;}printf("%d\n",low);}return 0; }
