poj 1222 EXTENDED LIGHTS OUT (高斯消元解异或方程组 开关问题)

本文主要是介绍poj 1222 EXTENDED LIGHTS OUT (高斯消元解异或方程组 开关问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

近距离观摩今天北京站的比赛,向志愿者学姐要了一份题目,看了看H题;

因为数据被弱化,瞬间就想到了背包;

就先研究下标准解法——异或方程组;



下面为转载文:

题意:有一个5*6的矩阵,每个位置都表示按钮和灯,1表示亮,0表示灭。每当按下一个位置的按钮,它和它周围灯的状态全部翻转,问在这样的一个方阵中按下哪些按钮可以把整个方阵都变成灭的,这时1表示按了,0表示没按。

以下分析部分转自:http://blog.csdn.net/shiren_Bod/article/details/5766907

这个游戏有一些技巧: 
1、按按钮的顺序可以随便。 
2、任何一个按钮都最多需要按下1次。因为按下第二次刚好抵消第一次,等于没有按。 

这个问题可以转化成数学问题。 
一个灯的布局可以看成一个0、1矩阵。以3x3为例: 
0 1 0 
1 1 0 
0 1 1 
表示一个布局。其中0表示灯灭,1表示灯亮。 
每次按下按钮(POJ1222)或者叫一个宿舍关灯(0998),可以看成在原矩阵上加(模2加,就是按位异或)上一个如下的矩阵: 
0 1 0 
1 1 1 
0 1 0 
上述矩阵中的1表示按下第2行第2列的按钮时,作用的范围。如果按左上角的按钮,就是: 
1 1 0 
1 0 0 
0 0 0 

我们记L为待求解的原始布局矩阵。A(i,j)表示按下第i行第j列的按钮时的作用范围矩阵。在上述例子中, 
L= 
0 1 0 
1 1 0 
0 1 1 

A(1,1)= 
1 1 0 
1 0 0 
0 0 0 

A(2,2)= 
0 1 0 
1 1 1 
0 1 0 

假设x(i,j)表示:想要使得L回到全灭状态,第i行第j列的按钮是否需要按下。0表示不按,1表示按下。那么,这个游戏就转化为如下方程的求解: 
L + x(1,1)*A(1,1) + x(1,2)*A(1,2) + x(1,3)*A(1,3) + x(2,1)*A(2,1) + ... + x(3,3)*A(3,3) = 0 

其中x(i,j)是未知数。方程右边的0表示零矩阵,表示全灭的状态。直观的理解就是:原来的L状态,经过了若干个A(i,j)的变换,最终变成0:全灭状态。 
由于是0、1矩阵,上述方程也可以写成: 
x(1,1)*A(1,1) + x(1,2)*A(1,2) + x(1,3)*A(1,3) + x(2,1)*A(2,1) + ... + x(3,3)*A(3,3) = L 

这是一个矩阵方程。两个矩阵相等,充要条件是矩阵中每个元素都相等。将上述方程展开,便转化成了一个9元1次方程组: 

简单地记做:AA * XX = LL 

这个方程有唯一解: 
x(1,1) x(1,2) x(1,3) 
x(2,1) x(2,2) x(2,3) 
x(3,1) x(3,2) x(3,3) 

1 1 1 
0 0 0 
0 0 1 

也就是说,按下第一行的3个按钮,和右下角的按钮,就

能使L状态变成全灭状态。 
对于固定行列的阵列来说,AA矩阵也是确定的。是否存在解,解是否唯一,只与AA矩阵有关。对于唯一解的情形,只要将LL乘以AA的逆矩阵即可。具体求AA的逆矩阵的方法,可以用高斯消元法。 

由于是0、1矩阵,上述方程也可以写成:

将1式两边同时加上一个L矩阵就可以变成
x(1,1)*A(1,1) + x(1,2)*A(1,2) + x(1,3)*A(1,3) + x(2,1)*A(2,1) + ... + x(3,3)*A(3,3) = L

A(1,1)把矩阵 转化为一个列向量,L也转化为一个列向量,

将sigma xi*Ai=Li 对应位置的值相等就可以建立方程组了

X1*A(1,1)1+X2*A(1,2)1+X3*A(1,3)1+…………X30*A(30,30)1=L1;    mod 2

X1*A(1,1)2+X2*A(1,2)2+X3*A(1,3)2+…………X30*A(30,30)2=L2;    mod 2

X1*A(1,1)3+X2*A(1,2)3+X3*A(1,3)3+…………X30*A(30,30)3=L3    mod 2

…….

…….

…….

X1*A(1,1)30+X2*A(1,2)30+X3*A(1,3)30+…………X30*A(30,30)30=L30; mod 2

其中A(i,j)k 表示列向量A中第K个元素

这里的*表示点乘,Xi取(1,0) +表示模2加法,所以在高斯消元的时候可以用^异或运算


1个开关最多控制5个灯,在构造的矩阵中,a[i][j]=1表示第i个开关可以影响到j号灯




#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int N=31;
int a[N][N];  //系数矩阵
int ans[N];/*
解异或方程可以套用高斯消元法,只须将原来的加减操作替换成异或操作就可以
两个方程的左边异或之后,它们的公共项就没有了。
*/void Debug ()
{for (int i=0;i<N-1;i++)for (int j=0;j<N-1;j++)printf (j==N-2?"%d\n":"%d ",a[i][j]);
}void Gauss ()
{int i,j,k;for (k=0;k<30;k++){i=k;for (;i<30;i++)//对于k=0..N-1,找到一个M[i][k]不为0的行iif (a[i][k]!=0)break;for (j=0;j<=30;j++)  //把找到的第i行与第k行交换swap (a[k][j],a[i][j]);
/*用第k行去异或下面所有M[i][j]不为0的行i,消去它们的第k个系数,这样就将原矩阵化成了上三角矩阵
最后一行只有一个未知数,这个未知数就已经求出来了,
用它跟上面所有含有这个未知数的方程异或,就消去了所有的着个未知数,
此时倒数第二行也只有一个未知数,它就被求出来了,用这样的方法可以自下而上求出所有未知数。
*/for (i=0;i<30;i++)if (k!=i && a[i][k])for (j=0;j<=30;j++)   // <= a[i][j]=a[k][j]^a[i][j];}for (i=0;i<30;i++)ans[i]=a[i][30];
}int main ()
{  
#ifdef ONLINE_JUDGE
#elsefreopen("read.txt","r",stdin);
#endifint T,i;scanf("%d",&T);for (int Cas=1;Cas<=T;Cas++){memset(a,0,sizeof(a));memset(ans,0,sizeof(ans));for (i=0;i<30;i++){scanf("%d",&a[i][30]);ans[i]=0;}for (i=0;i<30;i++){a[i][i]=1;if (i%6!=0) a[i-1][i]=1; //if (i%6!=5) a[i+1][i]=1;if (i>5) a[i-6][i]=1;if (i<24) a[i+6][i]=1;}
//		Debug();Gauss();printf ("PUZZLE #%d\n",Cas);for (i=0;i<30;i++)printf (i%6==5?"%d\n":"%d ",ans[i]);}return 0;
}


这篇关于poj 1222 EXTENDED LIGHTS OUT (高斯消元解异或方程组 开关问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102439

相关文章

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR