数位DP HDU3555

扫码查看

Bomb

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 15025    Accepted Submission(s): 5427

Problem Description
The
counter-terrorists found a time bomb in the dust. But this time the
terrorists improve on the time bomb. The number sequence of the time
bomb counts from 1 to N. If the current number sequence includes the
sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?
 
Input
The
first line of input consists of an integer T (1 <= T <= 10000),
indicating the number of test cases. For each test case, there will be
an integer N (1 <= N <= 2^63-1) as the description.

The input terminates by end of file marker.

 
Output
For each test case, output an integer indicating the final points of the power.
 
Sample Input
3
1
50
500
 
Sample Output
0
1
15

Hint

From 1 to 500, the numbers that include the sub-sequence "49" are "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499",
so the answer is 15.

 
Author
fatboy_cw@WHU
 
Source
 
Recommend
zhouzeyong   |   We have carefully selected several similar problems for you:  3554 3556 3557 3558 3559 
 
题意:
  1~nz中包含49的数有几个。
代码:
 /*
本题与HDU2089相似,把那道题的代码改了一下找出了不含49的,然后用总数减去,简单粗暴,当然有更好的方法。
*/
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
int t;
long long dp[][],n;
void init()
{
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
for(int k=;k<;k++)
{
if(j==&&k==) continue;
dp[i][j]+=dp[i-][k];
}
}
}
}
long long insum(long long n)
{
long long sum=;
int lne=,c[]={};
while(n)
{
c[lne++]=n%;
n/=;
}
for(int i=lne-;i>;i--)
{
for(int j=;j<c[i];j++) //j不能等于c[i],因为dp[i][j]中的j代表第i位取j时的总数,而j后面的数
//要全部遍历一遍,这里j后面并非取全部数而是取到给出的数的后几位
{
if(j==&&c[i+]==) continue;
sum+=dp[i][j];
}
if(c[i]==&&c[i+]==) break;
}
return sum;
}
int main()
{
scanf("%d",&t);
while(t--)
{
memset(dp,,sizeof(dp));
dp[][]=;
cin>>n;
n+=;
init();
long long a=insum(n);
cout<<n-a<<endl;
}
return ;
} /*
别人的一个更好的方法。很难想到。
*/
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
int t;
long long dp[][],n; //dp[i][0]表示到第i位没有49的个数,dp[i][1]表示到第i位没有49但第i位是9的个数,
//dp[i]][2]表示到第i位包含49的个数。
void init()
{
dp[][]=; //初始化
dp[][]=;
dp[][]=;
for(int i=;i<;i++)
{
dp[i][]=*dp[i-][]-dp[i-][]; //到第i位没有49的个数等于第i位依次取0~9连上后面没有49的,
//然后去掉第i位取4,i-1位为9的情况。
dp[i][]=dp[i-][]; //第i位是9时
dp[i][]=*dp[i-][]+dp[i-][]; //到第i位包含49的个数等于第i位依次取0~9连上后面包含49的,
//再加上第i位取4时,i-1位是9的情况。
}
}
long long insum(long long n)
{
long long sum=;
int c[]={};
int cnt=;
while(n)
{
c[cnt++]=n%;
n/=;
}
bool flag=false;
for(int i=cnt-;i>;i--) //从高位到低位依次枚举
{
sum+=dp[i-][]*c[i]; //到第i-1位包含49,就加上0~c[i]个
if(flag) sum+=dp[i-][]*c[i];
else
{
if(c[i]>) sum+=dp[i-][]; //如果第i位大于4了,并且i-1是9,则一定包含49.
}
if(c[i+]==&&c[i]==) flag=true; //当从高位出现49之后后面dp[i][0]就无意义了,全加上
}
return sum;
}
int main()
{
scanf("%d",&t);
{
while(t--)
{
scanf("%lld",&n);
init();
printf("%lld\n",insum(n+)); //计算结果不包含n本身
}
}
return ;
}
 //记忆化搜索法
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
long long n;
int t;
long long dp[][];
int c[];
long long dfs(int lne,int have,int lim)
{
if(lne<=)
return have==;
if(!lim&&dp[lne][have]!=-)
return dp[lne][have];
long long ans=;
int nnum=lim?c[lne]:;
for(int i=;i<=nnum;i++)
{
int nhave=have;
if(have==&&i==) nhave=;
if(have==&&i!=&&i!=) nhave=;
if(have==&&i==) nhave=;
ans+=dfs(lne-,nhave,lim&&i==nnum);
}
if(!lim)
dp[lne][have]=ans;
return ans;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
memset(dp,-,sizeof(dp));
int cnt=;
while(n)
{
c[++cnt]=n%;
n/=;
}
c[cnt+]=;
printf("%lld\n",dfs(cnt,,));
}
return ;
}
05-11 17:02
查看更多