Hdu3555 Bomb

发表于 | 更新于: | 分类于 ， ， | | 阅读数
字数统计: 640 | 阅读时长 ≈ 3

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 \leq T \leq 10000)$, indicating the number of test cases. For each test case, there will be an integer $N (1 \leq N \leq 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

1
2
3
4
3
1
50
500

Sample Output

1
2
3
0
1
15

Analysis

数位DP的模板题。题意是给出数N，求1到N内包含数字”49”的数的个数。

将数N按从低位到高位的顺序逐位存储在数组a中，从最高位开始往最低位搜索。

解释一下搜索的函数

1
ll dfs(int pos, bool state, bool limit)

pos表示当前dfs正在搜索的数位，state存储了搜索的前一位是不是”4”，如果true则表明是”4”，limit表示当前位是否存在最高位，例如1275，在前面为12时第三位最高只能取7，但是前面为11时第三位就可以取1到9，这时就需要用limit判断它否取到9。因为从最高位开始搜索，所以一开始传入limit为true。

这里用dp[20][2]来记忆化搜索结果，其中dp[i][0]表示搜索的前一位不是”4”的情况下，当前位有多少取法使其不含”49”，而dp[i][1]表示前一位是”4”的情况下，当前位有多少种取法使其不含”49”。

最后搜索出的结果是从0到N中不包含”49”的数字的个数，显然0是不包含的，所以要求1到N内包含”49”的数的个数的最终的结果应该是

1
N-solve(N)+1

代码如下。

Code

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
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

int T;
ll N;
int a[20];
ll dp[20][2];
int sum = 0;

ll dfs(int pos, bool state, bool limit)
{
	if (pos == 0)
		return 1;
	if (!limit&&dp[pos][state])
		return dp[pos][state];
	int up = (limit ? a[pos] : 9);
	ll cnt = 0;
	for (int i = 0; i <= up; i++)
	{
		if (state && (i == 9))
			continue;
		cnt += dfs(pos - 1, i == 4, limit && (i == up));
	}
	if (limit)
		return cnt;
	else
	{
		dp[pos][state] = cnt;
		return cnt;
	}

}

ll solve(ll n)
{
	int i = 0;
	while (n)
	{
		a[++i] = n % (ll)10;
		n /= (ll)10;
	}
	return dfs(i, false, true);
}

int main()
{
	memset(a, 0, sizeof(a));
	memset(dp, 0, sizeof(dp));
	cin >> T;
	while (T-- != 0)
	{
		cin >> N;
		cout << N - (solve(N) - solve(0)) << endl;
	}
	return 0;
}