题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=3555
题目:
输入t个数,如x,统计1~x含49的数字个数,注意x会很大,普通的暴力绝对超时!
解题思路:
数位dp模版题,记录每一位数的数组a[]从下标1开始存数,limit表示第pos位前所有位上的数是不是都达到了上限
两种方法:1.求0~x之间不含49的数字个数,x+1-solve()即是结果
2.直接求含49的数字个数
注意两种方法到达递归边界时返回值的区别!
第二种方法直接计算时的细节解析:(先看代码)
sum+=limit?n%z[pos-1]+1:z[pos-1];
如求1~5498间含49的数字个数,z[0]=1,z[pos]=z[pos-1]*10:
当千位为0,百位为4,十位为9时,limit为true,pos=2
n%z[pos-1]+1=5498%z[0]+1=9;即存在的情况有5490~5498共9个符合条件的数
当千位为0,百位为4,十位为9时,limit=false,pos=2
z[pos-1]=z[0]=10;即存在0490~0499共10个符合条件的数
当千位为0,百位为1,十位为4,个位为9时,limit=false,pos=1
z[pos-1]=z[0]=1,即只有0149一个符合条件的数
ac代码:
1.先求不含49
#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 1000005
#define inf 0x3fffffff
using namespace std;
typedef long long ll;
ll dp[20][3],a[20],z[30];
ll n,t;
ll dfs(ll pos,ll pre,int sta,bool limit)//求0~n中不包含49
{
if(pos==0) return 1;//注意返回的是1
if(!limit&&dp[pos][sta]!=-1) return dp[pos][sta];
ll sum=0;
ll up=limit?a[pos]:9;
for(ll i=0;i<=up;i++)
{
if(pre==4&&i==9) continue;
sum+=dfs(pos-1,i,i==4,limit && i==a[pos]);
}
if(!limit) dp[pos][sta]=sum;
return sum;
}
ll solve(ll x)
{
ll i=0;
while(x)
{
a[++i]=x%10;
x/=10;
}
return dfs(i,-1,0,true);
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
memset(dp,-1,sizeof(dp));
printf("%lld\n",n+1-solve(n));
}
return 0;
}
2.直接求含49
#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 1000005
#define inf 0x3fffffff
using namespace std;
typedef long long ll;
ll dp[20][3],a[20],z[30];
ll n,t;
ll dfs(ll pos,ll pre,int sta,bool limit)
{
if(pos==0) return 0;//注意返回0
if(!limit&&dp[pos][sta]!=-1) return dp[pos][sta];
ll sum=0;
ll up=limit?a[pos]:9;
for(ll i=0;i<=up;i++)
{
if(pre==4&&i==9)
sum+=limit?n%z[pos-1]+1:z[pos-1];//直接计算,具体细节在解题思路
else sum+=dfs(pos-1,i,i==4,limit && i==a[pos]);
}
if(!limit) dp[pos][sta]=sum;
return sum;
}
ll solve(ll x)
{
ll i=0;
while(x)
{
a[++i]=x%10;
x/=10;
}
return dfs(i,-1,0,true);
}
int main()
{
z[0]=1;
cin>>t;
for(int i=1;i<=30;i++)
z[i]=z[i-1]*10;
while(t--)
{
cin>>n;
memset(dp,-1,sizeof(dp));
printf("%lld\n",solve(n));
}
return 0;
}