夜雨聆风学习资料网

ARTICLE · 1387180

华为机考非AI方向11月20日笔试题与解析

华为机考非AI方向11月20日笔试题与解析

写在前面

本次给大家带来2026年11月20日华为非AI方向笔试题的3道题,

涉及到的岗位是:通软,嵌软,测试,普通算法(岗位名中不包含AI)以及数据科学,考试内容和报考部门无关,只和岗位有关。

需要我整理的机考一周速成题单可访问文章底部左侧:阅读原文

题号
题目
核心做法
1
水晶段封印统计
哈希表
2
元素迷宫封印路径
动态规划
3
巡检机器人补电路线
最短路算法

第1题-水晶段封印统计(150分)

题目内容

古老星界的边界上,立着一座长阵,是用魔法水晶一颗接一颗排出来的。

每颗水晶所含的魔力或正或负,水晶首尾相接,连成一道始终不断的轨迹。

传说里写着:某一段连续的水晶,其魔力加在一起若恰好是星轨密钥,这一段便会一同亮起,结出一枚安稳的封印,把这片魔法领域护在其中。

你被挑中做星轨巫师,眼下要办两件事:

这样的安稳封印一共有多少枚;

凡是能结出封印的连续水晶段,最短的那一段由几颗水晶组成?

倘若连一段能结出封印的水晶都没有,次数就记,最短长度记作。

输入描述

第一行给出两个整数:水晶的颗数,以及目标魔力之和。

第二行给出个整数,逐个描述每颗水晶的魔力,其中第颗的值记为。

输出描述

输出一行,含两个整数:封印被触发的次数、最短封印所含的颗数;若一条合法封印也没有,次数输出,长度输出。

数据范围:

  • 这里的「连续一段水晶」,限定为长度至少的连续子段
  • 封印被触发的次数上限为,约,务必用位整数存储和输出

样例1

输入

7 53 -1 4 2 -6 5 1

输出

4 1

说明

  • 下标到:,占了颗
  • 下标到:,占了颗
  • 下标单独一颗:,只占颗
  • 下标到:,占了颗

合起来封印共有枚,最短的一枚只占颗。

题解

解题思路

题目要的是两件事:和恰好为的连续水晶段有多少个,以及其中最短的有几颗。

把「连续段求和」换成「两个前缀和相减」。记为前颗水晶的魔力加总,并令,那么第颗到第颗的和就是,条件「和等于」于是等价于。

固定右端点,只要在前面所有里数一数有几个等于,这几个各自对应一段合法封印,个数就是右端点取时的封印数。段长是,要让长度最短,就得取最大的那个,也就是该前缀和最近一次出现的下标,所以哈希表里既要存出现次数,也要存最近下标。

从左往右扫:先用查表,累加次数、更新最短长度,再把记录进表。要提前放进表里,因为以第颗水晶开头的那一段,减掉的是空前缀。

与所有一共个前缀和,每个只查一次、插一次,用哈希表即可做到线性。

复杂度分析

时间:整个数组只扫一遍,每次哈希表的查询与插入是均摊。

空间:最坏情况下个前缀和互不相同,两张哈希表各存项。

代码实现

python代码(C++和JAVA代码见平台)

defcount_seals(m, t, w):"""返回 (封印数量, 最短封印的颗数);没有任何合法封印时长度为 -1。"""    cnt = {0: 1}      # 前缀和 -> 出现次数,空前缀 0 先记一次    last = {0: 0}     # 前缀和 -> 最近一次出现的下标    s = 0# 当前前缀和    ans = 0# 封印数量    best = -1# 最短长度for i inrange(1, m + 1):        s += w[i - 1]        need = s - t                      # 需要的旧前缀和if need in cnt:                   # 前面出现过 need,这些位置都能结出封印            ans += cnt[need]            length = i - last[need]       # 用最近的下标,长度才最短if best == -1or length < best:                best = length        cnt[s] = cnt.get(s, 0) + 1# 当前前缀和计数加一        last[s] = i                       # 下标越大越优,直接覆盖return ans, bestm, t = map(int, input().split())w = list(map(int, input().split()))ans, best = count_seals(m, t, w)print(ans, best)

