AcWing 4868. 数字替换(DFS + 剪枝优化)
AcWing 4868. 数字替换(DFS + 剪枝优化)
- 一、问题
- 二、思路
- 三、代码
一、问题

二、思路
题目中要求变换次数最小,其实第一印象应该是贪心,即我们每一次都去成各位中最大的那个数字。但是这个想法很容易推翻。因为你这次乘了一个最大的数,很有可能导致在最后的结果每一位都比较小,相反如果你这次乘了一个较小的数,可能最后的结果中有一位很大。也就是说,你只能保证当前操作是最优的,但是往后多看几步的话,就不一定是最优的了。
所以我们只能暴力枚举了。
枚举的过程中,我们需要存储一下这个数字都有哪几位,然后从大到小开始枚举,这个操作属于剪枝优化中的搜索顺序优化。
另外,我们还可以进行两次最优性剪枝。即,如果当前的操作次数已经大于我们之前算出来的答案了,我们就不需要去进行后续的操作了,直接舍去。
其次,还有一个最优性剪枝比较难想。
我们很容易观察出,n位数乘以一个1位数,最终的结果位数最多是n + 1的。证明也很简单,我们可以让每一位都是9,再去乘1个9,即使是这样,最后的位数依旧是最多多1。
假设当前有cntcntcnt位,操作次数是stepstepstep,目标是nnn位,那么我们还需要进行的最小操作次数是n−cntn-cntn−cnt。那么最终总的操作次数一定是大于等于step+n−cntstep+n-cntstep+n−cnt的。如果这个数是大于我们之前的最优解的话,也可以直接舍去。
三、代码
#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;
ll n, x, ans = INF;void dfs(ll x, int step)
{bool st[12] = {0};int cnt = 0;for(ll y = x; y; y /= 10){cnt ++;st[y % 10] = true;}if(n - cnt + step >= ans)return;if(step >= ans)return;if(cnt > n)return;if(cnt == n){ans = step;return;}for(int i = 9; i >= 2; i -- ){if(st[i])dfs(i * x, step + 1);}
}void solve()
{cin >> n >> x;dfs(x, 0);if(ans == INF){cout << -1 << endl;}else{cout << ans << endl;}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}
相关文章:
AcWing 4868. 数字替换(DFS + 剪枝优化)
AcWing 4868. 数字替换(DFS 剪枝优化)一、问题二、思路三、代码一、问题 二、思路 题目中要求变换次数最小,其实第一印象应该是贪心,即我们每一次都去成各位中最大的那个数字。但是这个想法很容易推翻。因为你这次乘了一个最大的…...
【教学典型案例】01.redis只管存不管删除让失效时间删除的问题
目录一:背景介绍二:redis1)redis数据类型①String(字符串)②Hash(哈希)③List(列表)④Set(集合)2)缓存同步①设置有效期②同步双写③异步通知3&am…...
电话号码管理
电话号码管理 文章目录 电话号码管理综述链表结构initcreatedeleteallfreeANSI颜色转义颜色列表如下:字背景颜色范围:40--49 字颜色: 30--39输出特效格式控制:光标位置等的格式控制:Makefile顶层Makefilescripts Makefilesearch main init include display delete create all…...
Shell 教程
Shell 是一个用 C 语言编写的程序,它是用户使用 Linux 的桥梁。Shell 既是一种命令语言,又是一种程序设计语言。 Shell 是指一种应用程序,这个应用程序提供了一个界面,用户通过这个界面访问操作系统内核的服务。 Ken Thompson 的…...
Shader 阴影
阴影生成原理 以平行光为例,把相机移动到光源位置,计算阴影映射纹理(shadowmap),这张shadowmap本质上是一张深度图,它记录了从该光源的位置出发、能看到的场景中距离它最近的表面位置(深度信息&…...
【冲刺蓝桥杯的最后30天】day2
大家好😃,我是想要慢慢变得优秀的向阳🌞同学👨💻,断更了整整一年,又开始恢复CSDN更新,从今天开始更新备战蓝桥30天系列,一共30天,如果对你有帮助或者正在备…...
docker系列1:docker安装
传送门 docker官网地址: Docker: Accelerated, Containerized Application Development 安装地址:Install Docker Engine docker hub地址 docker hub:Docker 安装步骤 前置条件 由于安装docker,需要根据操作系统版本选择…...
内核角度谈谈Linux进程和线程
目录前言内核对进程和线程的表示创建进程的过程创建线程的过程创建进程和线程的异同揭秘 do_fork 系统调用结论前言 昨天面试的时候,面试官问我了个平平淡淡的问题–>“聊聊Linux中进程和线程”; 相比大家不管是在考试还是面试中或多或少都遇到过这个问题&…...
【mmdeploy部署系列】使用Tensorrt加速部署mmpose人体姿态库
【mmdeploy部署系列】使用Tensorrt加速部署mmpose人体姿态库0.引言1.安装mmcv2.使用mmpose(1)安装mmpose(2)运行mmpose3.使用mmdeploy(1)安装ppl.cv(2)编译安装mmdeploy(…...
IDEA 每次新建工程都要重新配置 Maven 解决方案
IDEA 每次新建工程都要重新配置 Maven 解决方案 IDEA 每次新建工程都要重新配置 Maven,是一件相当浪费时间的事情。这是因为在创建一个项目后,在 File -> Settings -> Build,Execution,Deployment -> Build Tools -> Maven下配置了 Maven h…...
【C++修炼之路】25.哈希应用--布隆过滤器
每一个不曾起舞的日子都是对生命的辜负 布隆过滤器前言一.布隆过滤器提出二.布隆过滤器概念三. 布隆过滤器的操作3.1 布隆过滤器的插入3.2 布隆过滤器的查找3.3 布隆过滤器的删除四.布隆过滤器的代码4.1 HashFunc的仿函数参考4.2 BloomFilter.h五.布隆过滤器的优缺点六.布隆过滤…...
linux入门---权限
目录标题什么是权限人的分类为什么会有所属组查看文件属性文件的分类如何查看权限文件不同权限的表现rwx权限修改八进制权限修改umask有关内容文件中人的修改目录不同权限的表现rwx什么是权限 首先来看一个例子:比如说我没有爱奇艺的vip,那么我也就没有…...
Unity记录2.1-动作-多段跳、蹬墙跳、墙体滑落
文章首发及后续更新:https://mwhls.top/4450.html,无图/无目录/格式错误/更多相关请至首发页查看。 新的更新内容请到mwhls.top查看。 欢迎提出任何疑问及批评,非常感谢! 汇总:Unity 记录 摘要:实现跳跃、蹬…...
Spring Boot结合IDEA自带Maven插件快速切换profile | Spring Cloud 10
一、前言 IDEA是目前 Java 开发者中使用最多的开发工具,它有着简约的设计风格,强大的集成工具,便利的快捷键。 在项目项目整个开发运维周期中,我们的的项目往往需要根据不同的环境,使用不同的文件配置。 比如以下部…...
ES 7.7.0 数据迁移
本文使用 elasticdump 做数据迁移,支持在线和离线俩种方式,适用于数据量比较小的情况。 1、Node 安装 由于elasticdump 依赖于 node,首先需要安装下node。 1.1、 Linux 安装 $ wget https://nodejs.org/dist/v10.15.0/node-v10.15.0-linu…...
【玩转c++】vector讲解和模拟底层实现
本期主题:vector的讲解和模拟实现博客主页:小峰同学分享小编的在Linux中学习到的知识和遇到的问题小编的能力有限,出现错误希望大家不吝赐vector的介绍及使用1.1vector的介绍vector其实就是一个数组的模板 ,存放的数据可以改变而已…...
基本类型、包装类型、引用类型、String等作为实参传递后值会不会改变?
看了半天帖子,讲得乱七八糟,坑死了 [1] 先说结论 基本类型、包装类型、String类型作为参数传递之后,在方法里面修改他们的值,原值不会改变!引用类型不一定,要看是怎么修改它的。 [2] 为什么基本类型、包装类…...
Tomcat服务器配置以及问题解决方案
文章目录01 Tomcat简介02 Tomcat的安装03 Tomcat的使用启动Tomcat服务器 (解决一闪而过)测试 Tomcat 是否启动Tomcat 服务器的关闭04 Tomcat的配置配置端口控制台配置(乱码解决)部署工程到Tomcat中01 Tomcat简介 Tomcat是一款开源…...
【Node.js】HTTP协议、HTTP的请求报文和响应报文
HTTP协议、HTTP的请求报文和响应报文HTTP协议HTTP主要特点HTTP的请求报文和响应报文请求报文请求行请求消息头空行请求体响应报文响应状态行响应消息头空行响应体总结HTTP协议 HTTP 全称为超文本传输协议,是用于从WWW服务器传输超文本到本地浏览器的传送协议&#…...
CodeForce 455A. Boredom
题目链接 CodeForce 455A. Boredom 思路 因为跟序列的下标无关,所以先对数组a排个序。那么每次选择只会影响两侧的元素。 记号 令dp[i]dp[i]dp[i]表示排序后a[1..i]a[1..i]a[1..i]能够获得的最大点数。 但是这样不足以区分是否当前元素可以被使用,所…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
Unity VR/MR开发-VR开发与传统3D开发的差异
视频讲解链接:【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...
yaml读取写入常见错误 (‘cannot represent an object‘, 117)
错误一:yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因,后面把yaml.safe_dump直接替换成yaml.dump,确实能保存,但出现乱码: 放弃yaml.dump,又切…...
Canal环境搭建并实现和ES数据同步
作者:田超凡 日期:2025年6月7日 Canal安装,启动端口11111、8082: 安装canal-deployer服务端: https://github.com/alibaba/canal/releases/1.1.7/canal.deployer-1.1.7.tar.gz cd /opt/homebrew/etc mkdir canal…...
