[二分枚举]特殊密码锁
描述
有一种特殊的二进制密码锁,由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 容器以及容器中 …...

19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...