当前位置 博文首页 > ttoobne:牛客练习赛37B 筱玛的排列(字典树 + dfs)

    ttoobne:牛客练习赛37B 筱玛的排列(字典树 + dfs)

    作者:[db:作者] 时间:2021-08-30 10:30

    题目链接
    题解:
    由于 n n n 最大有 20,那所有从 1 到 n 的情况有 C 2 n n C_{2n}^n C2nn? 种情况,肯定不能暴力搜索,那么我们可以把图分成两个部分来搜索,分别从 ( 1 , 1 ) (1,1) (1,1) ( n , n ) (n,n) (n,n) 开始走 n n n 步到对角线上,然后用字典树求最大异或和就行啦。
    代码:

    #include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define P pair<int, int>
    #define debug(x) cout << (#x) << ": " << (x) << " "
    #define fastio ios::sync_with_stdio(false), cin.tie(0)
    const int mod = 1e9 + 7;
    const int M = 6000000 + 10;
    const int N = 20 + 10;
    
    int n, e, a[N][N];
    int tree[M][2], cnt;
    vector<int> v11[N], vnn[N];
    
    void add(int x)
    {
        int now = 1;
        for(int i = 31; i >= 0; -- i) {
            int &son = tree[now][(x >> i) & 1];
            if(!son) son = ++cnt;
            now = son;
        }
    }
    
    int query(int x)
    {
        int now = 1, ans = 0;
        for(int i = 31; i >= 0; -- i) {
            int &son = tree[now][!((x >> i) & 1)];
            if(son) ans += (1 << i), now = son;
            else now = tree[now][(x >> i) & 1];
        }
        return ans;
    }
    
    void dfs11(int x, int y, int sum, int num)
    {
        if(num == n) {
            v11[x].push_back(sum ^ a[x][y]);
            return ;
        }
        if(x + 1 <= n) dfs11(x + 1, y, sum ^ a[x + 1][y], num + 1);
        if(y + 1 <= n) dfs11(x, y + 1, sum ^ a[x][y + 1], num + 1);
    }
    
    void dfsnn(int x, int y, int sum, int num)
    {
        if(num == n) {
            vnn[x].push_back(e ^ sum);
            return ;
        }
        if(x - 1 >= 1) dfsnn(x - 1, y, sum ^ a[x - 1][y], num + 1);
        if(y - 1 >= 1) dfsnn(x, y - 1, sum ^ a[x][y - 1], num + 1);
    }
    
    signed main()
    {
        scanf("%d %d", &n, &e);
        for(int i = 1; i <= n; ++ i) {
            for(int j = 1; j <= n; ++ j) {
                scanf("%d", &a[i][j]);
            }
        }
    
        dfs11(1, 1, a[1][1], 1);
        dfsnn(n, n, a[n][n], 1);
    
        int ans = 0;
        for(int i = 1; i <= n; ++ i) {
            memset(tree, 0, sizeof tree);
            cnt = 1;
            for(int j = 0; j < v11[i].size(); ++ j) {
                add(v11[i][j]);
            }
            for(int j = 0; j < vnn[i].size(); ++ j) {
                ans = max(ans, query(vnn[i][j]));
            }
        }
    
        printf("%d\n", ans);
    
        return 0;
    }
    
    /*
    
      Rejoicing in hope, patient in tribulation .
    
    */
    
    
    cs