Bomb
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
HintFrom 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
题目类型：数位DP
算法分析：dp[i][0]表示长度为i不含有49的数字的个数，dp[i][1]表示长度为i不含有49且高位数字为9的数字的个数，dp[i][2]表示长度为i含有49的数字的个数。状态转移方程为dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1]; dp[i][1] = dp[i-1][2]; dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1]，初始条件为dp[0][0] = 1，最后对于每个读入的数字从高位开始计算：先加上当前位乘上低位含有49的数字的个数。然后判断此时49是否曾经出现过，若出现过，则累加当前位乘上低位不含有49的数字的个数。若此时最高位的值大于4，则还要加上低位不含有49且最高位数字为9的个数，最后再判断当前位和高一位的值是否能够组成49，若可以，则把标志置为true
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
/************************************************* Author :supermaker Created Time :2015/11/30 23:10:47 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; LL dp[26][3], aa[66]; void PP () { memset (dp, 0, sizeof (dp)); dp[0][0] = 1; for (int i = 1; i < 26; i++) { dp[i][0] = dp[i-1][0] * 10 - dp[i-1][1]; dp[i][1] = dp[i-1][0]; dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1]; } } int main() { //CFF; //CPPFF; PP (); int t; scanf ("%d", &t); while (t--) { LL n; scanf ("%I64d", &n); int len = 0; n++; while (n) { aa[++len] = n % 10; n /= 10; } aa[len+1] = 0; LL res = 0; bool is_have = false; for (int i = len; i >= 1; i--) { res += dp[i-1][2] * aa[i]; if (is_have) res += dp[i-1][0] * aa[i]; if (!is_have && aa[i] > 4) res += dp[i-1][1]; if (aa[i+1] == 4 && aa[i] == 9) is_have = true; } printf ("%I64d\n", res); } return 0; } |
- hdu2089：下一篇 »