HDU 3555 Bomb

  • 2018-09-18
  • 19
  • 0

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.

题目链接

之前写这种题(HDU 20892018年全国多校算法寒假训练营练习比赛(第二场)G)是直接对数据范围内所有数进行判断打表再在询问时循环计数,但是由于这题数据范围很大不能这么写,所以就学习了一下数位dp。

此题数位dp中dp[i][j]代表i位数中首位为j时不含49的数字个数。

那么状态转移公式就为dp[i][j]=\sum_{k=0}^{9}dp[i-1][k],其中j=4和k=9不能同时满足。

那么对于询问N,在计算1-N中不含49数字个数的时候从N的最高位Len开始求所有\sum_{j=0}^{9}dp[Len][j]之和并计入结果之中,依次向低位循环计数,当且仅当高一位数为4时dp[Len][9]不计数,当N的某两位为49时跳出循环(此时与低位数无关,无论低位数是几都会含有49)。

最后用总数减去计算得到的不含有49的数量即为含有49的数量。

AC代码:

评论

还没有任何评论,你来说两句吧