当前位置: 首页 > news >正文

【蓝桥杯集训·每日一题】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_setunordered_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、题目描述 奶牛贝茜正在学习如何在不同进制之间转换数字。 但是她总是犯错误&#xff0c;因为她无法轻易的用两…...

运维排查篇 | Linux 连接跟踪表满了怎么处理

nf_conntrack (在老版本的 Linux 内核中叫 ip_conntrack )是一个内核模块&#xff0c;用于跟踪一个网络连接的状态 一旦内核 netfilter 模块 conntrack 相关参数配置不合理&#xff0c;导致 nf_conntrack table full &#xff0c;就会出现丢包、连接无法建立的问题 这个问题其…...

docker网络基

本文简单介绍下&#xff0c;容器之间的网络访问、容器与宿主机之间的网络访问、宿主机上有哪些网络接口。lolocal的简写&#xff0c;本地回环地址&#xff0c;127.0.0.1&#xff0c;它代表本地虚拟设备接口&#xff0c;默认被看作是永远不会宕掉的接口eth0ethernet的简写&#…...

C++:谈谈单例模式的多种实现形式

文章目录实现 1&#xff1a;静态成员实现 2&#xff1a;atexit 懒汉模式实现 3&#xff1a;原子变量 懒汉模式实现4&#xff1a;atexit 饿汉模式* 实现5&#xff1a;magic static单例模式&#xff1a;保证一个类仅有一个实例&#xff0c;并提供一个该实例的全局访问点。 稳…...

【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 服务第一步&#xff1a;引入依赖第二步&#xff1a;修改 yaml 配置…...

《安富莱嵌入式周报》第304期:开源硬件耳机设计,AI单片机STM32N6已确定为M55内核,另外还有新品STM32H5, H50X, H7R, H7S发布

往期周报汇总地址&#xff1a;嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 更新一期视频教程&#xff1a; 第6期ThreadX视频教程&#xff1a;图文并茂吃透RTOS运行机制&#xff0c;任务管理&…...

vuex篇

1.简介(1)vuexVuex 是一个专为 Vue.js 应用程序开发的状态管理模式 库vuex是为vue.js开发的状态管理模式、组件状态集中管理(2)单页面数据流状态发生变化, 视图就重新渲染state发生变化时, 导致view视图发生改变, 视图通过操作action行为, 又会使得state状态发生变化(3)使用场…...

嵌入式开发:在嵌入式应用程序中混合C和C++

许多嵌入式应用程序仍使用c语言编写&#xff0c;但越来越多的嵌入式开发人员现在使用C语言编写程序。某些应用程序甚至共享这两种语言。这有意义吗?C是嵌入式应用中最常用的编程语言。多年来&#xff0c;人们一直期待着向C过渡&#xff0c;但过渡速度相当缓慢。但是&#xff0…...

【2023/图对比/增强】MA-GCL: Model Augmentation Tricks for Graph Contrastive Learning

如果觉得我的分享有一定帮助&#xff0c;欢迎关注我的微信公众号 “码农的科研笔记”&#xff0c;了解更多我的算法和代码学习总结记录。或者点击链接扫码关注【2023/图对比/增强】MA-GCL: Model Augmentation Tricks for Graph Contrastive Learning 【2023/图对比/增强】MA-…...

TensorBoard自定义修改单条及多条曲线颜色

在深度学习可视化训练过程中&#xff0c;曲线颜色是随机的&#xff0c;想要将好看的曲线颜色图放到论文中&#xff0c;就得自定义曲线颜色&#xff0c;具体方法见下文。 目录一、下载svg文件二、修改svg文件三、修改后曲线颜色对比四、总结一、下载svg文件 在TensorBoard界面中…...

时间和空间复杂度

文章目录 前言 一、算法效率 1.如何评判算法效率&#xff1f; 2.算法的复杂度 二、时间复杂度 1.时间复杂度的定义 2. 大O的渐进表示法 三、空间复杂度 总结 前言 本文章讲解时间与空间复杂度 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下面案例可供参考 一、算法…...

关于Linux下调试

关于Linux下调试 无论是内核&#xff08;操作系统&#xff09;还是应用程序&#xff0c;都存在需要调试的情况。 所谓工欲善其事&#xff0c;必先利其器。一个好的称手的工具&#xff0c;对于快速分析问题、定位问题&#xff0c;提高效率&#xff0c;非常有帮助。 除了工具&a…...

理解TP、FP、TN、FN

概念定义 按照常用的术语&#xff0c;将两个类分别称为正类 (positive) 和 负类 (negative)。使用数学表示&#xff1a; 1表示正类 &#xff0c; -1 表示负类。 正类通常是少数类&#xff0c;即样本较少的类&#xff08;例如有缺陷的零件&#xff09; 负类通常是多数类&#x…...

软考中级有用吗

当然有用了&#xff01; 软考“简历”&#xff1a;计算机软件资格考试在全国范围内已经实施了二十多年&#xff0c;近十年来,考试规模持续增长&#xff0c;截止目前,累计报考人数约有五百万人。该考试由于其权威性和严肃性&#xff0c;得到了社会各界及用人单位的广泛认同&…...

计算机网络之IP协议(详解

网络层主管地址管理与路由选择。而IP协议就是网络层中一个非常重要的协议。它的作用就是在复杂的网络环境中确定一个合适的路径。IP协议头格式4位版本号(version) 指定IP协议的版本&#xff0c;目前只有两个版本&#xff1a;IP v4和IP v6.对于IP v4来说&#xff0c;这个值就是4…...

Kubernetes之探针probe

deployment只保证pod的状态为running。如果pod状态是running&#xff0c;但是里面丢失了文件&#xff0c;导致用户不能访问数据&#xff0c;则deployment是不管用的&#xff0c;此时就需要probe来检测pod是否正常工作。 probe是定义在容器里的&#xff0c;可以理解为容器里加的…...

高性能低功耗4口高速USB2.0 HUB NS1.1S 兼容FE1.1

NS1.1S是一款高性能、低功耗4口高速 USB2.0 HUB 控制器&#xff0c;上行端口兼容高速 480MHz和全速12MHz两种模式&#xff0c;4个下行端口兼容高速480MHz、全速12MHz、低速1.5MHz三种模式。 NS1.1S采用状态机单事务处理架构&#xff0c;而非单片机架构&#xff0c;多个事务缓冲…...

通过VS Code轻松连接树莓派

如果您正在使用树莓派作为开发平台&#xff0c;那么通过远程连接VS Code到树莓派是非常方便的一种方法。这样&#xff0c;您可以在Windows或macOS等计算机上开发和测试代码&#xff0c;而不必在树莓派上进行。 以下是通过VS Code远程连接到树莓派的步骤&#xff1a; 1.安装Re…...

图纸等敏感文件数据外发时 如何确保效率和安全性?

很多企业随着业务的发展&#xff0c;需要频繁的与外部供应商、合作伙伴之间进行数据的交换和使用。尤其是制造型企业&#xff0c;可能每天都要与几十、上百家供应商及合作伙伴进行产品数据交换。目前&#xff0c;大多数企业已经在内部实施了PDM/PLM系统&#xff0c;实现了对组织…...

2023年CDGA考试-第4章-数据架构(含答案)

2023年CDGA考试-第4章-数据架构(含答案) 单选题 1.请从下列选项中选择不属于数据架构师职责的选项 A.确保数据架构和企业战略及业务架构一致 B.提供数据和组件的标准业务词汇 C.设计企业数据模型 D.整合企业数据架构蓝图 答案 C 2.请从下列选项中选择不属于企业数据架构…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...