|
|
poj 1830 开关问题
|
|
|
[题目传送门](http://poj.org/problem?id=1830)
|
|
|
|
|
|
### 1、描述
|
|
|
|
|
|
有一些开始状态的开关，题目让我们操控开关，使得开关从开始状态变成指定状态。
|
|
|
|
|
|
注意，当你操作一个开关，其关联的开关也会被操控。例如输入样例一，开始状态为$000$的三个开关，你要操作使其变成$111$。那么有以下四种方法：
|
|
|
* 只打开开关$1$，$2$ $and$ $3$和$1$关联，所以$2$ $and$ $3$也变成$1$
|
|
|
* 只打开开关$2$,$3$
|
|
|
* 只打开开关$3$,$4$
|
|
|
* 打开开关$1,2,3$
|
|
|
|
|
|
> 初始状态 $0$ $0$ $0$ $0$
|
|
|
终止状态 $1$ $1$ $1$ $1$
|
|
|
按下$i$号开关，会影响$j$号开关:
|
|
|
$1$ $3$
|
|
|
$3$ $1$
|
|
|
$3$ $4$
|
|
|
$4$ $1$
|
|
|
$4$ $3$
|
|
|
我能影响谁$a_i$
|
|
|
$a_1$->(1,0,1,0)->{$1$,$3$}
|
|
|
$a_2$->(0,1,0,0)->{$2$}
|
|
|
$a_3$->{$1,3,4$}
|
|
|
$a_4$->{$1,3,4$}
|
|
|
谁能影响我$k_i$
|
|
|
|
|
|
|
|
|
操作每个开关后，影响的情况
|
|
|
|
|
|
### 2、问题解决
|
|
|
我们用**线性方程组**来求解。
|
|
|
|
|
|
$$\large [a_1,a_2,a_3] * \begin{bmatrix}
|
|
|
x_1 \\
|
|
|
x_2 \\
|
|
|
x_3
|
|
|
\end{bmatrix} =b,即A_x=b
|
|
|
$$
|
|
|
|
|
|
由上图表达式，我们可以思考，倘若**乘号左边是开关的关联关系**，**乘号右边是开关操作**，那么两个矩阵相乘，**结果就是开关变化**。由此，我们可以让$b$为开关变化。
|
|
|
意思为当开关从$0$变为$1$，那么**开关有变化**，$b_i$为$1$；**当开关无变化**，则$b_i$为$0$。
|
|
|
|
|
|
<center><img src='https://img-blog.csdn.net/20150803170327397'></center>
|
|
|
|
|
|
例如上面例子，$a_1=(1,0,1,0)$表示，操作开关$1$，开关$3$也会改变。即$a[i][j]$表示操作开关$j$，开关$i$也会变化。
|
|
|
|
|
|
所以，我们可以列出矩阵乘法表达式，然后进行高斯消元求解。
|
|
|
|
|
|
<font color='red'><b>$Q$:为什么这里有反着记录的呢？</b></font>
|
|
|
答：我们希望以方程组的形式对原问题进行求解。那么，由于有$n $盏灯，每个方程都要描述一盏灯的变化情况，这样的话，就共需要$n$个方程。
|
|
|
我们以第$1$盏灯为例，我们知道它的初始状态和终止状态，我们就可以研究它是在初始状态下，通过什么样的操作变化到终止状态的。因为灯开关的特殊性，关联一次就变化一次，所以，我们还可以取一巧：看看开始状态和终止状态是一样的呢，还是有了变化。
|
|
|
|
|
|
* 一样的
|
|
|
中间的变化是偶数次。用异或运算来描述就是异或和等于$0$。
|
|
|
|
|
|
* 不一样
|
|
|
中间的变化是奇数次。用异或运算来描述就是异或和等$1$。
|
|
|
|
|
|
**总结：我们关心的是状态的变化情况**
|
|
|
|
|
|
$1$号灯的变化，受和它相关联灯的制约，以上面的图为例说明：
|
|
|
第$1$盏灯的变化，受$1,3,4$三个灯的影响，我们可以把$1$盏灯的变化情况看作
|
|
|
$$\large 1*x_1+0*x_2+1*x_3+1*x_4$$
|
|
|
描述的说是:
|
|
|
* $1$号灯操作，影响$1$号灯的状态
|
|
|
* $2$号灯操作，不影响$1$号灯的状态
|
|
|
* $3$号灯操作，影响$1$号灯的状态
|
|
|
* $4$号灯操作，影响$1$号灯的状态
|
|
|
|
|
|
当然，只是说影响，但每个灯还有是权力决定自己是不是要操作的。
|
|
|
这就引出了一个系数的问题：
|
|
|
“**我是一号灯，谁能影响我的状态？**”
|
|
|
|
|
|
这玩意和题目中给的“**我是$x$号灯，我能影响$y$号灯**”是反着的，输入的时候要 <font color='red'><b>小心识别</b></font> 。
|
|
|
|
|
|
|
|
|
|
|
|
```c++
|
|
|
#include <iostream>
|
|
|
#include <string.h>
|
|
|
#include <stdio.h>
|
|
|
#include <vector>
|
|
|
#include <map>
|
|
|
#include <queue>
|
|
|
#include <algorithm>
|
|
|
#include <math.h>
|
|
|
#include <cstdio>
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 30;
|
|
|
const double eps = 10e-8;
|
|
|
int n;
|
|
|
|
|
|
int start[N]; //开始状态
|
|
|
int stop[N]; //结束状态
|
|
|
|
|
|
//高斯消元模板
|
|
|
double a[N][N]; //增广矩阵
|
|
|
int gauss() {
|
|
|
int c, r; //当前列,行
|
|
|
// 1、枚举系数每一列
|
|
|
for (c = 0, r = 0; c < n; c++) {
|
|
|
// 2、找出系数最大的行
|
|
|
int t = r;
|
|
|
for (int i = r; i < n; i++) //行
|
|
|
if (abs(a[i][c]) > abs(a[t][c])) t = i;
|
|
|
// 3、最大系数为0，直接下一列
|
|
|
if (abs(a[t][c]) < eps) continue;
|
|
|
// 4、交换
|
|
|
if (r != t) // POJ中，如果二维数组，直接swap(a[t],a[r])会报编译错误，没办法，只好用了循环
|
|
|
for (int i = 0; i < N; i++) swap(a[t][i], a[r][i]);
|
|
|
// 5、倒序, 每项除a[r][c],化系数为1,处理的是方程左右两端，需要带着a[r][n]
|
|
|
for (int i = n; i >= c; i--) a[r][i] /= a[r][c];
|
|
|
// 6、用当前行将下面所有的列消成0
|
|
|
for (int i = r + 1; i < n; i++)
|
|
|
for (int j = n; j >= c; j--)
|
|
|
a[i][j] -= a[r][j] * a[i][c];
|
|
|
// 7、下一行
|
|
|
r++;
|
|
|
}
|
|
|
|
|
|
if (r < n) {
|
|
|
for (int i = r; i < n; i++)
|
|
|
if (abs(a[i][n]) > eps)
|
|
|
return -1; //无解
|
|
|
return n - r; //自由元个数
|
|
|
}
|
|
|
|
|
|
//倒三角，将已知解代入
|
|
|
for (int i = n - 2; i >= 0; i--)
|
|
|
for (int j = i + 1; j < n; j++)
|
|
|
a[i][n] -= a[i][j] * a[j][n];
|
|
|
|
|
|
//唯一解：0
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
int T;
|
|
|
cin >> T;
|
|
|
while (T--) {
|
|
|
cin >> n;
|
|
|
memset(a, 0, sizeof(a));
|
|
|
memset(start, 0, sizeof(start)); //初始化开始状态
|
|
|
memset(stop, 0, sizeof(stop)); //初始化终止状态
|
|
|
//输入起始状态(下标从0开始)
|
|
|
for (int i = 0; i < n; i++) cin >> start[i];
|
|
|
|
|
|
//输入终止状态(下标从0开始)
|
|
|
for (int i = 0; i < n; i++) cin >> stop[i];
|
|
|
|
|
|
//输入增广矩阵
|
|
|
int x, y;
|
|
|
while (cin >> x >> y && x != 0 && y != 0)
|
|
|
a[y - 1][x - 1] = 1; //反着存入y-1受x-1影响
|
|
|
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
a[i][n] = start[i] ^ stop[i]; //状态变化 start^stop
|
|
|
a[i][i] = 1; //自己影响自己
|
|
|
}
|
|
|
|
|
|
//高斯消元模板
|
|
|
int t = gauss();
|
|
|
|
|
|
if (t == -1)
|
|
|
cout << "Oh,it's impossible~!!" << endl;
|
|
|
else
|
|
|
cout << (1 << t) << endl;
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
``` |
