題目描述

筱瑪是個快樂的男孩子。
寒假終于到了，筱瑪決定請他的朋友們一起來玩迷陣探險。
迷陣可以看做一個$\mathrm{n\times nn\times n的矩陣A，每個格子上有一個有一個數(shù)Ai,j。\; 入口在左上角的(1,1)處，出口在右下角的(n,n)處。每一步都只能向下或向右移動一格。最后能獲得的經(jīng)驗值為初始經(jīng)驗e與路徑上經(jīng)過的所有數(shù)的權(quán)值異或和。\; 求筱瑪最大可能獲得的經(jīng)驗值。}$

輸入描述:

第一行兩個整數(shù)n和e。
接下來n行，每行n個整數(shù)，描述矩陣A。

輸出描述:

一個整數(shù)，表示筱瑪最大可能獲得的經(jīng)驗值。 示例1

輸入

復(fù)制 5 2 3 4 7 2 6 3 5 2 9 0 3 8 5 7 3 2 5 3 1 4 9 8 6 3 5

輸出

復(fù)制 15

鏈接：https://ac.nowcoder.com/acm/contest/545/D

思路：顯然我們直接搜等于是在搜一顆二叉樹，復(fù)雜度O（2^40）左右，肯定超時。但是我們可以用其他方法搜，先從左上角搜，，搜到對角線，然后把所有答案保存在01字典樹里。再從右下角往回搜，遇到對角線直接在字典樹搜最大異或，取最大值。

代碼：

#include<cmath> #include<cstdio> #include<vector> #include<cstring> #include <iostream> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 20 + 10; const int INF = 0x3f3f3f3f; struct node{node* Next[2];node(){for(int i = 0; i < 2; i++)Next[i] = NULL;} }; node* e[maxn]; //走到對角線（含） int mp[maxn][maxn]; int n, s; void add(int x, int pos){node* a = e[pos];for(int i = 31; i >=0; i--){int v = (x >> i) & 1;if(a ->Next[v] == NULL)a ->Next[v] = new node();a = a ->Next[v];} } int query(int x, int pos){node* a = e[pos];int ret = 0;for(int i = 31; i >= 0; i--){int v = (x >> i) & 1;if(a ->Next[!v] != NULL){a = a ->Next[!v];ret += (1 << i);}else a = a ->Next[v];}return ret; } void dfs(int x, int y, int sum){if(x + y == n + 1){add(sum ^ mp[x][y], x);return;}dfs(x + 1, y, sum ^ mp[x][y]);dfs(x, y + 1, sum ^ mp[x][y]); } int Max; void dfsBack(int x, int y, int sum){if(x + y == n + 1){Max = max(query(sum, x), Max);return;}dfsBack(x - 1, y, sum ^ mp[x][y]);dfsBack(x, y - 1, sum ^ mp[x][y]); } int main(){scanf("%d%d", &n, &s);for(int i = 1; i <= n; i++){e[i] = new node();for(int j = 1; j <= n; j++){scanf("%d", &mp[i][j]);}}dfs(1, 1, s);Max = -1;dfsBack(n, n, 0);printf("%d\n", Max);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/KirinSB/p/10627859.html

總結(jié)

以上是生活随笔為你收集整理的newcoder 筱玛的迷阵探险（搜索 + 01字典树）题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。