[二分枚举]特殊密码锁
描述
有一种特殊的二进制密码锁,由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 容器以及容器中 …...
构造函数、实例、原型对象三者之间的关系
在 JavaScript 中,构造函数、实例和原型对象之间有着密切的关系。下面是对它们之间关系的详细解析和代码示例: 构造函数:构造函数是一个特殊的函数,用于创建对象的模板。它定义了对象的属性和方法。构造函数通常以大写字母开头&a…...
人工智能抢走了他们的工作。现在他们得到报酬,让它听起来像人类
人工智能抢走了他们的工作。现在他们得到报酬,让它听起来像人类 如果你担心人工智能会如何影响你的工作,那么广告文案的世界或许能让你窥见未来。 作家本杰明米勒(化名)在2023年初非常红火。他领导了一个由60多名作家和编辑组成的团队,发表博…...
大模型微调出错的解决方案(持续更新)
大家好,我是herosunly。985院校硕士毕业,现担任算法研究员一职,热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算法…...
企业多云策略的优势与实施指南
企业在选择云服务提供商时,常见的选项包括亚马逊AWS、微软Azure、谷歌云GCP、阿里云、腾讯云和华为云。为了避免过度依赖单一供应商,许多企业选择采用多云策略,这样可以充分利用不同云服务的优势,同时避免重复工作和其他额外的工作…...
vue分页
先看效果 再看代码 <!-- 分页 --><div v-if"pageParams.pageCount > 1" class"flex justify-end mt-6"><n-paginationv-model:page"pageParams.page" v-model:page-size"pageParams.pageSize" :page-count"pa…...
服务器上设置pnpm环境变量
首先,确认 pnpm 是否已经安装: ls /www/server/nodejs/v20.10.0/bin/pnpm如果输出包含 pnpm,那么说明 pnpm 已经安装。 如果没有看到 pnpm,你可能需要重新安装它: npm install -g pnpm接下来,确保 PATH …...
Java中BIO、NIO、AIO详解
参考: https://blog.csdn.net/s2152637/article/details/98777686 https://blog.csdn.net/bigorsmallorlarge/article/details/137292669 1、几个基本概念 Java中IO模型简介 在Java中,主要有三种IO模型,分别是: 同步阻塞IO&…...
cloud_enum:一款针对不同平台云环境安全的OSINT工具
关于cloud_enum cloud_enum是一款功能强大的云环境安全OSINT工具,该工具支持AWS、Azure和Google Cloud三种不同的云环境,旨在帮助广大研究人员枚举目标云环境中的公共资源,并尝试寻找其中潜在的安全威胁。 功能介绍 当前版本的cloud_enum支…...
图像的对比度和亮度
目标 访问像素值用0来初始化矩阵cv::saturate_cast像素转换提高一张图像的亮度 原理 图像处理 图像变换可以被视作两个步骤: 点操纵(像素转换)相邻区域转换(以面积为基础) 像素转换 在这种图像处理的转换过程中…...
手撕设计模式——计划生育之单例模式
1.业务需求 大家好,我是菠菜啊。80、90后还记得计划生育这个国策吗?估计同龄的小伙伴们,小时候常常被”只生一个好“”少生、优生“等宣传标语洗脑,如今国家已经放开并鼓励生育了。话说回来,现实生活中有计划生育&…...
电影网站怎么做的/腾讯广告平台
查询与匹配 Stream提供了allMatch(), anyMatch(), noneMatch(), findFirst(), findAny()功能,用于实现条件匹配与查询,一起来看看。 anyMatch() anyMatch用于确认“有没有符合条件的元素?” 有->true->至少有一个符合要求 没有->…...
乌鲁木齐公司网站建设/百度热线客服24小时
学生成绩表(stuscore): 姓名:name 课程:subject 分数:score 学号:stuid 张三 数学 89 1 张三 语文 80 1 张三 英语 70 1 李四 数学 90 2 李四 语文 70 2 李四 英语 80 2 创建表SET ANSI_NU…...
导航网站的广告怎么做的/小程序开发一个多少钱啊
pymysql.err.InterfaceError: (0, ‘’)解决办法 导致这个错误的原因是通过pymysql连接MySQL,没有关闭连接的操作,所以短时间内不会出问题,长时间保持这个连接会出现连接混乱。虽然看着自己的代码没错,还是会报 pymysql.err.Inte…...
做网站+广告费+步骤/齐三seo顾问
Linux 定期切割Tomcat catalina.out和清理log日志Tomcat日志的清理有两种情况第一种:日志本身就以日期保存,每天一个文件的,比如localhost.2020-04-24.log;这类日志只需要卡一个定时器,定期删除即可。第二种࿱…...
合作社做网站有用吗/百度认证中心
Your Mono toolset 到这里的时候你可能已经放弃了,或者跟了下来.我们剩下要做的已经不多了.我们已经安装好了Mono和一些我们准备用来编译并运行C#应用程序的工具.在我们开始编写并运行应用程序之前,我觉得最好先稍微看一下目前已经可以使用的那些工具的简介,这只是其…...
美团网网站建设 费用/长春网站搭建
一、Web开发介绍 目前Web开发属于Browser/Server模式,简称BS架构,开发语言有(Python、PHP、Java …)。基于Python的Web工作原理如下: 二、框架介绍 1.什么是框架? 软件框架就是为实现或完成某种软件开发…...