F Find the AFei Numbers
2024-08-23 01:25:46
链接：https://ac.nowcoder.com/acm/contest/338/F
来源：牛客网
题目描述
AFei loves numbers. He defines the natural number containing "520" as the AFei number, such as 1234520, 8752012 and 5201314. Now he wants to know how many AFei numbers are not greater than n.
输入描述:
The first line contains an integer T (1 <= T <= 100 ). The following T lines contain an interger n ( 0 <= n <= 1e18 ).
输出描述:
For the last T lines, output the total numbers of AFei numbers that are not greater than n.
示例1
说明
For the first case, only 520 is AFei number. For the second case, 520,1520, 2520, 3520, 4520, 5200, 5201, 5202, 5203, 5204, 5205, 5206, 5207, 5208, 5209 and 5520 are AFei number. So there are 16 AFei numbers.
题意：给定一个自然数n(<=n<=1e18)，求[,n]里有多少个整数包含“”(即所谓Afei数的数量) 解题思路： 数位DP入门题。 首先，设dp[i]表示长度为i的AFei数的数量。发现这样不行，因为按数位计算的话，每次只会考虑一位，而AFei 数的特征是要有连续的三位，并且第一位是5，第二位是2，第三位是0。 这说明需要记录前两位，那么设dp[i][j]表示以j开头，后面还有i位的AFei数的数量。比如dp[][]就是表示形 如25****的数字中，AFei数的数量。因为n只有1e18，所以i最大不超过19，而j是用来记录前两位的，所以j最 大不超过99，所以声明dp数组的时候只需要long long dp[][]即可。 AFei数并没有规定“”的数量有多少个，碰到这样的我习惯性反着算，也就是用dp[i][j]表示以j开头，后面 还有i位的不是AFei数的数量。算到最后再减一下就行了。 状态转移方程：
举个例子：以f(****)表示形如****的不是afei数的数量，显然：f[****]=f[***]+f[***]+f[***]+f[***]+f[***]+f[***]+f[***]+f[***]+f[***]+f[***]也就是dp[][] = σ
最新文章
- ubuntu下cacti安装配置
- js数组去重的4个方法
- oracle学习 十二 使用.net程序调用带返回值的存储过程（持续更新）
- 关于近期需要学习sqlserver2008
- poj 1986 Distance Queries（LCA:倍增/离线）
- Eclipse不能自动编译 java文件的解决方案
- MVC 文件上传
- 列存储段消除（ColumnStore Segment Elimination）
- Windows下安装Nodejs步骤
- ThreadLocal深入剖析
- Windows下安装Kafka
- Go-常用库的介绍
- android异步任务处理（网络等耗时操作）
- intellij idea 相关设置
- git中tag的使用
- Python3+SQLAlchemy不使用字段名获取主键值教程
- c# 中config.exe 引发的一些问题
- Java程序运行机制及开发环境
- JavaScript -基础- 函数与对象（四) BOM 对象
- Jenkins进阶-发布后自动创建git tag(5)
热门文章