题解 | #古巴比伦迷宫#

解题思路

这是一个异或运算和线性代数的问题。给定：

1. 个机关，每个机关有开关两种状态
2. 个圆盘，每个圆盘可以同时反转若干机关的状态
3. 每个圆盘只能使用一次
4. 需要判断是否能通过使用这些圆盘使所有机关处于关闭状态

解决方案：

1. 使用异或运算表示状态转换
2. 将问题转化为线性方程组求解
3. 使用高斯消元法判断是否有解

关键点：

• 使用bitset优化空间和运算效率
• 将16进制字符串转换为二进制状态
• 使用异或运算消元

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 400;

int main() {
    // 预处理二进制表示
    bitset<N> b1[N], b2[N];
    for (int i = 1; i < N; i++) 
        b1[i].set(i - 1);
    
    // 生成4位二进制数的所有组合
    vector<string> binary;
    function<void(int, string)> dfs = [&](int i, string s) {
        if(i == 4) {
            binary.push_back(s);
            return;
        }
        dfs(i + 1, s + '0');
        dfs(i + 1, s + '1');
    };
    dfs(0, "");
    sort(binary.begin(), binary.end());
    
    int T, m, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &m, &n);
        // 初始化状态矩阵
        for (int i = 0; i < N; i++) 
            b2[i] = 0;
        
        bool possible = false;
        bitset<N> target;
        for (int i = 0; i < m; i++) 
            target.set(i);
            
        char str[N];
        for (int i = 0; i < n; i++) {
            scanf("%s", str);
            if(possible) continue;
            
            // 处理特殊情况
            int len = strlen(str);
            if(len == 1 && str[0] == '0') continue;
            
            // 转换16进制为二进制
            string bits;
            for (int j = 0; j < N/4 - len; j++) 
                bits.append("0000");
            for (int j = 0; j < len; j++) {
                int val = isdigit(str[j]) ? str[j] - '0' : str[j] - 'A' + 10;
                bits.append(binary[val]);
            }
            
            // 高斯消元
            bitset<N> curr(bits);
            curr &= target;
            for (int j = 1; j < N; j++) {
                if((curr & b1[j]) != b1[0]) {
                    if(b2[j] == b1[0]) {
                        b2[j] = curr;
                        break;
                    } else {
                        curr ^= b2[j];
                        if(curr == b1[0]) {
                            possible = true;
                            break;
                        }
                    }
                }
            }
        }
        puts(possible ? "yes" : "no");
    }
    return 0;
}

算法及复杂度

• 算法：高斯消元 + 位运算
• 时间复杂度： - 是测试用例数， 是圆盘数， 是机关数
• 空间复杂度： - 需要存储状态矩阵