【hdu3555】Bomb 数位dp

题目描述

求 1~N 内包含数位串 “49” 的数的个数。

输入

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.

样例输入

3
1
50
500

样例输出

0
1
15

题解

数位dp

设 $f[i][j][0/1]$ 表示 $i$ 位数，最高位为 $j$ ，是否包含数位串 “49” 的数的个数。

首先预处理出 $f$ 数组，根据是否以前有“49”或能构成“49”来更新新的 $f$ 值。

然后对于每个询问跑数位dp：先计算位数不满 $n$ 的位数的数的答案，然后从高位到低位计算，统计该位小于该数当前位的的数，相等的位考虑下一位。

注意统计当前位时需要同时考虑前面是否有“49”，两个数位能否拼成“49”，后面是否有“49”。然而本题数字串的第二位是“9”，枚举时枚举不到9，因此不需要考虑前后两个数位拼成“49”的情况。

把询问转化为 $[1,n)$ 的区间会更容易些。

代码中为了避免一些细节（比如 $10^{19}$ 爆long long之类的），使用了unsigned long long。

#include <cstdio>

typedef unsigned long long ull;

ull f[20][10][2] , b[20];

void init()

{

	int i , j , k , l;

	f[0][0][0] = b[0] = 1;

	for(i = 1 ; i < 20 ; i ++ )

	{

		b[i] = b[i - 1] * 10;

		for(j = 0 ; j < 10 ; j ++ )

			for(k = 0 ; k < 10 ; k ++ )

				for(l = 0 ; l < 2 ; l ++ )

					f[i][j][l || (j == 4 && k == 9)] += f[i - 1][k][l];

	}

}

ull calc(ull n)

{

	int i , j , di = 1 , flag = 0 , last = 0 , now;

	ull ans = 0;

	for(i = 1 ; b[i] <= n ; i ++ )

		for(j = 1 ; j < 10 ; j ++ )

			ans += f[i][j][1];

	for( ; i ; i -- )

	{

		now = n / b[i - 1] % 10;

		for(j = di ; j < now ; j ++ )

			ans += f[i][j][1] + f[i][j][0] * flag;

		if(last == 4 && now == 9) flag = 1;

		di = 0 , last = now;

	}

	return ans;

}

int main()

{

	init();

	int T;

	ull n;

	scanf("%d" , &T);

	while(T -- ) scanf("%llu" , &n) , printf("%llu\n" , calc(n + 1));

	return 0;

}

巴特西

【hdu3555】Bomb 数位dp

最新文章

热门文章