hdu3555 Bomb(数位dp）

时间：2023-01-22 03:47:20

题目传送门

Bomb

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

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 
题意：给你n，从[1,n]中找出含有“49”的数的个数
题解：数位dp入门题
代码：
第一份是间接法做的
#include<iostream>

#include<string.h>

#include<algorithm>

#include<stdio.h>

#include<queue>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long long ll;

typedef pair<int,int> PII;

#define mod 1000000007

#define pb push_back

#define mp make_pair

#define all(x) (x).begin(),(x).end()

#define fi first

#define se second

//head

ll n;

int bit[];

ll dp[][];

ll dfs(int pos,int pre,int sta,bool limit)

{

    if(pos==-)return ;

    if(!limit&&dp[pos][sta]!=-)return dp[pos][sta];

    int up=limit?bit[pos]:;

    ll ans=;

    for(int i=;i<=up;i++)

    {

        if(pre==&&i==)

            continue;

        ans+=dfs(pos-,i,i==,limit&&i==bit[pos]);

    }

    if(!limit)dp[pos][sta]=ans;

    return ans;

}

ll solve(ll x)

{

    int len=;

    while(x)

    {

        bit[len++]=x%;

        x/=;

    }

    return dfs(len-,-,,true);

}

int main()

{

    int T;

     scanf("%d",&T);

     while(T--){

         scanf("%lld",&n);

        memset(dp,-,sizeof(dp));

        printf("%lld\n",n+-solve(n));

     }

    return ;

}

下面的是直接法做的：

pre=0: 没有49; pre=1: 前一位为4; pre=2: 前几位中有49

#include<iostream>

#include<string.h>

#include<algorithm>

#include<stdio.h>

#include<queue>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long long ll;

typedef pair<int,int> PII;

#define mod 1000000007

#define pb push_back

#define mp make_pair

#define all(x) (x).begin(),(x).end()

#define fi first

#define se second

//head

ll n;

int bit[];

ll dp[][];

ll dfs(int pos,int pre,bool limit)

{

    if(pos==-)return pre==;

    if(!limit&&dp[pos][pre]!=-)return dp[pos][pre];

    int up=limit?bit[pos]:;

    ll ans=;

    for(int i=;i<=up;i++)

    {

        if(pre==||pre==&&i==)

        ans+=dfs(pos-,,limit&&i==bit[pos]);

        else if(i==)

         ans+=dfs(pos-,,limit&&i==bit[pos]);

        else

        ans+=dfs(pos-,,limit&&i==bit[pos]);

    }

    if(!limit)dp[pos][pre]=ans;

    return ans;

}

ll solve(ll x)

{

    int len=;

    while(x)

    {

        bit[len++]=x%;

        x/=;

    }

    return dfs(len-,,true);

}

int main()

{

    int T;

     scanf("%d",&T);

    memset(dp,-,sizeof(dp));

     while(T--){

         scanf("%lld",&n);

        printf("%lld\n",solve(n));

     }

    return ;

}
 

相关文章