「NowCoder 342C」筱玛的迷阵探险

Description

给定一个 $n \times n$ 的网格，每个格子的权值为 $a_{i,j}$，现在要从 $(1,1)$ 走到 $(n,m)$，初始值为 $e$，求路径最大异或和。$(1 \leq n \leq 20,0 \leq a_{i,j},e \leq 10^9)$

Source

[NowCoder]342C

Solution

与 [Codeforces]1006F 相似，考虑 折半搜索 。从起点和终点分别开始搜，到对角线停止。

怎么求最大异或和呢？

我们可以建 $n$ 棵 Trie 。当我们第一次搜到对角线上的点 $(x,y)$ 时，把此时的路径异或和插入到第 $x$ 棵 Trie 中。当我们第二次从终点搜到 $(x,y)$ 时，又得到了一个路径和 $val$，显然这时我们要从第 $x$ 棵 Trie 中找到一个数，使它与 $val$ 的异或值最大。这就变成了一个很经典的问题，具体操作详见 [LOJ]10050 。注意搜索的边界和 Trie 的空间大小。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 20, MAXM = 1e5;
int n, e, ans, a[MAXN + 5][MAXN + 5];
struct Trie {
    int tot, ch[MAXM * 31 + 5][2];
    
    inline void insert(int x) {
        int u = 1;
        for (int i = 30; ~i; --i) {
            bool v = x & (1 << i);//x 二进制下第 i 位的值 
            if (!ch[u][v]) ch[u][v] = ++tot;//新建节点 
            u = ch[u][v];
        }
    }
    inline int find(int x) {
        int u = 1, res = 0;
        for (int i = 30; ~i; --i) {
            bool v = x & (1 << i);//x 二进制下第 i 位的值 
            if (!ch[u][v ^ 1]) u = ch[u][v];//如果没有相反的路，则沿相同的路走
            else {
                res += 1 << i;//走相反的路
                u = ch[u][v ^ 1];//这一位为 1，累加答案 
            }
        }
        return res;
    }
} tr[MAXN + 5];

void dfs1(int x, int y, int val) {
    if (x + y == n + 1) {//(x,y) 在对角线上，n + 1 是为了防止 n = 1 时出错 
        tr[x].insert(val);//把 val 插入到第 x 棵 Trie 中 
        return;
    }
    if (x < n) dfs1(x + 1, y, val ^ a[x + 1][y]);
    if (y < n) dfs1(x, y + 1, val ^ a[x][y + 1]);//注意边界 
}

void dfs2(int x, int y, int val) {
    if (x + y == n + 1) {
        ans = max(ans, tr[x].find(val ^ e ^ a[x][y]));
        //不要忘记异或上初始值 e
        //这里异或 a[x][y] 是因为第二次到这个点多异或了 (x,y) 一次，
        //而第一次到 (x,y) 时已经异或过了，再异或一次相当于只保留一次异或 
        return;
    }
    if (x > 1) dfs2(x - 1, y, val ^ a[x - 1][y]);
    if (y > 1) dfs2(x, y - 1, val ^ a[x][y - 1]);
}

int main() {
    read(n), read(e);
    for (int i = 1; i <= n; ++i) {
        tr[i].tot = 1;//Trie 初始节点数为 1 
        for (int j = 1; j <= n; ++j) read(a[i][j]);
    }
    dfs1(1, 1, a[1][1]), dfs2(n, n, a[n][n]);
    write(ans);
    putchar('\n');
    return 0;
}