本文主要是介绍牛客练习赛37C 筱玛的迷阵探险 折半搜索+trie,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 524288K,其他语言1048576K
64bit IO Format: %lld
题目描述
筱玛是个快乐的男孩子。
寒假终于到了,筱玛决定请他的朋友们一起来玩迷阵探险。
迷阵可以看做一个n\times nn×n的矩阵A,每个格子上有一个有一个数Ai,j。
入口在左上角的(1,1)处,出口在右下角的(n,n)处。每一步都只能向下或向右移动一格。最后能获得的经验值为初始经验e与路径上经过的所有数的权值异或和。
求筱玛最大可能获得的经验值。
输入描述:
第一行两个整数n和e。 接下来n行,每行n个整数,描述矩阵A。
输出描述:
一个整数,表示筱玛最大可能获得的经验值。
示例1
输入
复制
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
输出
复制
15
备注:
1≤n≤20;0≤e,Ai,j<231
直接暴力是肯定不行的,所以我们可以折半搜索,我们保存正方形对角线上的每一点 建立字典树,然后倒着搜索寻求最大值即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxnode=200000+100;
const int sigma_size=3;
struct Trie
{int ch[maxnode<<4][sigma_size];//注意要多开10倍int sz;void clear(){sz=1;memset(ch[0],0,sizeof(ch[0]));}void insert(ll x){int u=0;for(int i=31; i>=0; i--){int id=(x>>i)&1;//取出第i位if(ch[u][id]==0){ch[u][id]=sz;memset(ch[sz],0,sizeof(ch[sz]));sz++;}u=ch[u][id];}}ll find(ll x){ll ans=0,u=0;for(int i=31; i>=0; i--){int id=(x>>i)&1;int y=id^1; //找与id不同的if(ch[u][y]==0){u=ch[u][id];ans<<=1; //相同为0,ans=ans*2}else{u=ch[u][y];ans=ans<<1|1; //不同为1,ans=ans*2+1}}return ans;}
};
Trie trie[25];
int n;
ll e;
ll mp[25][25];
ll ans=0;
void dfs1(int x,int y,int step,ll val)
{if(step==n){trie[x].insert(val^mp[x][y]);return ;}if(x+1<=n)dfs1(x+1,y,step+1,val^mp[x][y]);if(y+1<=n)dfs1(x,y+1,step+1,val^mp[x][y]);
}
void dfs2(int x,int y,int step,ll val)
{if(step==n){ans=max(ans,trie[x].find(val));return ;}if(x-1>=1)dfs2(x-1,y,step+1,val^mp[x][y]);if(y-1>=1)dfs2(x,y-1,step+1,val^mp[x][y]);
}int main()
{scanf("%d%lld",&n,&e);for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)scanf("%lld",&mp[i][j]);ans=0;for(int i=1;i<=n;i++)trie[i].clear();dfs1(1,1,1,e);dfs2(n,n,1,0);printf("%lld\n",ans);return 0;
}
这篇关于牛客练习赛37C 筱玛的迷阵探险 折半搜索+trie的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!