第2题-元素迷宫封印路径(150分)

题目内容

在艾尔德里亚王国之中,古老的混沌魔王如今即将苏醒。王国里最年轻的那位元素法师艾莉娅,就这样接到了智者赋予她的最终试炼:

那位智者神情严肃地叮嘱她:“年轻的法师,若真要封印混沌魔王,你就得先穿越元素迷宫,再去完成最终试炼。”

迷宫里的规则详解如下:

整座迷宫由个房间拼成,每个房间都蕴含一种元素能量,取值到:

法师每次只能向右或者向下移动,从左上角那格出发,抵达终点,也就是右下角的封印法阵。

第一条规则:

沿途收集到的元素能量,加起来必须恰好等于点。(数量太少的话无法形成封印,太多了则会引发能量反噬)

第二条规则:

阳炎元素(能量值为奇数:):炽热狂暴的红色元素,越烧越旺

寒冰元素(能量值为偶数:):冰冷沉寂的蓝色元素,寒气逼人

至于混沌元素(能量值等于):混乱中立的灰色元素,不偏不倚

同种元素连续收集就会致命!接连激活两个阳炎元素(都是奇数),炽热的能量就会把你焚烧;接连收集两个寒冰元素(非零偶数,如),极寒的能量会把你冻结。

特别地,这里要说明:混沌元素()不属于阳炎,同样不属于寒冰,它一点点限制都没有——混沌元素能同任何元素(含另一个混沌元素)相邻,再连着经过好几个混沌元素,都同样安全。

智者最后长久地凝视着艾莉娅,开口问道:

“年轻的法师,在这处处危机四伏的迷宫里,你能数出多少种方法,安全抵达封印法阵(也就是迷宫终点右下角),并且积累到恰好点能量?”

输入描述

第一行:给出三个整数(,),相邻两个数之间用一个空格隔开

:迷宫的行数与列数

:激活封印法阵(它就在迷宫终点)所必需的准确能量值

下面紧跟行:每行个到的整数,依次给出迷宫里每个房间的元素能量

输出描述

一个整数,代表满足全部生存条件的走法数量

样例1

输入

3 3 273 8 56 7 21 4 9

输出

2

说明

全部条走法里,只有下面条同时满足两个条件:

  • 路径一:(阳)(冰)(阳)(冰)(阳),能量和为。
  • 路径二:(阳)(冰)(阳)(冰)(阳),能量和为。

这两条走法上阳炎与寒冰一直交替出现,没有连着收两次同种元素。剩下的条走法分别拾取到、、、,能量和依次是、、、,都凑不出,因此不计入答案。

题解

解题思路

  • 法师只能向右或向下走,从到的每条走法都恰好经过个房间,长度固定。所以这只是一次普通的网格路径计数,只多了能量和与元素类型两个条件。
  • 关键观察:规则二管的是「路径上紧挨着的两个房间」。当逐格把路径往下铺时,已经收下的元素不可能再和后面的房间冲突,真正会影响后续判定的只有两件事:到目前为止收了多少能量,以及上一个房间是哪一类元素(、奇数、非零偶数)。因此状态只需要带这两维。
  • 于是设表示走到、能量和为、当前房间类型为的走法数,其中表示房间是混沌元素,表示阳炎元素(奇数),表示寒冰元素(非零偶数)。
  • 转移就是把来自上方与左方的走法合并,再按当前房间的类型决定能不能收:当前房间是时与谁相邻都安全,直接累加到;当前房间是奇数时只允许从的状态过来;当前房间是非零偶数时只允许从的状态过来。能量和一旦超过就不必再往下走,因为房间能量都不小于,后面只会更多。
  • 答案为终点上能量和恰好等于的三类状态之和。起点要单独初始化:它没有前一个房间,按自己的类型直接落位。
  • 这样做的正确性在于:一条完整走法被唯一地拆成「走到每一格」的前缀,而上面记录的信息恰好足够判断下一步是否合法,所以每条合法走法被计入且只被计入一次。

