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

算法题(128):费解的开关

审题:
本题需要我们将多组测试用例中拉灯数小于等于6的最小拉灯数输出,若拉灯数最小值仍大于6,则输出-1

思路:
方法一:二进制枚举

首先我们先分析一下基本特性:

1.所有的灯不可能重复拉:若拉的数为偶数,相当于没拉,这会凭空让拉灯数加n,不符合我们找最小拉灯数的需求。若拉的数为非1奇数,同理,我们可以直接拉一次达到同样的效果,没必要多拉那几次

2.拉灯先后顺序无影响:因为拉灯事件是相互独立的,且拉灯最后作用在灯上就是变换次数,所以无论先拉哪个灯,最终每个灯被拉的次数不会变,最终状态也就不会变

3.确定了第一行的拉灯情况就可以确定下一行的拉灯情况:若我们确定了第一行如何拉灯,那么为了使所有灯都处于亮的状态,第二行的目的就是使第一行灯保持全亮,第三行的目的就是让第二行全亮,以此类推,可以知道剩下的拉灯方法

然后我们分析一下具体的实现方法:
1.第一步:将灯的情况看成二进制数,并将其反着存到数组a中,也就是说我们的最终目的就转换成将灯弄成全灭

ps:二进制的位与数组索引对齐,第0位在最左侧

2.第二步:二进制枚举拉灯的方法,二进制中的1表示拉灯,0表示不拉灯

3.第三步:计算当前拉灯所需拉的次数并记录在count变量中

4.第四步:计算当前行灯按完后的结果以及下一行按完后的结果

5.第五步:求出下一行的按法

6.第六步:若a[4] == 0,则维护最小拉灯数answer

解题:

#include<iostream>
#include<cstring>
using namespace std;
int n;
const int N = 10;
int a[N];//用二进制形式存储初始状态,二进制位数和索引对齐
int f[N];//备份a
int cal(int num)
{int cnt = 0;while (num){cnt++;num &= num - 1;}return cnt;
}
int main()
{cin >> n;while (n--){//多组测试,需要清空遗留痕迹memset(a, 0, sizeof a);//存储初始数据for (int i = 0; i < 5; i++){for (int j = 0; j < 5; j++){char ch;cin >> ch;if (ch == '0') a[i] |= (1 << j);//反着存储:目标变为让灯全灭}}//开始二进制枚举int answer = 0x3f3f3f;for (int p = 0; p < (1 << 5); p++){memcpy(f, a, sizeof a);int push = p;int count = 0;for (int i = 0; i < 5; i++){count += cal(push);//求出当前行按完结果f[i] = f[i] ^ push ^ (push << 1) ^ (push >> 1);//清除高位污染f[i] &= (1 << 5) - 1;//求出下一行按完结果f[i + 1] = push^f[i+1];//求出下一行按法push = f[i];}if(f[4] == 0) answer = min(answer,count);}if (answer <= 6){cout << answer << endl;}else{cout << -1 << endl;}}return 0;
}

(1)f[N]数组的作用:备份数组a的情况,用于进行多次的二进制枚举拉灯模拟

(2)存在多组数据需要判断的时候我们一定要将全局变量的数组等痕迹清空,比如这里的数组a

(3)在存储数据给a数组的时候:我们的目的是将值为0的位置变为值为1,所以在第j位为0的时候有a[i] |= (1 << j),会将a的第j位变为1

(4)cal的目的是计算出数据的二进制位有多少个1:核心逻辑就是每次进行循环都会将一个二进制位的1分解掉

(5)我们按灯其实就是要将当前行的被按灯本身以及其左,其右的0变为1,1变为0。而其实二进制运算中的异或可以刚好达成这个目的,因为对应位置为0/1和对应位置为1的值进行异或都会变。

而对于下一行则更简单,只需要对被按位置改变即可

(6)下一行的按法怎么求?
由于我们的目的变为了让灯全灭,所以上一行按完之后的值就是下一行的按法

P10449 费解的开关 - 洛谷

http://www.xdnf.cn/news/390.html

相关文章:

  • 手动实现LinkedList
  • 【操作系统原理02】进程的描述与控制
  • Kubernetes 多主多从集群部署完整文档
  • 【上海大学计算机系统结构实验报告】多机环境下MPI并行编程
  • 国产GPU生态现状评估:从寒武纪到壁仞的编程适配挑战
  • 健康养生之道
  • package.json ^、~、>、>=、* 详解
  • JMeter介绍
  • Sentinel源码—5.FlowSlot借鉴Guava的限流算法二
  • Redis增删改查
  • FPGA——DDS信号发生器设计
  • 基于chatgpt和deepseek解答显卡的回答
  • Python语法系列博客 · 第8期[特殊字符] Lambda函数与高阶函数:函数式编程初体验
  • 【25软考网工笔记】第二章(7)多路复用技术
  • 抽象类和接口
  • 【现代深度学习技术】循环神经网络04:循环神经网络
  • 面试招聘:新能源汽车研发测试人员需求内部研讨会纪要(2025年4月19日草稿流出)
  • day28 学习笔记
  • 小程序 GET 接口两种传值方式
  • 利用 i2c 快速从 Interface 生成 Class
  • Linux系统:进程终止的概念与相关接口函数(_exit,exit,atexit)
  • 浅析vue2和vue3的区别
  • UIjavaScritIU
  • C++ 讲解—函数模板
  • Matlab画海洋与大气变量的时间序列并带标记面的三维折线图--来源粉丝
  • React-useImperativeHandle (forwardRef)
  • 美信监控易:数据采集与整合的卓越之选
  • JSAPI2.2—日期
  • 蓝桥杯之递归
  • ClawCloud的免费空间(github用户登录可以获得$5元/月的免费额度)