首页 > 代码库 > hdu---(3555)Bomb(数位dp（入门）)

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

2024-07-24 18:45:33   220人阅读

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
3150500
 

 

Sample Output
0115
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
2010 ACM-ICPC Multi-University Training Contest（12）——Host by WHU
 
题意： 给你一个数n,要你统计出1到n中出现含有49数字的个数： 比如 498,549,49.....
对于这一道题： 看到一个博客引用了这张图片，觉得说的很清晰，就引用了..
 
我们对于 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];
代码：详情见代码：
 1 //#define LOCAL 2 #include<cstdio> 3 #include<cstring> 4 #define LL __int64 5 using namespace std; 6  const int maxn=25; 7 LL dp[maxn][3]={0}; 8 int nn[maxn]; 9 int main()10 {11 12   #ifdef LOCAL13     freopen("test.in","r",stdin);14   #endif15  int cas,i;16  LL n;17  scanf("%d",&cas);18  /*数位DP的惯有模式预处理*/19  dp[0][0]=1;20  for(i=1;i<=20;i++)21  {22     dp[i][0]=dp[i-1][0]*10-dp[i-1][1];23     dp[i][1]=dp[i-1][0];24     dp[i][2]=dp[i-1][2]*10+dp[i-1][1];25  }26  while(cas--)27  {28    scanf("%I64d",&n);29    i=0;30    n+=1;31    memset(nn,0,sizeof(nn));32    while(n>0)33    {34      nn[++i]=n%10;35      n/=10;36    }37    LL ans=0;38    bool tag=0;39    int num=0;40    for(  ; i>=1  ; i--  )41    {42          ans+=dp[i-1][2]*nn[i];  /*计算49开头的个数*/43          if(tag){44         ans+=dp[i-1][0]*nn[i];   /*当前面出现了49的时候，那么后面出现的任何数字也要进行统计*/45       }46       if(!tag&&nn[i]>4)47       {48           ans+=dp[i-1][1];      /*如果没有出现49开头，只要首部大于5，那么必定保函有一个49*/49       }50       if(num==4&&nn[i]==9)51              tag=1;52       num=nn[i];53    }54     printf("%I64d\n",ans);55  }56  return 0;57 }
View Code

 

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


联系
我们