ARTICLE · 1387180
华为机考非AI方向11月20日笔试题与解析
写在前面
本次给大家带来2026年11月20日华为非AI方向笔试题的3道题,
涉及到的岗位是:通软,嵌软,测试,普通算法(岗位名中不包含AI)以及数据科学,考试内容和报考部门无关,只和岗位有关。
需要我整理的机考一周速成题单可访问文章底部左侧:阅读原文
第1题-水晶段封印统计(150分)
题目内容
古老星界的边界上,立着一座长阵,是用魔法水晶一颗接一颗排出来的。
每颗水晶所含的魔力或正或负,水晶首尾相接,连成一道始终不断的轨迹。
传说里写着:某一段连续的水晶,其魔力加在一起若恰好是星轨密钥,这一段便会一同亮起,结出一枚安稳的封印,把这片魔法领域护在其中。
你被挑中做星轨巫师,眼下要办两件事:
这样的安稳封印一共有多少枚;
凡是能结出封印的连续水晶段,最短的那一段由几颗水晶组成?
倘若连一段能结出封印的水晶都没有,次数就记,最短长度记作。
输入描述
第一行给出两个整数:水晶的颗数,以及目标魔力之和。
第二行给出个整数,逐个描述每颗水晶的魔力,其中第颗的值记为。
输出描述
输出一行,含两个整数:封印被触发的次数、最短封印所含的颗数;若一条合法封印也没有,次数输出,长度输出。
数据范围:
这里的「连续一段水晶」,限定为长度至少的连续子段 封印被触发的次数上限为,约,务必用位整数存储和输出
样例1
输入
输出
说明
下标到:,占了颗 下标到:,占了颗 下标单独一颗:,只占颗 下标到:,占了颗
合起来封印共有枚,最短的一枚只占颗。
题解
解题思路
题目要的是两件事:和恰好为的连续水晶段有多少个,以及其中最短的有几颗。
把「连续段求和」换成「两个前缀和相减」。记为前颗水晶的魔力加总,并令,那么第颗到第颗的和就是,条件「和等于」于是等价于。
固定右端点,只要在前面所有里数一数有几个等于,这几个各自对应一段合法封印,个数就是右端点取时的封印数。段长是,要让长度最短,就得取最大的那个,也就是该前缀和最近一次出现的下标,所以哈希表里既要存出现次数,也要存最近下标。
从左往右扫:先用查表,累加次数、更新最短长度,再把记录进表。要提前放进表里,因为以第颗水晶开头的那一段,减掉的是空前缀。
与所有一共个前缀和,每个只查一次、插一次,用哈希表即可做到线性。
复杂度分析
时间:整个数组只扫一遍,每次哈希表的查询与插入是均摊。
空间:最坏情况下个前缀和互不相同,两张哈希表各存项。
代码实现
python代码(C++和JAVA代码见平台)
第2题-元素迷宫封印路径(150分)
题目内容
在艾尔德里亚王国之中,古老的混沌魔王如今即将苏醒。王国里最年轻的那位元素法师艾莉娅,就这样接到了智者赋予她的最终试炼:
那位智者神情严肃地叮嘱她:“年轻的法师,若真要封印混沌魔王,你就得先穿越元素迷宫,再去完成最终试炼。”
迷宫里的规则详解如下:
整座迷宫由个房间拼成,每个房间都蕴含一种元素能量,取值到:
法师每次只能向右或者向下移动,从左上角那格出发,抵达终点,也就是右下角的封印法阵。
第一条规则:
沿途收集到的元素能量,加起来必须恰好等于点。(数量太少的话无法形成封印,太多了则会引发能量反噬)
第二条规则:
阳炎元素(能量值为奇数:):炽热狂暴的红色元素,越烧越旺
寒冰元素(能量值为偶数:):冰冷沉寂的蓝色元素,寒气逼人
至于混沌元素(能量值等于):混乱中立的灰色元素,不偏不倚
同种元素连续收集就会致命!接连激活两个阳炎元素(都是奇数),炽热的能量就会把你焚烧;接连收集两个寒冰元素(非零偶数,如),极寒的能量会把你冻结。
特别地,这里要说明:混沌元素()不属于阳炎,同样不属于寒冰,它一点点限制都没有——混沌元素能同任何元素(含另一个混沌元素)相邻,再连着经过好几个混沌元素,都同样安全。
智者最后长久地凝视着艾莉娅,开口问道:
“年轻的法师,在这处处危机四伏的迷宫里,你能数出多少种方法,安全抵达封印法阵(也就是迷宫终点右下角),并且积累到恰好点能量?”
输入描述
第一行:给出三个整数(,),相邻两个数之间用一个空格隔开
:迷宫的行数与列数
:激活封印法阵(它就在迷宫终点)所必需的准确能量值
下面紧跟行:每行个到的整数,依次给出迷宫里每个房间的元素能量
输出描述
一个整数,代表满足全部生存条件的走法数量
样例1
输入
输出
说明
全部条走法里,只有下面条同时满足两个条件:
路径一:(阳)(冰)(阳)(冰)(阳),能量和为。 路径二:(阳)(冰)(阳)(冰)(阳),能量和为。
这两条走法上阳炎与寒冰一直交替出现,没有连着收两次同种元素。剩下的条走法分别拾取到、、、,能量和依次是、、、,都凑不出,因此不计入答案。
题解
解题思路
法师只能向右或向下走,从到的每条走法都恰好经过个房间,长度固定。所以这只是一次普通的网格路径计数,只多了能量和与元素类型两个条件。 关键观察:规则二管的是「路径上紧挨着的两个房间」。当逐格把路径往下铺时,已经收下的元素不可能再和后面的房间冲突,真正会影响后续判定的只有两件事:到目前为止收了多少能量,以及上一个房间是哪一类元素(、奇数、非零偶数)。因此状态只需要带这两维。 于是设表示走到、能量和为、当前房间类型为的走法数,其中表示房间是混沌元素,表示阳炎元素(奇数),表示寒冰元素(非零偶数)。 转移就是把来自上方与左方的走法合并,再按当前房间的类型决定能不能收:当前房间是时与谁相邻都安全,直接累加到;当前房间是奇数时只允许从的状态过来;当前房间是非零偶数时只允许从的状态过来。能量和一旦超过就不必再往下走,因为房间能量都不小于,后面只会更多。 答案为终点上能量和恰好等于的三类状态之和。起点要单独初始化:它没有前一个房间,按自己的类型直接落位。 这样做的正确性在于:一条完整走法被唯一地拆成「走到每一格」的前缀,而上面记录的信息恰好足够判断下一步是否合法,所以每条合法走法被计入且只被计入一次。
复杂度分析
时间复杂度:,每个格子的每种能量和、每种来源类型都只被常数次访问。 空间复杂度:,与状态数同阶;、时状态总数不到。
代码实现
python代码(C++和JAVA代码见平台)
第3题-巡检机器人补电路线(300分)
题目内容
某城市里早就部署好了智能电网监控系统,还要派出巡检机器人去维护关键节点。地图上一共包含个节点(从编号到),节点就是总部,另外个关键节点都需要维护。
节点之间由双向道路连接,机器人通行时消耗的电量就等于道路的长度。
每个关键节点都具备补电能力,机器人一旦到达该关键节点,电量便增加一个固定数值(机器人补后电量不得高于最大电量),总部与非关键节点都不可以补电。
机器人需要从总部出发,初始电量就是最大电量,把所有个关键节点遍历一遍后再返回总部。
请计算完成该任务所需的最小总行驶距离。若任务无法完成,就输出。
输入描述
第一行:给定四个整数,依次是总节点个数、节点间总路径个数、关键节点个数、机器人最大电量;
紧随其后行,每行有三个整数,代表节点间的道路长度是;
再往下的一行是个整数,表示各关键节点的编号(编号在到之间,不包含总部节点);
末尾一行:个整数,表示这些关键节点机器人每经过一次可以补充的电量数值,任务全程中每次经过该节点都能补充电量。
约束说明:,,,,,。
输出描述
一个整数:机器人跑完巡检任务所需的最小总行驶距离;若任务不可行,则输出。
样例1
输入
输出
说明
路径:,距离。
出发电量,从节点到节点,用掉电量,补上电量;多于,所以机器人只能补到,剩下的电量; 从节点开往节点,消耗电量,再补充电量;正好等于,剩余电量; 从节点原路折回节点,用掉电量,节点又补上电量;少于,剩下的电量; 从节点回到节点,用掉电量,总部不再补电;少于,剩下的电量;全程电量都够用。
题解
题目分析
一条可行路线可以拆成「总部 → 第个关键节点 → 第个关键节点 → … → 总部」。相邻两个关键节点之间的那一段只经过非关键节点,没有地方补电,所以这段路纯粹是消耗;把它换成这两点之间的最短路只会更省电,也不会让后面更吃亏(最短路可能顺路经过别的关键节点,那只会多补一次电)。因此先用求出任意两点之间的最短路,之后只关心关键节点之间怎么跳。 问题于是变成:从总部出发,按某种顺序把个关键节点都走到,最后回总部;每次从跳到花掉的电量,到达时补上(补后不超过上限)。状态只需要「已经巡检过的集合、当前停在关键节点、剩余电量」这三样,要求的答案就是这些状态上的最短路。 状态之间的转移只依赖,边权非负,所以用优先队列按已行驶距离从小到大取状态:取到「已包含全部关键节点」的状态时,用更新答案;某个状态弹出时已经不短于当前答案,就可以直接结束。 剪枝是这道题的关键:同一个上,如果此前已经确定过一个电量更大(或相等)的状态,那么新状态一定不优——此前那个状态走得并不更远,电量还更多,它能走的后续路线新状态都能走。于是每个只记录已经确定过的最大电量 best,电量不超过它就丢掉。还要允许关键节点被重复经过。有的图里唯一的补电点必须先走过一次,之后回头再补一次电,才够走到下一个关键节点。集合只表示「去没去过」,所以从跳到已经属于的也是合法转移,此时不变。 所有状态都凑不出「全部巡检完并且能回到总部」时,输出。
复杂度分析
的时间是,空间是。 状态最多个,每个状态有个转移,时间,空间(优先队列里最多存这么多状态)。 有了上面的剪枝,每个只会留下电量一次比一次大的少量状态,实际规模远小于这个上界。
代码实现
python代码(C++和JAVA代码见平台)
PC端刷题:CodeFun2000.com















































































