首页 > 其他分享 >费解的开关(位运算+递推)

费解的开关(位运算+递推)

时间:2023-02-04 11:07:01浏览次数:64  
标签:状态 第一行 int 费解 开关 枚举 ans include 递推


题目描述:

你玩过“拉灯”游戏吗?25盏灯排成一个5x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯,用数字“0”表示关着的灯。下面这种状态

10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成:

01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成:

01111
11001
11001
10100
11011

给定一些游戏的初始状态,编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式

第一行输入正整数nn,代表数据中共有nn个待解决的游戏初始状态。

以下若干行数据分为nn组,每组数据有5行,每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

输出格式

一共输出nn行数据,每行有一个小于等于6的整数,它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态,若6步以内无法使所有灯变亮,则输出“-1”。

数据范围

0<n≤5000

输入样例:

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例:

3
2
-1

这道题很多人都有搜索做,搜索也可以做,不过复杂度应该是3*10^8左右,如果用递推复杂度只有2^5*4*5*5000,1600000,。

费解的开关(位运算+递推)_初始状态

上面是递推,下面是搜索,可以看到,复杂度降低了很多,这里来写一下递推做法。

首先我们要枚举第一行灯开关的所有情况,那么如果要改变第一行的灯的状态,那么就只能更改第二行的位于该灯下面的那个开关来改变

费解的开关(位运算+递推)_递推_02

如果我们固定了第一行,那么为了将全部都变成绿色,就必须利用第二行。例如,(1,1)(1,1)是红色,为了让它变成绿色,就必须更改(2,1)(2,1)。为了让(1,4)(1,4)变成绿色,就必须更改(2,4)(2,4)。
更改后图形如下:

费解的开关(位运算+递推)_#include_03

那么我们再固定第二行,利用第三行来更改它(就像用第一行来更改第二行一样),就变成了

费解的开关(位运算+递推)_#include_04

同理,更改第三行

费解的开关(位运算+递推)_初始状态_05

再更改第四行

费解的开关(位运算+递推)_递推_06

这是我们发现,最后还有一个灯是关着的,所以,这说明第一行的灯如果是这样的情况就无法成立
那么就继续枚举第一行的点击方式,再继续按照刚才的方法,判断能否点完即可。

这道题目首先看一眼,我们就可以知道必然与位运算有着密切的关系,因为出现了0和1,这是一个重要的发现,接着我们在仔细分析题意,我们知道如果纯暴力枚举的话,必然是会超时的,那么如何优化呢?因此我们需要从题目中找出非常有用的性质来优化,这是一个大致的思路方向

每一个位置顶多只会操作一次。因为如果操作两次的话,相当于不操作,必然是不满足最优解。

在一套方案中,操作的顺序无关紧要,这一个略加思索便可得知

最重要的性质,如果我们确定了第I行的操作方案的话,那么后面的行数都可以依此递推,下面给出一个详细的解答。

11011
10110
01111
11111
比如说这个例子,如果我们确定了第1行,那么第二行所有的0(坐标:a[i][j])
都只能是第三行a[i+1][j]来修改了,因为如果你第二行修改的话,那么第一行将会打乱,下面每一行依此类推。

我一开始是不理解为什么要枚举32种第一行的所有情况,可能很多人和我一样不理解。

如果不枚举,就让第一行不动,那么最后会发现需要的次数>6次了,那么有没有可能让次数<=6呢?
有的,就是稍微改一下第一行的状态,那怎么改呢,没人知道,只能一个一个按钮去试,那不正好是枚举32次吗。所以不枚举直接递推的话输出的所有结果都是-1,枚举只是为了找到最小的答案。

