AcWing 1085. 不要62
不要 AcWing 62
2023-09-27 14:28:12 时间
\(AcWing\) \(1085\). 不要\(62\)
一、题目描述
杭州人称那些傻乎乎粘嗒嗒的人为 \(62\)(音:\(laoer\))。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有 \(4\) 或 \(62\) 的号码。例如:\(62315\),\(73418\),\(88914\) 都属于不吉利号码。但是,\(61152\) 虽然含有 \(6\) 和 \(2\),但不是 连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照号区间 \([n,m]\),推断出交管局今后又要实际上给多少辆新的士车上牌照了。
二、实现思路
- 给出了\([n,m]\)的区间
- 不要数字\(4\),不要连续的\(62\),问可以有多少个符合条件的数字
以上两个条件,满足数位\(DP\)的情况,可以直接套用模板解决:
三、实现代码
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int N = 32;
int a[N];
int f[N][10];
int dfs(int pos, int pre, bool limit) {
if (pos == 0) return 1;
if (!limit && ~f[pos][pre]) return f[pos][pre];
int up = limit ? a[pos] : 9;
int ans = 0;
for (int i = 0; i <= up; i++) {
if (pre == 6 && i == 2) continue;
if (i == 4) continue;
ans += dfs(pos - 1, i, limit && i == a[pos]);
}
if (!limit) f[pos][pre] = ans;
return ans;
}
inline int calc(int x) {
if (x == -1) return 0;
int al = 0;
while (x) a[++al] = x % 10, x /= 10;
return dfs(al, -1, true);
}
int main() {
memset(f, -1, sizeof f);
int l, r;
while (~scanf("%d%d", &l, &r) && l + r)
printf("%d\n", calc(r) - calc(l - 1));
return 0;
}
相关文章
- 面试官问你斐波那契数列的时候不要高兴得太早 搞懂C语言函数指针 搜索引擎还可以这么玩? 那些相见恨晚的搜索技巧
- C/C++写函数的时候函数名不要用div
- 九月,劝搞测试的不要跳槽
- 增强现实?先不要指望那些眼镜了
- 人生必须做的十件事情 不要在意别人的评论
- 从程序员到项目经理(10):程序员加油站 --要执着但不要固执【转载】
- 校招答疑总结!准备实习、校招的学妹(弟)们,可不要努力错方向了!
- 小豆君:你的目标是让其它工具为你服务,你要踩在巨人的肩膀上创造世界(摒弃掉你的好奇心,千万不要去追求第三方类或工具是怎么实现的,这往往会让你收效甚微,其实,你只需要熟练掌握它的接口,知道类的目的即可,不可犯面向过程的毛病)
- 《C语言解惑》—— 1.7 scanf要“&”不要“n”
- MATLAB制作简易版本不要停,八分音符酱 (大概算音游)
- 懒要懒到底,能自动的就不要手动,Hibernate正向工程完成Oracle数据库到MySql数据库转换(含字段转换、注释)
- 为什么说不懂数据思维和零售思维就不要从事零售业?