[二分枚举]特殊密码锁
描述
有一种特殊的二进制密码锁,由n个相连的按钮组成(n<30),按钮有凹/凸两种状态,用手按按钮会改变其状态。
然而让人头疼的是,当你按一个按钮时,跟它相邻的两个按钮状态也会反转。当然,如果你按的是最左或者最右边的按钮,该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知,需要解决的问题是,你至少需要按多少次按钮,才能将密码锁转变为所期望的目标状态。
输入
两行,给出两个由0、1组成的等长字符串,表示当前/目标密码锁状态,其中0代表凹,1代表凸。
输出
至少需要进行的按按钮操作次数,如果无法实现转变,则输出impossible。
样例输入
011 000
样例输出
1
解题分析
二进制序列,按了其中一个数可以让其和其旁边的一个或者两个数取反。
其实这道题的限制条件也很容易发现,关键就在于一个分类讨论,那就是第一个按钮开始的一个确定序列。什么意思?如果前面一个按钮按与不按的状态确定了,那么后续的按钮按与不按的状态也都确定了,我们只需要枚举第一个按钮的状态即可。这个又可以联想到一个15*15方格的画家图画板的问题,或者说是点灯问题,这也是很经典的。
我们枚举第一个按钮的状态,如果二者第一个数不同,我们要想改变第一个数的状态就只有按第一个按钮或者说按第二个按钮。如果我们选择了按第一个按钮,那么后续能够影响第二个按钮状态的就只有第三个按钮了,如果不按第一个按钮,我们就得按第二个按钮,然后我们同样地也可以发现能影响第二个按钮的就只有第三个按钮了,以此类推。
代码实现
#include <iostream>
#include <cmath>
#include <iomanip>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
using namespace std;void press(string &s,int i){int l=s.size();if(i==0){s[i]=(s[i]=='1'?'0':'1');s[i+1]=(s[i+1]=='1'?'0':'1');}else if(i==l-1){s[i]=(s[i]=='1'?'0':'1');s[i-1]=(s[i-1]=='1'?'0':'1');}else{s[i]=(s[i]=='1'?'0':'1');s[i-1]=(s[i-1]=='1'?'0':'1');s[i+1]=(s[i+1]=='1'?'0':'1');}
}int main(){string cur,des;int len;int c=0;int res=1e9;cin>>cur>>des;len=cur.size();//分类讨论,第一个位置按或者不按,总共只有这两种情况//之后的每个位置都因为第一个位置按或者不按而确定string cur1=cur;press(cur,0);c++;for(int i=1;i<len;i++){if(cur[i-1]==des[i-1]){continue;}else{press(cur,i);c++;}} if(cur==des){res=min(res,c);}c=0;for(int i=1;i<len;i++){if(cur1[i-1]==des[i-1]){continue;}else{press(cur1,i);c++;}}if(cur1==des){res=min(res,c);}if(res==1e9){cout<<"impossible"<<endl;}else{cout<<res<<endl;}return 0;
}
相关文章:
[二分枚举]特殊密码锁
描述 有一种特殊的二进制密码锁,由n个相连的按钮组成(n<30),按钮有凹/凸两种状态,用手按按钮会改变其状态。 然而让人头疼的是,当你按一个按钮时,跟它相邻的两个按钮状态也会反转。当然&am…...
MT1434 找数字
题目 输入一个字符串(包含26个英文字母大小写及 . 空格,不含其他字符),把其中连续的数字作为一个整数,依次存放到一个数组中,输出这些整数的和。 格式 输入格式 输入字符串 输出格式 输出整型 样例1 输入: a12…...
2024年6月四六级考试复盘
一、考试情况 1.1四级考试情况 听力:一开始没有进入状态。总共对了9道。7.1*37.1*314.2*3 8.2 新闻听力:3/7 长对话:3/8 讲座/讲话:3/10 阅读:3.55*7 7.1*8 14.2 * 7 181.05 选词填空:保守估计7/1…...
join和left join性能比较
1、join和left join性能比较(AI生成) 在MySQL中,JOIN和LEFT JOIN的效率并不是绝对的,它们之间的性能差异取决于多种因素,如表的大小、使用的索引、查询的复杂性等。 一般来说: 如果两个表之间的连接条件能…...
Qt正则表达式
需求:对输入的内容进行限制 只能以字母或下划线开始不能以数字开始 不能有中文 字母,数字,下划线混合使用 QRegExp rx("^[A-Za-z_][A-Za-z0-9_]*$");QRegExpValidator validator(rx);QLineEdit edit;edit.setValidator(&va…...

排序-快排算法对数组进行排序
目录 一、问题描述 二、解题思路 1.初始化 2.将右侧小于基准元素移到左边 3.将左侧大于基准元素移到右边 4.重复执行上面的操作 5.对分好的左、右分区再次执行分区操作 6.最终排序结果 三、代码实现 四、刷题链接 一、问题描述 二、解题思路 快排算法实现数组排序&am…...
flink学习-容错机制
checkpoint(检查点) 在flink中最重要的容错机制,就是checkpoint机制,使用checkpoint可以将之前某个时间点的所有的状态进行保存,这个存档就是checkpoint。 检查点的保存 周期性存储保存,间隔时间可以由用…...
InfluxDB技术分享
InfluxDB是一个开源的时间序列数据库,它被设计用来处理高速写入和查询大量的时间序列数据。以下是一份关于“InfluxDB在Java开发中的使用”的三十分钟技术分享内容概要: 1. 引言 (2分钟) 介绍时间序列数据和时间序列数据库的概念。引入InfluxDB的特点和…...

Windows10安装配置Docker客户端和WSL2与Hyper-V虚拟机
一、需求说明 需要在Windows系统中安装配置Docker的客户端,方便直接管理配置docker镜像容器内容。 二、Windows10安装Docker客户端步骤 2.1、下载安装Docker客户端 对于Windows 10以下的用户,推荐使用Docker Toolbox Windows安装文件:http://mirrors.aliyun.com/docker-…...

EIQ-ABC 分析法在配送中心储位分配中的应用
配送中心运作效率的高低主要取决于仓储业务流程的作业效率,在配送作业流程中,储位分配的是否合理性成为影响配送运作效率的重要因素。为实现储位的合理分配,提出通过对订单信息的分析,并应用 EIQ-ABC 分析法,以此实现缩…...

【安装笔记-20240613-Linux-在 OpenWrt 的 LuCI界面支持命令行调试】
安装笔记-系列文章目录 安装笔记-20240613-Linux-在 OpenWrt 的 LuCI界面支持命令行调试 文章目录 安装笔记-系列文章目录安装笔记-20240613-Linux-在 OpenWrt 的 LuCI界面支持命令行调试 前言一、软件介绍名称:ttyd主页官方介绍特点 二、安装步骤测试版本…...
React小记(一)_基础部分
1、项目搭建与结构 2、类组件和函数组件 主要区别:1、函数组件没有生命周期2、函数组件没有this指向3、函数组件没有状态4、函数组件通过hooks实现各种操作5、props在函数的第一个参数接收6、函数体相当于类组件的render函数import React from reactfunction App()…...

40、基于深度学习的线性预测设计(matlab)
1、原理及流程 深度学习的线性预测是一种利用深度神经网络模型进行线性回归预测的方法。其设计原理主要基于神经网络的层次化特性,利用多层感知器(MLP)等模型进行特征学习和非线性变换,从而提高线性预测的准确性。 设计流程如下…...
【初体验 threejs】【学习】【笔记】hello,正方体 3!
前言 为了满足工作需求,我已着手学习 Three.js,并决定详细记录这一学习过程。在此旅程中,如果出现理解偏差或有其他更佳的学习方法,请大家不吝赐教,在评论区给予指正或分享您的宝贵建议,我将不胜感激。 项…...

第04章:IDEA的安装与使用
第04章:随堂复习与企业真题(IDEA安装与使用) 一、随堂复习 1. IDEA的认识 IDEA(集成功能强大、符合人体工程学(设置人性化))Eclipse 2. IDEA的下载、安装、卸载 卸载:使用控制面板进行卸载,…...
[原创][Delphi多线程]使用TMonitor, TEvent和TQueue配合实现TThreadQueue的经典使用案例.
[简介] 常用网名: 猪头三 出生日期: 1981.XX.XX QQ: 643439947 个人网站: 80x86汇编小站 https://www.x86asm.org 编程生涯: 2001年~至今[共22年] 职业生涯: 20年 开发语言: C/C、80x86ASM、PHP、Perl、Objective-C、Object Pascal、C#、Python 开发工具: Visual Studio、Delph…...

6.12ctf练习
[西湖论剑 2022]Node Magical Login 源码在这里:GitHub - CTF-Archives/2022-xhlj-web-node_magical_login: A web challenge in 2022 西湖论剑大赛打开 打开环境是个登录框,先进行了扫描和抓包都没有看见什么有价值的东西,看源码 大致连接…...

海豚调度异常处理: 使用 arthas 在内存中删除启动失败的工作流
💡 本系列文章是 DolphinScheduler 由浅入深的教程,涵盖搭建、二开迭代、核心原理解读、运维和管理等一系列内容。适用于想对 DolphinScheduler了解或想要加深理解的读者。祝开卷有益。大数据学习指南 大家好,我是小陶,DolphinSch…...
在Qt中,QSerialPort::write(data) 和 readAll() 有什么关联和联系
在Qt中,QSerialPort::write(data) 和 readAll() 是与串行通信相关的两个不同的函数,它们属于 QSerialPort 类。这两个函数在串行通信中扮演不同的角色,但它们之间存在一定的联系: QSerialPort::write(data) 这个函数用于将数据发…...

第 2 章:Spring Framework 中的 IoC 容器
控制反转(Inversion of Control,IoC)与 面向切面编程(Aspect Oriented Programming,AOP)是 Spring Framework 中最重要的两个概念,本章会着重介绍前者,内容包括 IoC 容器以及容器中 …...

网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
在Ubuntu24上采用Wine打开SourceInsight
1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...