首页 > 试题广场 >

古巴比伦迷宫

[编程题]古巴比伦迷宫
  • 热度指数:741 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

一群探险家被困古巴比伦迷宫 ,经过努力,探险家破译出了密码。原来通关需要先打开前方的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。



输入描述:
包含多组数据,第一行是数据组数。

每组数据中首行为M N,M为机关个数,M <= 360(大部分情况下小于40),N为圆盘个数,
N<=50000;其余为N行圆盘的16进制ID,可以保证每行输入小于2^M


输出描述:
每组一行输出,满足条件输出yes,反之输出no
示例1

输入

2
2 3
0
2
2
5 2
4
1C

输出

yes
no
//线性基模板题 但是二进制位可能有360位 用bitset就可以 细节处理一下就可以过
#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define mem(x,v) memset(x,v,sizeof(x))
#define rep(i,a,n) for(int i = a;i<n;i++)
#define per(i,a,n) for(int i = n-1;i>=a;i--)
using namespace std;
constint N = 400;
int T,n,m;
chars[N];
string ss[] = {"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001","1010","1011","1100","1101","1110","1111"};
string buff;
bitset<N> b[N];
bitset<N> bs[N];
int main()
{
    //freopen("1.in","r",stdin);
    scanf("%d",&T);
    rep(i,1,N) b[i].set(i-1);
    while(T--){
        rep(i,0,N) bs[i] = 0;
        scanf("%d %d",&m,&n);
        bool flag = false;
        bitset<N> bi = 0;
        rep(i,0,m) bi.set(i);
        rep(i,0,n){
            scanf("%s",s);buff = "";
            int len = strlen(s);
            if(flag) continue;
            if(len==1&&s[0]=='0') continue;
            rep(j,0,N/4-len) buff.append("0000");
            rep(j,0,len){
                if(s[j]>='0'&&s[j]<='9') buff.append(ss[s[j] - '0']) ;
                else buff.append(ss[s[j] - 'A'+ 10]) ;
            }
            bitset<N> t(buff);
            t = t&bi;
            //cout<<t<<endl;
            per(j,1,N){
                if((t&b[j])!=b[0]){
                    if(bs[j]==b[0]){
                        bs[j] = t;
                        break;
                    }else{
                        t = t^bs[j];
                        if(t==b[0]){
                            flag = true;
                            break;
                        }
                    }
                }
            }
        }
        if(flag) printf("yes\n");
        else printf("no\n");
    } 
    return 0;
}

发表于 2019-06-12 18:33:17 回复(0)
#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;
}

发表于 2020-11-17 12:57:06 回复(0)