洛谷-P4124题-手机号码-Java
题目
题目链接: https://www.luogu.com.cn/problem/P4124

分析
给定两个长度为11位的数字,代表两个区间 [L,R] 需要编写程序来计算出,这两个区间内满足要求的数字个数。这样的题一般来说就是数位dp题。首先我们可以根据容斥原理 [0,R]中满足要求的个数 - [0,L-1]中满足要求的个数 来计算出 [L,R] 这个区间中满足要求数字的数量。
但是由于给定的数字范围很大,超过了int与long类型的范围,只能用字符串存储,那么字符串的加减计算就变得很麻烦了。那么可以这样计算 [0,R]-[0,L] 最后再特判一下 L 串是否符合要求,符合要求的话,最后的答案再+1。
根据题目要求,我们需要使用两个变量来记录前两个位置上的数,用来判断是否符合条件,还需要一个变量来记录当前数字是否满足要求,还有使用一个变量来记录当前数字是否出现过4与8。
然后就是套用数位dp的模板了。
code
package dp.数位dp;import java.util.*;public class Main {static final int N = 12;static final int M = (1 << 11);static long[][][][][] memo = new long[N][N][N][2][M];public static void main(String[] args) {Scanner in = new Scanner(System.in);// 由于数字位数太大,那么只能用字符串读取再转成字符数组char[] l = in.next().toCharArray();char[] r = in.next().toCharArray();reset(r.length);long ans = dfs(r, 0, 10, 10, false, true, 0);reset(l.length);ans -= dfs(l, 0, 10, 10, false, true, 0);if (check(l)) {++ans;}System.out.println(ans);}/** chs ;从高到底存储着数字的每一个数位* i :当前数位下标* pp :表示当前数位前一位的前一位数字* p :表示当前数位前一位的数字* flag :表示当前数字中是否出现过3个相邻且相等的数字* isLimit :表示构造当前位数字是否受限制* status :用二进制位来判断当前数字中是否同时出现过4与8* */public static long dfs(char[] chs, int i, int pp, int p, boolean flag, boolean isLimit, int status) {if (i >= chs.length) {return flag ? 1 : 0;}if (!isLimit && memo[i][pp][p][flag ? 1 : 0][status] != -1) {return memo[i][pp][p][flag ? 1 : 0][status];}long ans = 0;int up = isLimit ? chs[i] - '0' : 9; // 获取构造当前数字的上限// 无前导零for (int d = (i == 0) ? 1 : 0; d <= up; ++d) {// 不能同时出现4或8if ((d == 4 && ((status >> 8) & 1) != 0) || (d == 8 && ((status >> 4) & 1) != 0)) {continue;}ans += dfs(chs, i + 1, p, d, flag || (pp == p && d == p), isLimit && d == up, status | (1 << d));}if (!isLimit) {memo[i][pp][p][flag ? 1 : 0][status] = ans;}return ans;}// 判断一个数字是否符合条件public static boolean check(char[] chs) {if(chs[0] == '0') { return false; }char pp = 'x', p = 'x';boolean flag=false,cnt4 = false, cnt8 = false;for (char ch : chs) {if (ch == '4') {cnt4 = true;} else if (ch == '8') {cnt8 = true;}if (cnt4 && cnt8) {return false;}if (pp == p && p == ch) {flag=true;}pp = p;p = ch;}return !(cnt4 && cnt8) && flag;}public static void reset(int n) {for (int i = 0; i < n; i++) {for (int j = 0; j < memo[i].length; j++) {for (int k = 0; k < memo[i][j].length; k++) {for (int u = 0; u < memo[i][j][k].length; u++) {Arrays.fill(memo[i][j][k][u], -1);}}}}}
}
提交结果:

相关文章:
洛谷-P4124题-手机号码-Java
题目 题目链接: https://www.luogu.com.cn/problem/P4124 分析 给定两个长度为11位的数字,代表两个区间 [L,R] 需要编写程序来计算出,这两个区间内满足要求的数字个数。这样的题一般来说就是数位dp题。首先我们可以根据容斥原理 [0,R]中满…...
仅使用 Python 创建的 Web 应用程序(前端版本)第08章_商品详细
在本章中,我们将实现一个产品详细信息页面。 完成后的图像如下。 Model、MockDB、Service都是在产品列表页实现的,所以创建步骤如下。 No分类内容1Page定义PageId并创建继承自BasePage的页面类2Application将页面 ID 和页面类对添加到 MultiPageApp 的页面中Page:定义PageI…...
Stable Diffusion 长视频真人动画风格互转
Stable Diffusion Temporal-Kit和EbSynth 从娱乐到商用 1. Temporal Kit 和 EbSynth1.1 提取关键帧1.2 关键帧风格迁移1.3 生成序列帧2. 真人转卡通3. 卡通转真人4. 编辑技巧5. ControlNet + TemporalNet + 达芬奇Fusion6. Rerender A Video7. DiffSynth-Studio基于SD的风格化…...
精要图示:园区金融数字化服务蓝图,以园区为支点推动信贷业务增长
作为企业集聚地,园区已然成为银行业夯实客群基础的重要切口,各大行陆续围绕园区场景创新金融产品,以期抢跑园区金融新赛道、把握新增量。 启信慧眼首推一站式【园区金融】数字化服务方案,该方案同时支持启信天元私有化部署&#x…...
2024 中国(南京)国际口腔设备器械博览会
2024 中国(南京)国际口腔设备器械博览会 时间:2024 年 7 月 18-20 日 地点:南京国际展览中心 WeChat_20230512134641 主办单位: 南京民营口腔医疗协会 北京铭曼国际展览有限公司 承办单位: 北京铭曼国际展览有限公司 展会介绍 随…...
【MyBatis】快速入门MyBatis(保姆式教学),你值得一看
文章目录 📄前言一. Mybatis简介✈️1. 什么是Mybatis🚀2. 为什么使用Mybatis 二. Mybatis快速入门🍆1. mybatis使用前准备1.1 创建springboot项目并引入相关依赖1.2 在 application.ym中进行数据源的配置1.3 创建数据表,准备表数…...
git pull代码时候报错:error: cannot open .git/FETCH_HEAD: Permission denied
git pull代码时候报错: error: cannot open .git/FETCH_HEAD: Permission denied 原因: 当前登录用户没有修改目录的权限。 解决办法: 修改当前目录权限 1. whoami 查看当前登录用户 xxx$ whoami 假设上边查询登陆账号为:csd…...
shell - 正则表达式和grep命令和sed命令
一.正则表达式概述 1.正则表达式定义 1.1 定义 使用字符串描述、匹配一系列符合某个规则的字符串 1.2 了解 普通字符: 大小写字母、数字、标点符号及一些其它符号元字符: 在正则表达式中具有特殊意义的专用字符 1.3 层次分类 基础正则表达式扩展正…...
datawhale 大模型学习 第十二章-大模型环境影响
环境影响概述 气候变化:大语言模型(LLM)的训练和运行需要大量计算资源,导致显著的能源消耗和温室气体排放,加剧气候变化。能源消耗:训练LLM的计算过程消耗大量电力,间接增加了化石燃料的使用&a…...
Qt WebEngine模块使用(开发环境安装和程序开发)
一、Qt WebEngine Qt WebEngine_hitzsf的博客-CSDN博客 Qt WebEngine模块提供了一个Web浏览器引擎,可以轻松地将万维网上的内容嵌入到没有本机Web引擎的平台上的Qt应用程序中。Qt WebEngine提供了用于渲染HTML,XHTML和SVG文档的C 类和QML类型ÿ…...
网络体系结构 和网络原理之UDP和TCP
目录 网络分层 一. 应用层 http协议 二. 传输层 1. 介绍 2.UDP协议 (1)组成 (2)细节 3.TCP协议 (1)特性如下链接: (2)组成 (3)特点 三. 网络层 四. 数据链路层 1.介绍 2.以太网协议 3.mac地址和ip地址 五. 物理层 DNS 网络分层 一. 应用层 应用程序 现成的…...
将Android APP安装到sm8550 HDK的NVMe SSD
APP存储路径 在Android中,App在运行过程中主要访问的数据路径通常包括以下几个方面: 内部存储(Internal Storage):App会访问其私有的内部存储空间,这个空间通常位于: /data/data/<package…...
(Arcgis)Python编程批量将HDF5文件转换为TIFF格式并应用地理转换和投影信息
国家青藏高原科学数据中心下载中国1千米分辨率逐日全天候地表土壤水分数据集(2003-2022) 问题:数据在arcgis打开特别大,无法和矢量数据重合,没有设置地理坐标系 数据在网站上提供了投影信息,提示可以进行py…...
Linux:进度条的创建
目录 使用工具的简单介绍: \r : fflush : 倒计时的创建: 倒计时的工作原理: 进度条的创建: 不同场景下、打印任意长度的进度条: main .c procbor.c 测试效果: 使用工具…...
treeview
QML自定义一个TreeView,使用ListView递归 在 Qt5 的 QtQuick.Controls 2.x 中还没有 TreeView 这个控件(在 Qt6 中出了一个继承自 TableView 的 TreeView),而且 QtQuick.Controls 1.x 中的也需要配合 C model 来自定义,…...
Android开发中自定义View实现RecyclerView下划线
本篇文章主要讲解的是有关RecyclerView下划线的使用,主要有几个方法,具体如下: 第一种方式:网格分割线 public class GridDivider extends RecyclerView.ItemDecoration { private Drawable mDividerDarwable; private i…...
MySQL前百分之N问题--percent_rank()函数
PERCENT_RANK()函数 PERCENT_RANK()函数用于将每行按照(rank - 1) / (rows - 1)进行计算,用以求MySQL中前百分之N问题。其中,rank为RANK()函数产生的序号,rows为当前窗口的记录总行数 PERCENT_RANK()函数返回介于 0 和 1 之间的小数值 selectstudent_…...
【高效开发工具系列】Wolfram Alpha
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
分享7种SQL的进阶用法
推荐一款ChatGPT4.0国内站点,每日有免费使用额度,支持PC、APP、VScode插件同步使用 SQL(Structured Query Language)是一种强大的数据库查询和操作语言,它用于与关系数据库进行交互。随着数据的不断增长和应用需求的日益复杂,掌握SQL的进阶用法对于数据库管理员、数据分析…...
protobuf-go pragma.go 文件介绍
pragma.go 文件 文件位于: https://github.com/protocolbuffers/protobuf-go/blob/master/internal/pragma/pragma.go 该文件核心思想: 利用 Golang 语法机制,扩展 Golang 语言特性 目前,该文件提供以下 4 个功能: …...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
