[HDU3555]Bomb-白红宇

[HDU3555]Bomb

阅读量：4704 次

发布时间：2019-06-10

本文共 1987 字，大约阅读时间需要 6 分钟。

[HDU3555]Bomb

试题描述

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?

输入

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.

输出

For each test case, output an integer indicating the final points of the power.

输入示例

输出示例

数据规模及约定

见“输入”

题解

裸数位 dp，f[i][j] 表示前 i 位最高位为数字 j 的数中，包含“49”的个数。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 using namespace std;#define LL long longLL read() { LL x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); } return x * f;}#define maxn 21LL f[maxn][maxn], ten[maxn];int num[maxn], cnt;LL sum(LL x) { cnt = 0; LL orx = x; while(x) num[++cnt] = x % 10, x /= 10; LL sum = 0; for(int i = cnt; i; i--) { for(int j = 0; j < num[i]; j++) sum += f[i][j]; if(i < cnt && num[i+1] == 4 && num[i] == 9) { sum += orx % ten[i-1] + 1; break; } } return sum;}int main() { ten[0] = 1; for(int i = 1; i < maxn; i++) ten[i] = ten[i-1] * 10; for(int i = 1; i < maxn - 1; i++) for(int j = 0; j <= 9; j++) for(int k = 0; k <= 9; k++) { if(k == 4 && j == 9) f[i+1][k] += ten[i-1]; else f[i+1][k] += f[i][j]; } int T = read(); while(T--) { LL n = read(); printf("%lld\n", sum(n)); } return 0;}

打这种题最好写一发暴力。。。

转载于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/6107251.html

你可能感兴趣的文章