SG7. 古巴比伦迷宫
描述
一群探险家被困古巴比伦迷宫 ，经过努力，探险家破译出了密码。原来通关需要先打开前方的M个机关的任意一个或多个为打开状态，然后关闭所有机关才能安全通过。探险家还发现了一种带有凸起的圆盘，圆盘可以用来同时反转若干个机关的状态（打开状态反转为关闭状态，关闭状态反转为打开状态，这若干个机关必须同时反转）。为了速记，探险家们用十六进制数字表示一个圆盘。如圆盘能同时控制第3、4、5个开关，圆盘就记为1C（11100）。每次操作一个圆盘，比特位为1的位置的机关同时被反转；而且每个圆盘使用一次后就会碎掉。目前探险家收集到了N个圆盘，问现在探险家可以顺利走出迷宫么？
若探险家手里有0、1、2、3、5五个圆盘，M=7，由于存在1 xor 2 xor 3 = 0， 因此结果是yes；
若探险家手里有0、1、2、2、5五个圆盘，M=7，由于存在2 xor 2 = 0， 因此结果是yes；
若探险家手里有0、1、3、5、9五个圆盘，M=7，由于不存组合使得 xor = 0， 因此结果是no。
输入描述
包含多组数据，第一行是数据组数。输出描述
每组一行输出，满足条件输出yes，反之输出no示例1
输入:
2 2 3 0 2 2 5 2 4 1C
输出:
yes no
C++ 解法, 执行用时: 8ms, 内存消耗: 380KB, 提交时间: 2020-10-31
#include <bits/stdc++.h>
using namespace std;
const int N = 400;
bitset<N> b1[N], b2[N];
char str[N];
string buff;
int main() {
for (int i = 1; i < N; i++) b1[i].set(i - 1);
vector <string> ss;
function<void(int, string)> dfs = [&](int i, string s){if(i == 4) {ss.push_back(s); return;} else {dfs(i + 1, s + '0'); dfs(i + 1, s + '1');}};
dfs(0, "");
sort(ss.begin(), ss.end());
ios::sync_with_stdio(false);
cin.tie(0);
int tt, m, n;
scanf("%d", &tt);
while(tt--){
for (int i = 0; i < N; i++) b2[i] = 0;
scanf("%d %d", &m, &n);
bool flag = false;
bitset<N> bt = 0;
for (int i = 0; i < m; i++) bt.set(i);
for (int i = 0; i < n; i++){
scanf("%s", str);
buff = "";
int len = strlen(str);
if(flag) continue;
if(len == 1 && str[0] == '0') continue;
for (int j = 0; j < N / 4 - len; j++) buff.append("0000");
for (int j = 0; j < len; j++) {
if(str[j] >= '0' && str[j] <= '9') buff.append(ss[str[j] - '0']);
else buff.append(ss[str[j] - 'A' + 10]);
}
bitset<N> t(buff);
t &= bt;
for (int j = 1; j < N; j++){
if((t & b1[j]) != b1[0]){
if(b2[j] == b1[0]){
b2[j] = t;
break;
} else {
t ^= b2[j];
if(t == b1[0]){
flag = true;
break;
}
}
}
}
}
puts(flag ? "yes" : "no");
}
return 0;
}
C++ 解法, 执行用时: 9ms, 内存消耗: 376KB, 提交时间: 2020-11-17
#include <bits/stdc++.h>
using namespace std;
const int N = 361;
bitset<N> b1[N], b2[N];
string s;
vector<string> v;
void DFS(int i, string s){
if(i==4){
v.push_back(s);
return;
}
DFS(i+1, s+'0');
DFS(i+1, s+'1');
}
int main(){
for(int i=1;i<N;i++)
b1[i].set(i-1);
DFS(0, "");
sort(v.begin(), v.end());
int T, m, n;
scanf("%d", &T);
while(T--){
for(int i=0;i<N;i++)
b2[i] = 0;
scanf("%d%d", &m, &n);
bool flag = false;
bitset<N> bt = 0;
for(int i=0;i<m;i++)
bt.set(i);
for(int i=0;i<n;i++){
char str[N];
scanf("%s", str);
int l = strlen(str);
s = "";
if(flag)
continue;
if(l==1 && str[0]=='0')
continue;
for(int j=0;j<N/4-l;j++)
s.append("0000");
for(int j=0;j<l;j++){
if(isdigit(str[j]))
s.append(v[str[j]-'0']);
else
s.append(v[str[j]-'A'+10]);
}
bitset<N> t(s);
t &= bt;
for(int j=1;j<N;j++){
if((t&b1[j]) != b1[0]){
if(b2[j] == b1[0]){
b2[j] = t;
break;
}else{
t ^= b2[j];
if(t == b1[0]){
flag = true;
break;
}
}
}
}
}
puts(flag?"yes":"no");
}
return 0;
}
C++ 解法, 执行用时: 9ms, 内存消耗: 416KB, 提交时间: 2020-11-01
#include <bits/stdc++.h>
using namespace std;
const int N = 400;
bitset<N> b1[N], b2[N];
char str[N];
string buff;
int main() {
for (int i = 1; i < N; i++) b1[i].set(i - 1);
vector <string> ss;
function<void(int, string)> dfs = [&](int i, string s){if(i == 4) {ss.push_back(s); return;} else {dfs(i + 1, s + '0'); dfs(i + 1, s + '1');}};
dfs(0, "");
sort(ss.begin(), ss.end());
ios::sync_with_stdio(false);
cin.tie(0);
int tt, m, n;
scanf("%d", &tt);
while(tt--){
for (int i = 0; i < N; i++) b2[i] = 0;
scanf("%d %d", &m, &n);
bool flag = false;
bitset<N> bt = 0;
for (int i = 0; i < m; i++) bt.set(i);
for (int i = 0; i < n; i++){
scanf("%s", str);
buff = "";
int len = strlen(str);
if(flag) continue;
if(len == 1 && str[0] == '0') continue;
for (int j = 0; j < N / 4 - len; j++) buff.append("0000");
for (int j = 0; j < len; j++) {
if(str[j] >= '0' && str[j] <= '9') buff.append(ss[str[j] - '0']);
else buff.append(ss[str[j] - 'A' + 10]);
}
bitset<N> t(buff);
t &= bt;
for (int j = 1; j < N; j++){
if((t & b1[j]) != b1[0]){
if(b2[j] == b1[0]){
b2[j] = t;
break;
} else {
t ^= b2[j];
if(t == b1[0]){
flag = true;
break;
}
}
}
}
}
puts(flag ? "yes" : "no");
}
return 0;
}
C++ 解法, 执行用时: 9ms, 内存消耗: 432KB, 提交时间: 2020-10-31
#include <bits/stdc++.h>
using namespace std;
const int N = 400;
bitset<N> b1[N], b2[N];
char str[N];
string buff;
int main() {
for (int i = 1; i < N; i++) b1[i].set(i - 1);
vector <string> ss;
function<void(int, string)> dfs = [&](int i, string s){if(i == 4) {ss.push_back(s); return;} else {dfs(i + 1, s + '0'); dfs(i + 1, s + '1');}};
dfs(0, "");
sort(ss.begin(), ss.end());
ios::sync_with_stdio(false);
cin.tie(0);
int tt, m, n;
scanf("%d", &tt);
while(tt--){
for (int i = 0; i < N; i++) b2[i] = 0;
scanf("%d %d", &m, &n);
bool flag = false;
bitset<N> bt = 0;
for (int i = 0; i < m; i++) bt.set(i);
for (int i = 0; i < n; i++){
scanf("%s", str);
buff = "";
int len = strlen(str);
if(flag) continue;
if(len == 1 && str[0] == '0') continue;
for (int j = 0; j < N / 4 - len; j++) buff.append("0000");
for (int j = 0; j < len; j++) {
if(str[j] >= '0' && str[j] <= '9') buff.append(ss[str[j] - '0']);
else buff.append(ss[str[j] - 'A' + 10]);
}
bitset<N> t(buff);
t &= bt;
for (int j = 1; j < N; j++){
if((t & b1[j]) != b1[0]){
if(b2[j] == b1[0]){
b2[j] = t;
break;
} else {
t ^= b2[j];
if(t == b1[0]){
flag = true;
break;
}
}
}
}
}
puts(flag ? "yes" : "no");
}
return 0;
}
C++ 解法, 执行用时: 11ms, 内存消耗: 384KB, 提交时间: 2020-12-23
#include <bits/stdc++.h>
using namespace std;
const int N = 400;
bitset<N> b1[N], b2[N];
char str[N];
string buff;
int main() {
for (int i = 1; i < N; i++) b1[i].set(i - 1);
vector <string> ss;
function<void(int, string)> dfs = [&](int i, string s){if(i == 4) {ss.push_back(s); return;} else {dfs(i + 1, s + '0'); dfs(i + 1, s + '1');}};
dfs(0, "");
sort(ss.begin(), ss.end());
ios::sync_with_stdio(false);
cin.tie(0);
int tt, m, n;
scanf("%d", &tt);
while(tt--){
for (int i = 0; i < N; i++) b2[i] = 0;
scanf("%d %d", &m, &n);
bool flag = false;
bitset<N> bt = 0;
for (int i = 0; i < m; i++) bt.set(i);
for (int i = 0; i < n; i++){
scanf("%s", str);
buff = "";
int len = strlen(str);
if(flag) continue;
if(len == 1 && str[0] == '0') continue;
for (int j = 0; j < N / 4 - len; j++) buff.append("0000");
for (int j = 0; j < len; j++) {
if(str[j] >= '0' && str[j] <= '9') buff.append(ss[str[j] - '0']);
else buff.append(ss[str[j] - 'A' + 10]);
}
bitset<N> t(buff);
t &= bt;
for (int j = 1; j < N; j++){
if((t & b1[j]) != b1[0]){
if(b2[j] == b1[0]){
b2[j] = t;
break;
} else {
t ^= b2[j];
if(t == b1[0]){
flag = true;
break;
}
}
}
}
}
puts(flag ? "yes" : "no");
}
return 0;
}