复杂度分析

  • 时间复杂度:,每个格子的每种能量和、每种来源类型都只被常数次访问。
  • 空间复杂度:,与状态数同阶;、时状态总数不到。

代码实现

python代码(C++和JAVA代码见平台)

defsolve(h, w, K, g):# dp[i][j][s][p]:走到 (i,j)、能量和为 s、当前房间类型为 p 时的走法数# p = 0 表示房间是 0(混沌),p = 1 表示奇数(阳炎),p = 2 表示非零偶数(寒冰)    dp = [[[[0] * 3for _ inrange(K + 1)] for _ inrange(w)] for _ inrange(h)]    v0 = g[0][0]if v0 <= K:        p0 = 0if v0 == 0else (1if v0 % 2 == 1else2)        dp[0][0][v0][p0] = 1for i inrange(h):for j inrange(w):if i == 0and j == 0:continue            v = g[i][j]for s inrange(K + 1):for p inrange(3):                    c = 0if i > 0:                        c += dp[i - 1][j][s][p]if j > 0:                        c += dp[i][j - 1][s][p]if c == 0:continueif v == 0:# 混沌元素跟谁相邻都安全                        dp[i][j][s][0] += celif v % 2 == 1:# 上一个房间是阳炎时,不能再收一个阳炎if p != 1and s + v <= K:                            dp[i][j][s + v][1] += celse:# 上一个房间是寒冰时,不能再收一个寒冰if p != 2and s + v <= K:                            dp[i][j][s + v][2] += creturn dp[h - 1][w - 1][K][0] + dp[h - 1][w - 1][K][1] + dp[h - 1][w - 1][K][2]defmain():    h, w, K = map(int, input().split())    g = [list(map(int, input().split())) for _ inrange(h)]print(solve(h, w, K, g))main()

第3题-巡检机器人补电路线(300分)

题目内容

某城市里早就部署好了智能电网监控系统,还要派出巡检机器人去维护关键节点。地图上一共包含个节点(从编号到),节点就是总部,另外个关键节点都需要维护。

节点之间由双向道路连接,机器人通行时消耗的电量就等于道路的长度。

每个关键节点都具备补电能力,机器人一旦到达该关键节点,电量便增加一个固定数值(机器人补后电量不得高于最大电量),总部与非关键节点都不可以补电。

机器人需要从总部出发,初始电量就是最大电量,把所有个关键节点遍历一遍后再返回总部。

请计算完成该任务所需的最小总行驶距离。若任务无法完成,就输出。

输入描述

第一行:给定四个整数,依次是总节点个数、节点间总路径个数、关键节点个数、机器人最大电量;

紧随其后行,每行有三个整数,代表节点间的道路长度是;

再往下的一行是个整数,表示各关键节点的编号(编号在到之间,不包含总部节点);

末尾一行:个整数,表示这些关键节点机器人每经过一次可以补充的电量数值,任务全程中每次经过该节点都能补充电量。

约束说明:,,,,,。

输出描述

一个整数:机器人跑完巡检任务所需的最小总行驶距离;若任务不可行,则输出。

样例1

输入

5 6 2 120 1 20 2 51 2 21 3 62 4 34 3 31 34 6

输出

16

说明

路径:,距离。

  • 出发电量,从节点到节点,用掉电量,补上电量;多于,所以机器人只能补到,剩下的电量;
  • 从节点开往节点,消耗电量,再补充电量;正好等于,剩余电量;
  • 从节点原路折回节点,用掉电量,节点又补上电量;少于,剩下的电量;
  • 从节点回到节点,用掉电量,总部不再补电;少于,剩下的电量;全程电量都够用。

题解

