【蓝桥杯集训·每日一题】AcWing 2058. 笨拙的手指
文章目录
- 一、题目
- 1、原题链接
- 2、题目描述
- 二、解题报告
- 1、思路分析
- 2、时间复杂度
- 3、代码详解
- 三、知识风暴
- 哈希表
- 秦九韶算法
一、题目
1、原题链接
2058. 笨拙的手指
2、题目描述
奶牛贝茜正在学习如何在不同进制之间转换数字。
但是她总是犯错误,因为她无法轻易的用两个前蹄握住笔。
每当贝茜将数字转换为一个新的进制并写下结果时,她总是将其中的某一位数字写错。
例如,如果她将数字 14 转换为二进制数,那么正确的结果应为 1110,但她可能会写下 0110 或 1111 。
贝茜不会额外添加或删除数字,但是可能会由于写错数字的原因,写下包含前导 0 的数字。
给定贝茜将数字 N 转换为二进制数字以及三进制数字的结果,请 确定 N 的正确初始值(十进制表示)。
输入格式
第一行包含 N 的二进制表示,其中一位是错误的。
第二行包含 N 的三进制表示,其中一位是错误的。
输出格式
输出正确的 N 的值。
数据范围
0≤N≤109,且存在唯一解。
输入样例:
1010 212输出样例:
14样例解释
14 在二进制下的正确表示为 1110,在三进制下的正确表示为 112。
二、解题报告
1、思路分析
思路来源:y总视频讲解
y总yyds
(1)将数N的二进制表示下可能写错的每种情况的十进制下的数值存入哈希表中。
(2)将数N的三进制表示下的每种写错的情况的十进制下的数值在哈希表中进行查找,如果该数值出现过,则该数就是N的十进制表示,输出即可。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
使用STL中unordered_set
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
//使用秦九韶算法,将y进制下的数x转化为十进制
int ten(string x,int y){int ans=0;for(int i=0;i<x.size();i++){ans=ans*y+x[i]-'0';}return ans;
}
int main(){string n,m;cin>>n>>m;unordered_set<int> s;for(int i=0;i<n.size();i++){string t=n;t[i]^=1; //改变第i位数,0变1,1变0if(t[0]=='0'&&t.size()>1) continue; //如果数字存在前导0,则不合法,直接跳过s.insert(ten(t,2)); //将写错后的数字在十进制下的数值放入哈希表}for(int i=0;i<m.size();i++){for(int j=0;j<3;j++){ //枚举第i位数字可能的写错情况,然后再在哈希表中查找该数的十进制下数值是否出现过if(m[i]-'0'!=j){ string tmp=m;tmp[i]=j+'0';if(tmp[0]=='0'&&tmp.size()>1) continue; //同上if(s.count(ten(tmp,3))){ //如果该数的十进制的值在哈希表存在过,直接输出,该数就是答案cout<<ten(tmp,3);}}}}return 0;
}
手写哈希表
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int N=103;
int h[N];
//哈希表开放寻址法,如果x存在,返回x的位置,否则返回x应该插入的位置
int find(int x){int t=(x%N+N)%N;while(h[t]!=-1&&h[t]!=x){t++;if(t==N) t=0;}return t;
}
//使用秦九韶算法,将y进制下的数x转化为十进制
int ten(string x,int y){int ans=0;for(int i=0;i<x.size();i++){ans=ans*y+x[i]-'0';}return ans;
}int main(){string n,m;cin>>n>>m;memset(h,-1,sizeof h);for(int i=0;i<n.size();i++){string t=n;t[i]^=1; //改变第i位数,0变1,1变0if(t[0]=='0'&&t.size()>1) continue; //如果数字存在前导0,则不合法,直接跳过h[find(ten(t,2))]=ten(t,2); //将写错后的数字在十进制下的数值放入哈希表}for(int i=0;i<m.size();i++){for(int j=0;j<3;j++){ //枚举第i位数字可能的写错情况,然后再在哈希表中查找该数的十进制下数值是否出现过if(m[i]-'0'!=j){ string tmp=m;tmp[i]=j+'0';if(tmp[0]=='0'&&tmp.size()>1) continue; //同上if(h[find(ten(tmp,3))]!=-1){ //如果该数的十进制的值在哈希表存在过,直接输出,该数就是答案cout<<ten(tmp,3);}}}}return 0;
}
三、知识风暴
哈希表
- 哈希表的增删改查的时间复杂度为O(1)。
- C++中STL的
unordered_set和unordered_map底层就是使用哈希结构实现的。秦九韶算法
- 参考百度百科
秦九韶算法是一种多项式的简化算法。
具体做法是将多项式
改写为:
先计算内层的数值然后依次由内向外进行拓展。- 针对本题我们可以使用其来进行计算不同进制转十进制的结果。
例如:求二进制1010的十进制
二进制1010转换为10进制的算式可以写成1x23+0x22+1x21+0x20,类比上述多项式,2即为多项式中的x,二进制的每位数字则是多项式的系数,而我们在本题中二进制数是按字符串(记为s)读入的,所以将其每位数字记为s[i]。根据上述算法可知,我们最终算的每层均是s[i]*x+s[i+1],而在计算下一层时,上一层的结果更新成了下一层x前面的系数,所以我们将上一层的结果记录到临时变量ans中,然后按照公式s[i]*x+s[i+1]依次向外扩展,直到遍历完所有数字,ans就是多项式的值,也就是我们要求的十进制的数值。所以据此我们可以总结出计算本题将
x进制转换为十进制数值的代码int ans=0; //ans存储每层的结果,最终ans的值为最外层的值,也就是多项式的值 for(int i=0;i<s.size();i++){ans=ans*x+s[i]-'0'; //i可以理解为层数,第0层只有第一个数字,而最后一层就是整个多项式的值 }
相关文章:
【蓝桥杯集训·每日一题】AcWing 2058. 笨拙的手指
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴哈希表秦九韶算法一、题目 1、原题链接 2058. 笨拙的手指 2、题目描述 奶牛贝茜正在学习如何在不同进制之间转换数字。 但是她总是犯错误,因为她无法轻易的用两…...
运维排查篇 | Linux 连接跟踪表满了怎么处理
nf_conntrack (在老版本的 Linux 内核中叫 ip_conntrack )是一个内核模块,用于跟踪一个网络连接的状态 一旦内核 netfilter 模块 conntrack 相关参数配置不合理,导致 nf_conntrack table full ,就会出现丢包、连接无法建立的问题 这个问题其…...
docker网络基
本文简单介绍下,容器之间的网络访问、容器与宿主机之间的网络访问、宿主机上有哪些网络接口。lolocal的简写,本地回环地址,127.0.0.1,它代表本地虚拟设备接口,默认被看作是永远不会宕掉的接口eth0ethernet的简写&#…...
C++:谈谈单例模式的多种实现形式
文章目录实现 1:静态成员实现 2:atexit 懒汉模式实现 3:原子变量 懒汉模式实现4:atexit 饿汉模式* 实现5:magic static单例模式:保证一个类仅有一个实例,并提供一个该实例的全局访问点。 稳…...
【Spring Cloud Alibaba】007-Nacos 配置*
【Spring Cloud Alibaba】007-Nacos 配置* 文章目录【Spring Cloud Alibaba】007-Nacos 配置*一、概述1、概述2、对比 spring cloud config二、基本使用1、在管理界面新建配置2、启动权限3、 搭建 nacos-config 服务第一步:引入依赖第二步:修改 yaml 配置…...
《安富莱嵌入式周报》第304期:开源硬件耳机设计,AI单片机STM32N6已确定为M55内核,另外还有新品STM32H5, H50X, H7R, H7S发布
往期周报汇总地址:嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 更新一期视频教程: 第6期ThreadX视频教程:图文并茂吃透RTOS运行机制,任务管理&…...
vuex篇
1.简介(1)vuexVuex 是一个专为 Vue.js 应用程序开发的状态管理模式 库vuex是为vue.js开发的状态管理模式、组件状态集中管理(2)单页面数据流状态发生变化, 视图就重新渲染state发生变化时, 导致view视图发生改变, 视图通过操作action行为, 又会使得state状态发生变化(3)使用场…...
嵌入式开发:在嵌入式应用程序中混合C和C++
许多嵌入式应用程序仍使用c语言编写,但越来越多的嵌入式开发人员现在使用C语言编写程序。某些应用程序甚至共享这两种语言。这有意义吗?C是嵌入式应用中最常用的编程语言。多年来,人们一直期待着向C过渡,但过渡速度相当缓慢。但是࿰…...
【2023/图对比/增强】MA-GCL: Model Augmentation Tricks for Graph Contrastive Learning
如果觉得我的分享有一定帮助,欢迎关注我的微信公众号 “码农的科研笔记”,了解更多我的算法和代码学习总结记录。或者点击链接扫码关注【2023/图对比/增强】MA-GCL: Model Augmentation Tricks for Graph Contrastive Learning 【2023/图对比/增强】MA-…...
TensorBoard自定义修改单条及多条曲线颜色
在深度学习可视化训练过程中,曲线颜色是随机的,想要将好看的曲线颜色图放到论文中,就得自定义曲线颜色,具体方法见下文。 目录一、下载svg文件二、修改svg文件三、修改后曲线颜色对比四、总结一、下载svg文件 在TensorBoard界面中…...
时间和空间复杂度
文章目录 前言 一、算法效率 1.如何评判算法效率? 2.算法的复杂度 二、时间复杂度 1.时间复杂度的定义 2. 大O的渐进表示法 三、空间复杂度 总结 前言 本文章讲解时间与空间复杂度 提示:以下是本篇文章正文内容,下面案例可供参考 一、算法…...
关于Linux下调试
关于Linux下调试 无论是内核(操作系统)还是应用程序,都存在需要调试的情况。 所谓工欲善其事,必先利其器。一个好的称手的工具,对于快速分析问题、定位问题,提高效率,非常有帮助。 除了工具&a…...
理解TP、FP、TN、FN
概念定义 按照常用的术语,将两个类分别称为正类 (positive) 和 负类 (negative)。使用数学表示: 1表示正类 , -1 表示负类。 正类通常是少数类,即样本较少的类(例如有缺陷的零件) 负类通常是多数类&#x…...
软考中级有用吗
当然有用了! 软考“简历”:计算机软件资格考试在全国范围内已经实施了二十多年,近十年来,考试规模持续增长,截止目前,累计报考人数约有五百万人。该考试由于其权威性和严肃性,得到了社会各界及用人单位的广泛认同&…...
计算机网络之IP协议(详解
网络层主管地址管理与路由选择。而IP协议就是网络层中一个非常重要的协议。它的作用就是在复杂的网络环境中确定一个合适的路径。IP协议头格式4位版本号(version) 指定IP协议的版本,目前只有两个版本:IP v4和IP v6.对于IP v4来说,这个值就是4…...
Kubernetes之探针probe
deployment只保证pod的状态为running。如果pod状态是running,但是里面丢失了文件,导致用户不能访问数据,则deployment是不管用的,此时就需要probe来检测pod是否正常工作。 probe是定义在容器里的,可以理解为容器里加的…...
高性能低功耗4口高速USB2.0 HUB NS1.1S 兼容FE1.1
NS1.1S是一款高性能、低功耗4口高速 USB2.0 HUB 控制器,上行端口兼容高速 480MHz和全速12MHz两种模式,4个下行端口兼容高速480MHz、全速12MHz、低速1.5MHz三种模式。 NS1.1S采用状态机单事务处理架构,而非单片机架构,多个事务缓冲…...
通过VS Code轻松连接树莓派
如果您正在使用树莓派作为开发平台,那么通过远程连接VS Code到树莓派是非常方便的一种方法。这样,您可以在Windows或macOS等计算机上开发和测试代码,而不必在树莓派上进行。 以下是通过VS Code远程连接到树莓派的步骤: 1.安装Re…...
图纸等敏感文件数据外发时 如何确保效率和安全性?
很多企业随着业务的发展,需要频繁的与外部供应商、合作伙伴之间进行数据的交换和使用。尤其是制造型企业,可能每天都要与几十、上百家供应商及合作伙伴进行产品数据交换。目前,大多数企业已经在内部实施了PDM/PLM系统,实现了对组织…...
2023年CDGA考试-第4章-数据架构(含答案)
2023年CDGA考试-第4章-数据架构(含答案) 单选题 1.请从下列选项中选择不属于数据架构师职责的选项 A.确保数据架构和企业战略及业务架构一致 B.提供数据和组件的标准业务词汇 C.设计企业数据模型 D.整合企业数据架构蓝图 答案 C 2.请从下列选项中选择不属于企业数据架构…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

