牛客练习赛37C 筱玛的迷阵探险 折半搜索+trie

2023-11-09 23:50

本文主要是介绍牛客练习赛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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/379190

相关文章

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

浙大数据结构:04-树7 二叉搜索树的操作集

这道题答案都在PPT上,所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现,小就进左子树,大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo

【python计算机视觉编程——7.图像搜索】

python计算机视觉编程——7.图像搜索 7.图像搜索7.1 基于内容的图像检索(CBIR)从文本挖掘中获取灵感——矢量空间模型(BOW表示模型)7.2 视觉单词**思想****特征提取**: 创建词汇7.3 图像索引7.3.1 建立数据库7.3.2 添加图像 7.4 在数据库中搜索图像7.4.1 利用索引获取获选图像7.4.2 用一幅图像进行查询7.4.3 确定对比基准并绘制结果 7.

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>