题目分析

  • 一条可行路线可以拆成「总部 → 第个关键节点 → 第个关键节点 → … → 总部」。相邻两个关键节点之间的那一段只经过非关键节点,没有地方补电,所以这段路纯粹是消耗;把它换成这两点之间的最短路只会更省电,也不会让后面更吃亏(最短路可能顺路经过别的关键节点,那只会多补一次电)。因此先用求出任意两点之间的最短路,之后只关心关键节点之间怎么跳。
  • 问题于是变成:从总部出发,按某种顺序把个关键节点都走到,最后回总部;每次从跳到花掉的电量,到达时补上(补后不超过上限)。状态只需要「已经巡检过的集合、当前停在关键节点、剩余电量」这三样,要求的答案就是这些状态上的最短路。
  • 状态之间的转移只依赖,边权非负,所以用优先队列按已行驶距离从小到大取状态:取到「已包含全部关键节点」的状态时,用更新答案;某个状态弹出时已经不短于当前答案,就可以直接结束。
  • 剪枝是这道题的关键:同一个上,如果此前已经确定过一个电量更大(或相等)的状态,那么新状态一定不优——此前那个状态走得并不更远,电量还更多,它能走的后续路线新状态都能走。于是每个只记录已经确定过的最大电量 best,电量不超过它就丢掉。
  • 还要允许关键节点被重复经过。有的图里唯一的补电点必须先走过一次,之后回头再补一次电,才够走到下一个关键节点。集合只表示「去没去过」,所以从跳到已经属于的也是合法转移,此时不变。
  • 所有状态都凑不出「全部巡检完并且能回到总部」时,输出。

复杂度分析

  • 的时间是,空间是。
  • 状态最多个,每个状态有个转移,时间,空间(优先队列里最多存这么多状态)。
  • 有了上面的剪枝,每个只会留下电量一次比一次大的少量状态,实际规模远小于这个上界。

代码实现

python代码(C++和JAVA代码见平台)

import heapqINF = float('inf')defread_ints(cnt):"""按行读入,凑够 cnt 个整数为止(题面保证同一组数据在一行里)"""    got = []whilelen(got) < cnt:        got += list(map(int, input().split()))return gotdefsolve(n, edges, keys, rec, cap):# 先用 Floyd 求出任意两个节点之间最省电的走法长度    d = [[INF] * n for _ inrange(n)]for i inrange(n):        d[i][i] = 0for x, y, z in edges:if z < d[x][y]:            d[x][y] = z            d[y][x] = zfor t inrange(n):        dt = d[t]for i inrange(n):            dit = d[i][t]if dit == INF:continue            di = d[i]for j inrange(n):                cur = dit + dt[j]if cur < di[j]:                    di[j] = cur    k = len(keys)    full = (1 << k) - 1# 状态:已经巡检过的关键节点集合 mask、当前停在关键节点 i、剩余电量 fuel# best[mask * k + i] 记录该状态已确定过的最大剩余电量,电量更小的状态一定不优    best = {}    pq = []for i inrange(k):        dist = d[0][keys[i]]if dist <= cap:            fuel = cap - dist + rec[i]if fuel > cap:                fuel = cap            heapq.heappush(pq, (dist, 1 << i, i, fuel))    ans = INFwhile pq:        dist, mask, i, fuel = heapq.heappop(pq)if dist >= ans:break        state = mask * k + iif best.get(state, -1) >= fuel:continue        best[state] = fuel        node = keys[i]if mask == full:# 全部巡检完,直接回总部            back = d[node][0]if fuel >= back and dist + back < ans:                ans = dist + backcontinuefor j inrange(k):if j == i:continue            cost = d[node][keys[j]]if cost > fuel:continue            nxt_mask = mask | (1 << j)            nxt_dist = dist + costif nxt_dist >= ans:continue            nxt_fuel = fuel - cost + rec[j]if nxt_fuel > cap:                nxt_fuel = cap            nxt_state = nxt_mask * k + jif best.get(nxt_state, -1) >= nxt_fuel:continue            heapq.heappush(pq, (nxt_dist, nxt_mask, j, nxt_fuel))return -1if ans == INF else ansdefmain():    n, m, k, cap = read_ints(4)    edges = []for _ inrange(m):        x, y, z = read_ints(3)        edges.append((x, y, z))    keys = read_ints(k)    rec = read_ints(k)print(solve(n, edges, keys, rec, cap))main()

PC端刷题:CodeFun2000.com

手机端刷题:塔子哥刷题宝

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料