城市漫步——题解：

问题分析

这道题描述了一个由二进制串命名的城市网络，本质上是一个n维超立方体的图模型(示例)：

• 每个节点是一个n位二进制串（共$2^n$个可能节点）
• 其中k个节点是禁止访问的（不是城市）
• 边连接汉明距离为1的节点（即仅有一位不同的二进制串）

问题：判断两个节点s和t在删除禁止节点后的图中是否连通。

关键约束：$n \leq 60$，但$2^n$可能达到$2^{60}$，无法存储所有节点。

算法核心思想

双向BFS + 剪枝策略

虽然总节点数可能极大($2^{60}$)，但观察发现：

1. 禁止节点数$k \leq 10^6$，相对较少
2. 从起点s出发，能访问的节点数受禁止节点限制
3. 如果从s能到达的节点数 > $n \cdot k$，说明搜索空间很大，很可能连通

算法步骤

1. 从s开始BFS，标记访问过的节点
2. 如果遇到t，直接返回连通
3. 如果访问节点数 > $n \cdot k$，停止搜索（认为连通）
4. 同样从t开始BFS验证
5. 只有两个方向都"连通"才输出TAK

代码深度解析

核心数据结构：自定义哈希表

const int mod = 1234577, maxk = 5e6 + 10;
struct Hash_Map {
    int nxt[maxk], cnt[maxk], head[mod + 100], tot;
    ll val[maxk];
    
    void clear() {
        memset(head, 0, sizeof(head));
        tot = 0;
    }
    
    int Hash(LL x) { return x % mod; }
    
    void ins(LL x) {
        int u = Hash(x);
        for (int i = head[u]; i; i = nxt[i]) {
            if (val[i] == x) {
                cnt[i]++;
                return;
            }
        }
        // 链地址法解决哈希冲突
        tot++;
        val[tot] = x, nxt[tot] = head[u];
        cnt[tot] = 1;
        head[u] = tot;
    }
    
    bool find(LL x) {
        int u = Hash(x);
        for (int i = head[u]; i; i = nxt[i]) {
            if (val[i] == x) return true;
        }
        return false;
    }
};

设计优势：

• 避免unordered_set的开销
• 链地址法处理哈希冲突
• 同时记录禁止节点和已访问节点

二进制串高效处理

ll trans(char *str) {
    ll res = 0;
    int len = strlen(str);
    ll k = 1;
    for (int i = len - 1; i >= 0; i--) {
        if (str[i] == '1') res += k;
        k <<= 1;  // 位运算快速计算
    }
    return res;
}

将二进制字符串转换为长整型，便于存储和位运算。

BFS核心实现与剪枝

int bfs(ll x, ll y) {
    int cnt = 0;
    if (x == y) return 1;  // 起点即终点
    
    hh.clear();
    // 将禁止节点加入哈希表
    for (int i = 1; i <= k; i++) {
        hh.ins(a[i]);
    }
    
    queue<ll> q;
    q.push(x);
    cnt++;
    hh.ins(x);
    
    while (!q.empty()) {
        ll u = q.front(); q.pop();
        
        // 生成所有邻居节点（改变每一位）
        for (int i = 0; i < n; i++) {
            ll v = (u ^ (1ll << i));  // 位运算翻转第i位
            
            if (v == y) return 1;  // 找到终点
            
            if (hh.find(v)) continue;  // 禁止节点或已访问
            
            cnt++;
            // 关键剪枝：访问节点数超过n*k认为连通
            if (cnt > 1ll * n * k) return 1;
            
            q.push(v);
            hh.ins(v);
        }
    }
    return 0;
}

主函数：双向验证

int main() {
    scanf("%lld%lld", &n, &k);
    scanf("%s", tmp); s = trans(tmp);
    scanf("%s", tmp); t = trans(tmp);
    
    // 读入禁止节点
    for (int i = 1; i <= k; i++) {
        scanf("%s", tmp);
        a[i] = trans(tmp);
    }
    
    // 双向BFS验证
    int res = bfs(s, t);  // 从s到t
    if (!res) { cout << "NIE"; return 0; }
    
    res &= bfs(t, s);     // 从t到s  
    if (!res) { cout << "NIE"; return 0; }
    
    cout << "TAK";
    return 0;
}

关键优化点详解

1. $n \cdot k$剪枝的数学原理

if (cnt > 1ll * n * k) return 1;

为什么这个剪枝有效？

• 每个禁止节点最多影响n个邻居
• 如果搜索超过$n \cdot k$个节点，说明禁止节点形成的障碍很"稀疏"
• 在n维超立方体中，稀疏障碍很难完全隔离大空间
• 基于图论中的等周不等式原理

2. 双向BFS的优势

分别从s和t出发验证：

• 防止单向被大量禁止节点阻挡的情况
• 在连通分量大小差异较大时更高效
• 提高算法在边界情况下的鲁棒性

3. 位运算优化

ll v = (u ^ (1ll << i));  // 翻转第i位

使用异或运算快速生成相邻节点，避免字符串操作。

复杂度分析

• 时间复杂度：最坏$O(n \cdot k)$，受搜索节点数限制
• 空间复杂度：$O(n \cdot k)$，存储访问节点和禁止节点
• 哈希操作：平均$O(1)$的插入和查询

学习要点总结

1. 状态压缩技巧：用整数表示二进制串，便于存储和运算
2. 邻域生成优化：通过位运算快速生成图邻居
3. 自定义哈希表：针对特定问题优化存储结构
4. 启发式剪枝：利用图结构特性设置合理阈值
5. 双向搜索策略：提高算法完备性和效率
6. 稀疏图处理：在无法存储完整图时仍能解决问题

算法适用场景

这种解法适用于：

• 状态空间极大但障碍相对稀疏的图搜索问题
• 具有规则邻接关系的图结构（如网格图、超立方体等）
• 需要判断连通性但无法构建完整图的情况