HDU - 2089 不要62(数位DP)
题目如下:
杭州人称那些傻乎乎粘嗒嗒的人为 626262(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有 444 或 626262 的号码。例如:
62315734188891462315 73418 88914623157341888914
都属于不吉利号码。但是,611526115261152 虽然含有 666 和 222 ,但不是 626262 连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对 n、m(0<n≤m<1000000)n、m(0<n≤m<1000000)n、m(0<n≤m<1000000),如果遇到都是 000 的整数对,则输入结束。
Output
对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。
Sample
Input
1 100
0 0
Output
80
题目链接
题解 or 思路:
数位DP
dfs(位置, 是否有限制, 上一位是否是 666 )
具体请参考下面的代码。
AC 代码如下:
/*
Make it simple and keep self stupid
author:Joanh_Lan
*/
#pragma GCC optimize(3)
#pragma GCC optimize("inline") // 如果比赛允许开编译器优化的话,可以默写这两段
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include <random>
#include <ctime>
#include <queue>
#include <stack>
#include <climits>
#define buff \ios::sync_with_stdio(false); \cin.tie(0);
// #define int long long
#define ll long long
#define PII pair<int, int>
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod = 1e9 + 7;
const int inf = 2147483647;
const int N = 1000009;
//int Mod(int a,int mod){return (a%mod+mod)%mod;}
//int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
//int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
//int inv(int a,int mod){return qmi(a,mod-2,mod);}
//int lcm(int a,int b){return a*b/__gcd(a,b);}
int l, r, f[N][2];
int a[N], idx;
int dfs(int pos, bool lim, bool sex)
{if (pos == 0)return 1;if (!lim && f[pos][sex] != -1)return f[pos][sex];int len = lim ? a[pos] : 9;int ans = 0;for (int i = 0; i <= len; i++){if (i == 4) continue;if (i == 2 && sex) continue;ans += dfs(pos - 1, lim && i == a[pos], i == 6);}if (!lim)f[pos][sex] = ans;return ans;
}
int work(int x)
{idx = 0;while (x){a[++idx] = x % 10;x /= 10;}return dfs(idx, 1, 0);
}
void solve()
{int x = work(l - 1), y = work(r);cout << y - x << '\n';
}
int main()
{buff;memset(f, -1, sizeof f);int _ = 1;// cin >> _;while (cin >> l >> r, l, r)solve();
}
相关文章:
HDU - 2089 不要62(数位DP)
题目如下: 杭州人称那些傻乎乎粘嗒嗒的人为 626262(音:laoer)。 杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来&#x…...
网络安全与防御
1. 什么是IDS? IDS(入侵检测系统):入侵检测是防火墙的合理补充,帮助系统对付网络攻击,扩展了系统管理员的安全管理能力,提高了信息安全基础结构的完整性。主要针对防火墙涉及不到的部分进行检测。 入侵检测主要面对的…...
【DT】蒸脱机的结构和工作原理
DT蒸脱机的结构和工作原理什么是DTDT结构图工作过程什么是DT DT 蒸脱机(DesolventazationerToaster),根据英文名可以看出来,他的作用是脱溶、烘烤。用于蒸脱湿豆粕中的溶剂。 大豆油生产工艺有2种:压榨油的加工工艺是…...
Docker管理软件
下面是一些常见的Docker管理软件 Portainer Portainer是一个轻量级的Docker管理界面,可以以用户友好的方式显示Docker环境的状态。它提供了仪表板、容器、镜像、卷、网络等功能。 Rancher Rancher是一个开源的Docker容器管理平台,支持多个主机和集群…...
关于运行时内存数据区的一些扩展概念
栈顶缓存技术(Top-of-Stack Cashing) 前面提过,基于栈式架构的虚拟机所使用的零地址指令更加紧凑,但完成一项操作的时候必然需要使用更多的入栈和出栈指令,这同时也就意味着将需要更多的指令分派(instruction dispatc…...
计算机组成原理第二章数据的表示与运算(中)
提示:且行且忘且随风,且行且看且从容 文章目录前言2.2.0 奇偶校验码(大纲已删)2.2.1 电路的基本原理 加法器设计2.2.2 并行进位加法器2.2.3 补码加减运算器2.2.4 标志位的生成2.2.5 定点数的移位运算2.2.62.2.6.1 原码的乘法运算2.2.6.2 补码的乘法运算2…...
我的第一台电脑的故事
第一台电脑啊,多么遥远的故事了,又似乎就在眼前。今天重回往事,就简单记录一下吧。 🌱缘起 那是初一,至今已13年,遂觉遥远,而又是立志我学习的起点,至今还在校园,又觉就…...
【1041. 困于环中的机器人】
来源:力扣(LeetCode) 描述: 在无限的平面上,机器人最初位于 (0, 0) 处,面朝北方。注意: 北方向 是 y 轴的正方向。南方向 是 y 轴的负方向。东方向 是 x 轴的正方向。西方向 是 x 轴的负方向。 机器人可…...
几何算法——4.交线(intersection curve)的表达与参数化、微分性质
几何算法——4.曲面求交的交线(intersection curve)的表达与参数化、微分性质1 关于曲面求交的交线表达2 交线的微分性质3 交线的参数化4 修正弦长参数化的微分性质1 关于曲面求交的交线表达 两个曲面求交,比较经典的方法是用跟踪法…...
【GPT】让你事半功倍特别好用的5个GPT工具
文章目录前言一、现在还能开通ChatGPT4.0吗?二、推荐五款与ChatGPT的相关实用工具1.一款浏览器插件:ChatGPT for Google2.一款生成图片的AI工具:midjourney3.推荐两款AI自动生成PPT:闪击PPT、mindshow4.识别PFD文件内容对话&#…...
人工智能大模型多场景应用原理解析
前言 在上篇文章《人工智能大模型之ChatGPT原理解析》中分享了一些大模型之ChatGPT的核心原理后,收到大量读者的反馈,诸如:在了解了核心原理后想进一步了解未来的发展趋势(比如生成式人工智能和元宇宙能擦出什么样的火花?),大模型…...
SpringBoot默认包扫描机制与默认配置文件
文章目录一、SpringBoot默认包扫描机制 - 示例二、SpringBoot默认扫描包机制 - 原理三、SpringBoot手动扫描包机制 - 原理&示例四、ComponentScan与MapperScan五、SpringBoot默认配置文件一、SpringBoot默认包扫描机制 - 示例 默认情况下,扫描启动类同级及其子…...
RabbitMq 消息可靠性问题(一) --- publisher发送时丢失
前言 消息从生产者发送到exchange, 再到 queue, 再到消费者。这个过程中有哪些有消息丢失的可能性呢? 发送时丢失: 生产者发送的消息未送达 exchange消息到达 exchange 后未到达 queue MQ 宕机,queue将消息丢失consumer 接收到消息后未消费…...
Java初识泛型
目录 一、包装类 1、基本数据类型和对应的包装类 2、装箱和拆箱 3、自动装箱和自动拆箱 二、什么是泛型 三、引出泛型 1、泛型的语法 四、泛型类的使用 1、语法 2、示例 3、类型推导(Type Inference) 六、泛型如何编译的 1、擦除机制 2、为什么不能实例化泛型类…...
寸照换底色技巧大全,超详细图文教程
在日常的设计工作中,我们常常需要将图片的背景色进行修改,以适应不同的场景和需求。其中最常用的方法就是寸照换底色技巧。本文将为大家介绍一些常见的寸照换底色技巧,并提供超详细的图文教程,帮助大家轻松完成这项任务。 一、使…...
这篇文章价值很大:股票历史分时成交数据怎么简单获取?【干货】
文章目录前言一、准备二、使用步骤1.引入库2,使用这个API查询历史分时数据:3.查询完整历史分时数据4.其他查询方法参数格式:[(市场代码, 股票代码), ...]参数:市场代码, 股票代码, 文件名, 起始位置, 数量参数:市场代码…...
muduo源码剖析--Buffer
Buffer类 Buffer类是自定义处理数据输入缓冲的类,底层是vector< char >,通过readIdx和writeIdx将缓冲区分为3个部分,第一部分是预留的8字节已经读出的缓冲区字节数、第二部分是还未读出的部分、第三部分是可写的部分。 Buffer类的设计…...
AI人工智能简介和其定义
全称:人工智能(Artificial Intelligence) 缩写:AI / ai 人工智能研究 亦称智械、机器智能,指由人制造出来的可以表现出智能的机器。通常人工智能是指通过普通计算机程序来呈现人类智能的技术。该词也指出研究这样的智…...
python数据清洗
数据清洗包括:空值,异常值,重复值,类型转换和数据整合这里数据清洗需要用到的库是pandas库,下载方式还是在终端运行 : pip install pandas.首先我们需要对数据进行读取import pandas as pddata pd.read_cs…...
Python3 os.makedirs() 方法、Python3 os.read() 方法
Python3 os.makedirs() 方法 概述 os.makedirs() 方法用于递归创建目录。像 mkdir(), 但创建的所有intermediate-level文件夹需要包含子目录。 语法 makedirs()方法语法格式如下: os.makedirs(path, mode0o777)参数 path -- 需要递归创建的目录。 mode -- 权限…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
用递归算法解锁「子集」问题 —— LeetCode 78题解析
文章目录 一、题目介绍二、递归思路详解:从决策树开始理解三、解法一:二叉决策树 DFS四、解法二:组合式回溯写法(推荐)五、解法对比 递归算法是编程中一种非常强大且常见的思想,它能够优雅地解决很多复杂的…...
