8.9专题赛题解（下）
PS:沉迷于图论学习无法自拔，因此拖更hhh，明日定会奉上图论大作！请各位亲们敬请期待！告辞！
A - 飞行员兄弟
POJ - 2965 / AcWing 116（难度：简单）
题目：
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有16个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个4х4的矩阵，您可以改变任何一个位置[i,j]上把手的状态。
但是，这也会使得第i行和第j列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行，每行包含四个把手的初始状态。
符号“+”表示把手处于闭合状态，而符号“-”表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数N，表示所需的最小切换把手次数。
接下来N行描述切换顺序，每行输入两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
如果有多种解决方案，您可以提供其中任何一种解决方案。
数据范围
1≤i,j≤4
Sample Input
-+--
----
----
-+--
Sample Output
6
1 1
1 3
1 4
4 1
4 3
4 4
题意：
输入一个4*4的矩阵，矩阵里每一个元素都是“+”或者“-”，“+”表示开关是闭合状态，“-”表示开关是打开状态，目标是让所有的开关全部打开，相当于是把所有的“+”变成“-”。操作开关有额外的属性，如果要操作一个开关，那么这个开关所在的一行和一列都会被同时操作。操作的意思就是，如果这个开关原本是闭合的，那么操作一次以后，开关就会变成打开状态了，反之亦然。注意，如果存在多种打开冰箱的方式，输出字典序最小的方案
思路：（知识点：位运算）
令冰箱打开状态为“0”，关闭状态为“1”。同样一个地方操作两次没有意义，因为同一个地方操作两次就等于没有操作，所以一个地方只会操作一次。可以考虑暴力枚举，因为它总共的操作数是有限的。总共有16个开关，每种开关有按和不按两种状态，那么所有的方案数就是216，也就是说，若把所有方案全部枚举一遍，就只需要216种方案。那如何判断一个方案是否能把所有矩阵全部变为“0”（时间复杂度是O(n)）（与216的时间复杂度相乘，总的时间复杂度大概是106）可以用位运算的方法枚举，直接从0枚举到216-1，因为每个数在二进制表示下都有16位，如果这一位为0表示我不按这个开关，如果这一位为1的话，表示我按这个开关。在这种情况下，就可以通过从0循环到216-1来枚举所有方案。例如，现在枚举出了一个方案k，可以先遍历一下k的哪些位是1，j可以用16次运算来做，从0开始枚举到15，然后判断某一位是不是1，可以用位运算来判断某一位是不是1（k>>i&1)(这步运算可以快速的判断出k的第i位是不是1)从而判断出了哪一位开关需要按。（可以把题目种的矩阵每一位都标一下号）下一步操作可以继续用位运算，如果我们想改变某一个数所在行和列的状态，就可以预先求出这一行和列上所有的数组合起来的二进制表示。相当于我们每次改变一个开关的状态的时候，都可以直接查表得出该异或的数的值，然后直接异或一下就行了。
AC代码：
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 4, INF = 100;
int change[N][N];
int get(int x, int y)
{
return x * N + y;
}
int main()
{
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
{
for (int k = 0; k < N; k ++ )
{
change[i][j] += (1 << get(i, k)) + (1 << get(k, j));
}
change[i][j] -= 1 << get(i, j);
}
int state = 0;
for (int i = 0; i < N; i ++ )
{
string line;
cin >> line;
for (int j = 0; j < N; j ++ )
{
if (line[j] == '+')
{
state += 1 << get(i, j);
}
}
}
vector<PII> path, temp;
for (int i = 0; i < 1 << 16; i ++ )
{
int now = state;
temp.clear();
for (int j = 0; j < 16; j ++ )
if (i >> j & 1)
{
int x = j / 4;
int y = j % 4;
now ^= change[x][y];
temp.push_back({x, y});
}
if (!now && (path.empty() || path.size() > temp.size()))
{
path = temp;
}
}
cout << path.size() << endl;
for (auto &p : path)
cout << p.first + 1 << ' ' << p.second + 1 << endl;
return 0;
}
|