【hdu3555】Bomb 数位dp
DP 数位
2023-09-11 14:22:39 时间
题目描述
求 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; }
相关文章
- hdu2167 方格取数 状态压缩dp
- [CQOI2016]手机号码(数位DP)
- 和与或(数位DP + 状压)
- CodeForces 935E Fafa and Ancient Mathematics (树形DP)
- BZOJ 1026 [SCOI2009]windy数 (数位DP)
- HDU 6156 Palindrome Function (数位DP)
- SPOJ BALNUM (数位DP)
- CodeForces 55D Beautiful numbers (数位DP)
- HDU 5898 odd-even number (数位DP)
- LightOJ 1140 How Many Zeroes? (数位DP)
- HDU 3652 B-number (数位DP)
- CCF 201312-4有趣的数 (数位DP, 状压DP, 组合数学+暴力枚举, 推公式, 矩阵快速幂)
- HDU 1864 最大报销额 (DP-01背包问题)
- 【USACO 3.2】Stringsobits (dp)
- 猿创征文 |【算法面试入门必刷】动态规划-线性dp(二)
- hdu 4734 数位dp
- 【bzoj3717】[PA2014]Pakowanie 状压dp
- 【bzoj5064】B-number 数位dp
- 【bzoj3672】[Noi2014]购票 斜率优化dp+CDQ分治+树的点分治
- 【bzoj3329】Xorequ 数位dp+矩阵乘法
- 【bzoj1222】[HNOI2001]产品加工 背包dp
- 【bzoj2806】[Ctsc2012]Cheat 广义后缀自动机+二分+单调队列优化dp
- 【bzoj2435】[NOI2011]道路修建 树形dp
- 等和的分隔子集(DP)