hdu---(3555)Bomb(数位dp（入门）)

时间：2022-11-05 03:48:51

Bomb

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

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
 
题意： 给你一个数n,要你统计出1到n中出现含有49数字的个数： 比如 498,549,49.....
对于这一道题： 看到一个博客引用了这张图片，觉得说的很清晰，就引用了..
hdu---(3555)Bomb(数位dp（入门）)
 
我们对于 i-1长度的数字分析，无疑就这么集中情况（当然只是围绕49来说的哇）首部分析：
                                                          i-1长度                                  那么对于 i长度
首部为49 ，那么它的格式必然为：              49****                                   ？49****（？可能为9）
 
首部保函9 ，那么它的格式必然为：             9*****                                   ？9*****（？可能为4）
 
首部部位49 ，那么它的格式为：                *******                                  ？*******（？可能为9）
 
    我们不妨用dp[i][2]表示首部为49的,dp[i][1]表示首部为9的，dp[i][0]表示首部不为49，于是我们可以发现这样一个规律：
 
     dp[i-1][2]向前移一位，即原来的个位变为十位，十位变为百位的那种移位。 形成dp[i][2],但是需要注意的是:
      当dp[i-1][2]时，其实由我上面说的，？可能为9 ，所以当向前移一位时，？为9的可能性被去掉了。所以
    dp[i-1][2]*10（移动一位时）需要减去 开头为9的那种模式dp[i-1][1],所以得到：
  （1）      dp[i][2]=dp[i-1][2]*10-dp[i-1][1];
    对于i位首部为9那么后面只需要满足不为49即可，刚好满足dp[i][0];
  （2）  所以 dp[i][1]=d[i-1][0];
   对于首部不为49的
       同样也可以分析出来...
      dp[i][0]=dp[i-1][0]*10+dp[i-1][1];
 
于是得到这样一个预处理方程：
                        dp[i][2]=dp[i-1][2]*10-dp[i-1][1];
                        dp[i][1]=d[i-1][0]; 
                        dp[i][0]=dp[i-1][0]*10+dp[i-1][1];
代码：详情见代码：
 //#define LOCAL

 #include<cstdio>

 #include<cstring>

 #define LL __int64

 using namespace std;

  const int maxn=;

 LL dp[maxn][]={};

 int nn[maxn];

 int main()

 {

   #ifdef LOCAL

     freopen("test.in","r",stdin);

   #endif

  int cas,i;

  LL n;

  scanf("%d",&cas);

  /*数位DP的惯有模式预处理*/

  dp[][]=;

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

  {

     dp[i][]=dp[i-][]*-dp[i-][];

     dp[i][]=dp[i-][];

     dp[i][]=dp[i-][]*+dp[i-][];

  }

  while(cas--)

  {

    scanf("%I64d",&n);

    i=;

    n+=;

    memset(nn,,sizeof(nn));

    while(n>)

    {

      nn[++i]=n%;

      n/=;

    }

    LL ans=;

    bool tag=;

    int num=;

    for(  ; i>=  ; i--  )

    {

          ans+=dp[i-][]*nn[i];  /*计算49开头的个数*/

          if(tag){

         ans+=dp[i-][]*nn[i];   /*当前面出现了49的时候，那么后面出现的任何数字也要进行统计*/

       }

       if(!tag&&nn[i]>)

       {

           ans+=dp[i-][];      /*如果没有出现49开头，只要首部大于5，那么必定保函有一个49*/

       }

       if(num==&&nn[i]==)

              tag=;

       num=nn[i];

    }

     printf("%I64d\n",ans);

  }

  return ;

 }

相关文章