AC代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<ctime>
#include<map>
const int INF = 0x3f3f3f3f;
using namespace std;
int i,j,k,l;
int n,m;
int ans;
char a[10][10],cpy[10][10];
int dx[6]={0,-1,0,1,0},dy[6]={0,0,1,0,-1};
void turn(int x,int y)
{
for(l=0;l<5;l++)
{
int xx=x+dx[l];
int yy=y+dy[l];
if(xx>=0&&xx<5&&yy>=0&&yy<5)//控制边界范围
a[xx][yy] ^= 1;//对1这个位置的灯做相反操作
}
}
int slove()
{
ans=INF;
for(k=0;k < 1<<5;k++)//一共只有32种状态对每种状态枚举递推
{
int res=0;
memcpy(cpy,a,sizeof a );
for(j=0;j<5;j++)
{
if(k>>j&1)//取出k的第j位就是相当于取出第几盏灯的状态
{
res++;
turn(0,j);
}
}
for(i=0;i<4;i++)
{
for(j=0;j<5;j++)
{
if(a[i][j]=='0')
{
res++;
turn(i+1,j);//第i行的状态只能由第i+1行得到
}
}
}
bool flag=true;
for(j=0;j<5;j++)
{
if(a[4][j]=='0')
{
flag=false;
break;
}
}
if(flag)
ans=min(ans,res);//在每次的状态中寻找最小值
memcpy(a,cpy,sizeof cpy );
}
if(ans>6)
ans=-1;
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
for(i=0;i<5;i++)
scanf("%s",a[i]);
slove();
cout<<ans<<endl;
}
return 0;
}

 

标签:状态,第一行,int,费解,开关,枚举,ans,include,递推
From: https://blog.51cto.com/u_15952369/6036914

相关文章

  • 常系数齐次线性递推
    现在终于把线性递推常数减小了许多。(实际上我原先写的多项式取模才这么慢)Fiduccia算法一个方法是求\(x^n\)对递推数列的特征多项式\[p(x)=x^k-p_1x^{k-1}-p_2x^{k-2}......
  • 万字详解递归与递推
    前言相信这个故事,朋友们应该都不陌生,从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?「从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事......
  • 查看电脑开关机时间
    在我们的生活和工作中都离不开电脑,而为了更好的管理电脑,我们就需要知道电脑的开关机时间,那么这要去哪看呢?下面小编在计算机管理器上操作,来查看电脑开关机时间。先在“此......
  • luogu P5326 [ZJOI2019]开关
    题面传送门直接优化高斯消元似乎不是很可做,可以换一种思路。我们先来考虑一个弱化版的问题:求某个时刻为当前局面的答案。这个东西长得一脸指数生成函数,不妨列出来,设\(F_......
  • CMake option选项开关
    CMakeoption使用场景:编译脚本传递参数->CMake脚本接收option->源代码宏1.编译脚本传入参数传入一个cmakeoptionTEST_DEBUG#!/bin/shcmake-DTEST_DEBUG=ON......
  • 继电器与接近开关
    1、接近开关一般情况都是 常开NO,而且都是金属接近才能吸合一般24V(三线开关信息——棕正蓝负黑信号)PNP型——黑色是高电平(即正极)NPN型——黑色是低电平(即负极)2......
  • 空气开关A型、B型、C型、D型的区别
    空气开关分为A型、B型、C型和D型,A型和B型使用的比较少,最常用的就是C型和D型了,C型应用于家庭电路用电,D型应用于动力用电空气开关A型、B型、C型、D型的区别对于这4种型号,它......
  • 荣耀无5G开关,荣耀手机,荣耀80GT
    荣耀无5G开关,荣耀手机,荣耀80GT。MagicOS版本号是:7.0.0.138(C00E135R2P6)。解决方法:1.进入设置-关于手机-连续点击7次版本号。会提示,开发者选项已开启。2.在设置-系......
  • 浅谈线性递推
    线性递推相关常系数齐次线性递推对于一般的递归式,我们有\(\sum\limits_{j=0}^{k}A_{i-j}R_j=0,i\gek\)定义\(S=AR\),则\(S\)的最高次为\(k-1\),小于\(R\)的最高次项\(......
  • STC51 STC15开发工控网关-工控主机-02-开关量采集原理与设计
    开关量采集电路适用于对开关量信号进行采集,如循环泵的状态信号,进出仓阀门的开关状态灯开关量。污染源在线检测仪可采集16路开关信号,输入24VDC;设定当输入范围为18~24VDC时,认......