大厂真题 / 华为
华为 2026-10-28 笔试真题 - 研发岗
本场考试概述
考试时间：2026年10月28日
考试岗位：研发岗
难度评级：中等
考点分析：
- 第一题：有向图路径计数、分步动态规划（中等）。
- 第二题：稀疏表示、大整数加法、进位模拟（中等）。
- 第三题：资金约束下的状态机动态规划（中等偏难）。
建议策略：
- 第一题以“走了多少条边”为阶段，严格只从上一层状态转移，允许重复经过节点。
- 第二题按指数存储非零数字位，进位只向更高指数传播，避免按最高指数开数组。
- 第三题分别记录空仓和持仓资金，并让每天的状态只从前一天转移，避免同日买卖。
第 1 题：物流中转网络
题目描述
有 $n$ 个中转站，编号为 $1$ 到 $n$，由 $m$ 条单向运输线路连接。给定起点 start、终点 target 和整数 $k$，求从起点到终点恰好经过 $k$ 条线路的不同路径数量。路径允许重复经过同一中转站，但同一对站点之间没有重边。
输入格式与约束
- 第一行包含 $n,m$，满足 $1\le n\le20$、$1\le m\le200$。
- 第二行包含
start target k，其中 $1\le start,target\le n$、$1\le k\le10$。 - 接下来 $m$ 行，每行包含一条有向边
from to，满足 $1\le from,to\le n$ 且from与to不同。
输出格式
输出恰好经过 $k$ 条线路的路径数；不存在符合条件的路径时输出 $0$。
样例 1
输入
4 6
1 4 4
1 2
2 1
2 3
3 2
3 4
2 4
输出
2
解释：符合条件的路径是 $1\to2\to1\to2\to4$ 和 $1\to2\to3\to2\to4$。
样例 2
输入
4 5
1 4 2
1 2
1 3
2 3
2 4
3 4
输出
2
解释：恰好经过两条线路的路径为 $1\to2\to4$ 和 $1\to3\to4$。
样例 3
输入
3 3
1 3 1
1 2
2 3
1 3
输出
1
解释：只经过一条线路时，只有直接从中转站 $1$ 到 $3$ 的路径符合要求。
思路分析
第一步：把“恰好走 $k$ 步”作为动态规划阶段。
令 dp[v] 表示当前阶段从起点出发、走了指定条数线路后到达站点 $v$ 的路径数。走 $0$ 条线路时，只有起点可达，因此 dp[start] = 1，其余状态为 $0$。
第二步：沿每条有向边推进一层。
若边为 $u\to v$，当前所有到达 $u$ 的路径再走这条边，便成为下一层到达 $v$ 的路径。因此对每条边执行 next_dp[v] += dp[u]。每一轮都从旧数组创建新数组，完成整轮后再替换状态，确保每次转移恰好增加一条线路。
题目允许重复经过站点，所以不应排除已经访问过的点。不同路径由所选线路的顺序区分；逐层沿边累加会把每条长度为 $k$ 的线路序列恰好计数一次。
第三步：读取第 $k$ 层的目标状态。
重复上述过程 $k$ 次后，dp[target] 即为答案。暴力枚举路径可能随 $k$ 指数增长；这里每一层只扫描 $m$ 条边，在给定的小范围内足够高效。
正确性证明
走 $0$ 条线路时，到达起点的空路径恰好有一条，到达其他站点的路径数为零，初始化正确。
假设当前 dp[u] 正确统计走了 $i$ 条线路后到达 $u$ 的路径数。每条长度为 $i+1$ 且终点为 $v$ 的路径，都唯一地由一条长度为 $i$、终点为某个 $u$ 的路径及最后一条边 $u\to v$ 组成。对所有边执行累加会完整且不重复地构造这些路径。因此下一层数组正确统计走 $i+1$ 条线路的路径数。
归纳可知，执行 $k$ 轮后 dp[target] 正是题目所求路径数。
题解代码
import sys
input = sys.stdin.readline
def count_paths(n, edges, start, target, steps):
dp = [0] * (n + 1)
dp[start] = 1
for _ in range(steps):
next_dp = [0] * (n + 1)
for source, destination in edges:
next_dp[destination] += dp[source]
dp = next_dp
return dp[target]
def solve():
n, m = map(int, input().split())
start, target, steps = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
print(count_paths(n, edges, start, target, steps))
if __name__ == '__main__':
solve()
复杂度分析
时间复杂度：$O(km)$。每一层遍历全部 $m$ 条线路，共推进 $k$ 层。
空间复杂度：$O(n+m)$。存储边以及当前层和下一层的路径计数。
第 2 题：大数加法
题目描述
输入两个用稀疏编码表示的非负整数，输出它们的和，仍使用相同编码。
每个非零片段写成 xxx:n，表示整数 $xxx\times10^n$。片段按高位到低位排列，xxx 由一至三位数字组成且不包含 $0$；连续的非零数字尽量组成最多三位的片段。整个整数以 0:0 结束，零本身也写作 0:0。
例如，整数 $1234005006$ 编码为 123:7 4:6 5:3 6:0 0:0。
输入格式与约束
- 输入两行，每行是一个非负整数的稀疏编码。
- 每个片段的指数 $n$ 满足 $0\le n<2{,}000{,}000{,}000$；系数片段长度不超过 $3$，且内部不含 $0$。
- 单个编码字符串长度小于 $512$，两个数的和的最高指数小于 $2{,}000{,}000{,}000$。
- 每个整数的编码均以
0:0结束。
输出格式
输出两数之和的稀疏编码，按格式以 0:0 结尾。
样例 1
输入
12:6 345:2 0:0
1:7 965:3 49:1 0:0
输出
229:5 999:2 9:1 0:0
解释：两个输入数分别为 $12{,}034{,}500$ 和 $10{,}965{,}490$，和为 $22{,}999{,}990$，对应编码 229:5 999:2 9:1 0:0。
样例 2
输入
123:5 9:2 0:0
878:5 1:2 1:0 0:0
输出
1:8 1:5 1:3 1:0 0:0
解释：两数分别为 $12{,}300{,}900$ 和 $87{,}800{,}101$，和为 $100{,}101{,}001$。结果中非零数字位彼此不连续，所以需要分别编码。
思路分析
第一步：将片段展开为稀疏的数字位映射。
使用字典 digits，以十进制指数为键、该位的数字和为值。对于 abc:e，字符从右向左依次对应指数 $e,e+1,e+2$。解析两行时，相同指数的数字累加。指数可能接近 $2\times10^9$，因此不能创建从 $0$ 到最高指数的数组。
第二步：从低位向高位处理进位。
将出现过的指数放入最小堆，从小到大处理。当前位的值用 divmod(value, 10) 分成余数和进位；余数保留在当前指数，进位加到下一个指数。如果进位目标是原先未出现的新指数，也将它加入堆。这样既能处理连续进位，也不会遍历指数之间可能极大的空白区间。
第三步：按编码规则重新组合。
删除值为 $0$ 的数字位，把剩余数字按指数从高到低排列。只有指数连续递减的位才能拼在同一片段中，每段至多三位；段中的数字天然都非零。若结果没有非零位，输出 0:0，否则在所有片段后追加 0:0。
正确性证明
解码时，每个片段的每个数字都放到其实际对应的十进制指数上；相同指数求和与十进制逐位加法等价，因此字典准确表示两个输入数的位和。
堆按指数从小到大处理。处理某指数前，所有更低指数产生的进位都已加入该位；divmod 恰好留下该位的十进制数字并把剩余部分传给下一位。新产生的指数也进入堆，故进位不会遗漏，所有最终非零数字位均正确。
最后按连续指数分组且每组最多三位，所得片段满足编码规则；每位只出现一次，因而编码表示的数与逐位加法结果相同。若没有非零位，和为零，输出约定的 0:0。
题解代码
import sys
import heapq
input = sys.stdin.readline
def decode(encoded):
digits = {}
for token in encoded.split():
if token == '0:0':
break
coefficient, exponent_text = token.split(':')
exponent = int(exponent_text)
for offset, char in enumerate(reversed(coefficient)):
position = exponent + offset
digits[position] = digits.get(position, 0) + int(char)
return digits
def add_sparse(first, second):
digits = decode(first)
for position, value in decode(second).items():
digits[position] = digits.get(position, 0) + value
pending = list(digits)
heapq.heapify(pending)
queued = set(pending)
while pending:
position = heapq.heappop(pending)
value = digits[position]
carry, digit = divmod(value, 10)
digits[position] = digit
if carry:
next_position = position + 1
digits[next_position] = digits.get(next_position, 0) + carry
if next_position not in queued:
heapq.heappush(pending, next_position)
queued.add(next_position)
nonzero = sorted((position, digit)
for position, digit in digits.items() if digit)
if not nonzero:
return '0:0'
pieces = []
i = len(nonzero) - 1
while i >= 0:
highest = nonzero[i][0]
coefficient = [str(nonzero[i][1])]
j = i - 1
while (j >= 0 and len(coefficient) < 3
and nonzero[j][0] == highest - len(coefficient)):
coefficient.append(str(nonzero[j][1]))
j -= 1
lowest = nonzero[j + 1][0]
pieces.append(''.join(coefficient) + ':' + str(lowest))
i = j
return ' '.join(pieces + ['0:0'])
def solve():
first = input().strip()
second = input().strip()
print(add_sparse(first, second))
if __name__ == '__main__':
solve()
复杂度分析
设 $L$ 为两个编码展开后的数字位总数。
时间复杂度：$O(L\log L)$，主要用于指数排序及堆处理；每个原始或进位产生的指数至多入堆、出堆一次。
空间复杂度：$O(L)$，字典、堆及排序后的非零数字位均与输入数字位数量成正比，不随最高指数大小增长。
第 3 题：黄金投资
题目描述
已知未来若干天的黄金价格。初始资金为 budget，最多进行 max_trades 笔交易，每次买入和卖出固定数量 investment_num 的黄金。必须先买入、再于之后某天卖出；任意时刻至多持有一笔交易。买入时账户资金必须足够支付全部买入成本，卖出时一次性卖出持有的黄金并支付一笔手续费 fee。卖出所得资金可以用于后续交易。
求最终能够获得的最大收益；如果不进行交易更好，收益为 $0$。
输入格式与约束
- 第一行是天数
days，满足 $2\le days\le500$。 - 第二行是
days个价格prices[i]，满足 $1\le prices[i]\le1000$。 - 接下来三行依次是手续费
fee、初始资金budget、最多交易次数max_trades，满足 $0<fee\le1000$、$0<budget\le10000$、$0<max_trades\le100$。 - 最后一行是每笔交易固定买入的数量
investment_num，满足 $1\le investment_num\le30$。
输出格式
输出可获得的最大收益。如果没有可以获利的交易，输出 $0$。
样例 1
输入
4
3 5 2 7
1
10
1
2
输出
9
解释：第 3 天以 $2$ 的价格买入 $2$ 单位，花费 $4$；第 4 天以 $7$ 的价格卖出，收入 $14$，扣除手续费 $1$ 后净收益为 $14-4-1=9$。
样例 2
输入
6
1 3 2 8 4 9
2
10
2
1
输出
8
解释：先以价格 $1$ 买入、以 $8$ 卖出，扣费后的收益为 $5$；再以价格 $4$ 买入、以 $9$ 卖出，扣费后的收益为 $3$，总收益为 $8$。
思路分析
第一步：资金约束决定需要保留账户资金。
只记录累计收益不足以判断后续交易是否合法：即使某笔交易利润很高，买入下一笔时仍必须有足够资金支付固定数量黄金的成本。因此状态直接记录交易后的现金，而不是只记录收益。
第二步：分别维护空仓与持仓状态。
令 cash[j] 表示处理完当前天后，已完成 $j$ 笔交易且没有持仓时的最大现金；hold[j] 表示已经买入第 $j$ 笔、尚未卖出时手头剩余现金的最大值。初始化只有 cash[0] = budget 可达，其余状态均不可达。
若当天价格为 $p$，买入成本是 $p\times investment_num$。从前一天的 cash[j - 1] 买入第 $j$ 笔，前提是现金不少于成本；卖出第 $j$ 笔时，现金增加 $p\times investment_num-fee$。空仓或持仓不动则保留原状态。
第三步：用新数组隔离每天的转移。
每天从上一天的 cash、hold 计算新状态，再整体替换。这样同一天的买入结果不能立刻用于卖出，也不能用同一天卖出的现金再次买入。最终在所有空仓状态中取最大现金，并减去初始资金；不交易的状态也在其中，所以收益不会小于零。
正确性证明
初始时没有完成交易、没有持仓且现金为 budget，只有 cash[0] 可达，状态定义成立。
假设一天开始前的状态正确。结束时处于空仓的方案，要么延续此前空仓，要么卖出此前已经买入的第 $j$ 笔交易；对应转移分别保留 cash[j] 或将 hold[j] 加上卖出收入并扣除手续费。结束时持仓的方案，要么延续此前持仓，要么从已完成 $j-1$ 笔交易的空仓状态买入第 $j$ 笔；买入转移检查现金足够，因而不会产生资金不足的非法方案。逐日新数组保证买入与卖出发生在不同天。
每个状态保留同类方案中的最大现金是安全的：更高的现金不会减少任何未来买入的可行性，且所有后续收支只依赖当前状态与未来价格。归纳可知，处理完所有天后，空仓状态覆盖全部合法的已完成交易方案，并保留每种交易次数下的最大最终资金。取其最大值并与初始资金比较，即得最大非负收益。
题解代码
import sys
input = sys.stdin.readline
def max_profit(prices, fee, budget, max_trades, investment_num):
unreachable = -10**30
cash = [unreachable] * (max_trades + 1)
hold = [unreachable] * (max_trades + 1)
cash[0] = budget
for price in prices:
cost = price * investment_num
next_cash = cash[:]
next_hold = hold[:]
for completed in range(max_trades + 1):
if hold[completed] != unreachable:
sale_cash = hold[completed] + cost - fee
if sale_cash > next_cash[completed]:
next_cash[completed] = sale_cash
if completed < max_trades and cash[completed] >= cost:
remaining_cash = cash[completed] - cost
if remaining_cash > next_hold[completed + 1]:
next_hold[completed + 1] = remaining_cash
cash, hold = next_cash, next_hold
return max(0, max(cash) - budget)
def solve():
days = int(input())
prices = list(map(int, input().split()))[:days]
fee = int(input())
budget = int(input())
max_trades = int(input())
investment_num = int(input())
print(max_profit(prices, fee, budget, max_trades, investment_num))
if __name__ == '__main__':
solve()
复杂度分析
时间复杂度：$O(days\cdot max_trades)$，每天对每个交易次数状态做常数次转移。
空间复杂度：$O(max_trades)$，滚动保存前后两天的空仓与持仓状态。
小结
- 物流中转网络：以步数分层，沿边从旧状态转移到新状态，能够准确统计允许重复经过节点的定长路径。
- 大数加法：只保存非零指数位，再从低位处理进位，空间与编码长度相关而非最高指数相关。
- 黄金投资：资金可行性要纳入状态，空仓和持仓分开转移，逐日更新以保证买入和卖出发生在不同天。