华为 10.28 非 AI 方向机考:路径计数 DP 与稀疏大整数相加
- 轮次
- 笔试
- 时间
- 2026-10
- 来源
- 牛客网
《面试题目》
第 1 题:运输中转站计数(150 分)
一家物流企业共有 N 座中转站,依次标记为 1 至 N。站点间铺了若干只支持指定方向运输的线路。请统计从中转站 S 启程、沿线路移动恰好 L 次后停在中转站 T 的路径总数。同一站点可以在途中反复到访,走过的线路也能再次使用;只要经过的站点序列有一处不同就算两条不同路径。
输入:首行 N、M(站点数与线路数);下一行 S、T、L;随后 M 行每行 u、v,表示一条从 u 驶向 v 的有向线路。
约束:1 ≤ N ≤ 20,1 ≤ M ≤ 200,1 ≤ L ≤ 10,1 ≤ u,v,S,T ≤ N,u ≠ v,任意一对有序站点之间至多一条线路。
输出:一个整数表示路径总数,无可行路径则输出 0,答案无需取模。
样例:5 7 / 2 5 4 / 边为 2→3、3→2、3→4、4→3、3→5、2→5、5→1,输出 2。两条走法分别是 2→3→2→3→5 与 2→3→4→3→5,途中都再次到访了站点 3。
第 2 题:稀疏整数求和(150 分)
给定两个位数可能极多的非负整数,求相加结果。这类整数的十进制表示通常只有少量数位不为 0,因此只记录非零数字片段,每段写作 c:p,表示 c × 10^p,p 是该段系数最右侧数字所在的数位。
编码约定:
- 指数满足 0 ≤ p < 2×10⁹,允许的最大单项是
999:1999999999。 - 按数位从高到低列出片段,任何片段的系数中都不能出现数字 0;遇到零位就断开片段。
- 系数 c 至多 3 位数字;一段连续非零数字若更长,就从左端起每次取尽可能多且不超过 3 位的数字成一组,例如
8765432划为876、543、2。 - 每个整数的编码末尾都附标记
0:0,数值为零时只写这一个标记;相邻项以空格隔开。 - 输入编码均合法,每行字符数连同空格小于 512,且求和结果各片段指数也小于 2×10⁹。
例如 8765004009 编码为 876:7 5:6 4:3 9:0 0:0,8765004000 编码为 876:7 5:6 4:3 0:0。
输入:首行一个非负整数的编码,次行另一个。输出:两数之和,同样按上述约定编码(连续非零数字从高位起每次最多 3 位,末尾附 0:0)。
样例:输入 567:3 89:1 0:0 与 444:3 321:0 0:0(即 567890 + 444321),输出 1:6 122:2 11:0 0:0,对应 1012211——零位把结果分成 1 与 12211 两段,后一段再从左向右划为 122、11。
《参考解析》
路径计数:状态定义一句话,坑在「恰好」两个字。 令 dp[i][v] 表示从 S 出发、恰好走 i 条线路后到达 v 的路径数,dp[0][S] = 1,其余为 0;转移是遍历每条有向边 u→v,把 dp[i][u] 累加到 dp[i+1][v],答案是 dp[L][T]。必须用新数组承接下一层,如果写成 dp[v] += dp[u] 原地累加,那么在同一个 step 里刚被更新的 dp 值会被后续边继续使用,等价于让路径在同一层里多走了一条边,结果偏大——这是本题唯一但致命的坑。约束里 L ≤ 10、N ≤ 20、M ≤ 200,路径总数最多 200¹⁰ 量级,超出 32 位,必须用 64 位整数(题目说答案无需取模,就是让你用 long long)。复杂度 O(L·(N+M)),空间 O(N+M)(只需保存相邻两层)。
还有两个容易答错的变体值得分清:如果问的是「至多 L 步」,答案要把 dp[0..L][T] 全部加起来;如果问的是「可以停在任何站点」,那答案是对 v 求和。题面写「恰好」且指定了终点,两者都不能顺手做。
稀疏大整数:不要真的把十进制串展开。 两个数的位数都可能接近 2×10⁹,任何「转成字符串再做竖式」的思路在内存上就先崩了。正确做法是把编码拆成「指数 → 数字」的映射,只处理实际出现的位:对每一段 c:p,把系数 c 从右往左逐位摊到 p、p+1、p+2 上累加,于是得到一张最多几百个条目的稀疏数位表。
接下来做进位模拟,必须从低位往高位:反复取出当前指数最小的那一项,v = 该位数字和,保留 v mod 10(为 0 就不产出数字,因为它会被零位断开),把 v / 10 加到 p+1 上,直到表里没有剩余项为止。进位遇到空位就自然停止,所以实际处理的位数是 O(D),D 是非零数字总数;用有序映射(C++/Java 的 map、Python 的 heapq 小根堆)都能保证每次取到当前最低位,总体 O(D log D)。Python 的整数本身是任意精度,也可以直接把两行编码展开成两个大整数相加再重新编码——在本题的字符数约束(每行 < 512 字符)下这条路是安全的,但它绕开了题目想考的东西,换成 10¹⁸ 量级的指数就会直接崩。
输出编码是第二个坑,规则要照着字面实现。 拿到完整数字序列后,从高位往低位扫,把连续的非零数字切成每段至多 3 位:段内第一位对应的高位指数要算准——一段 c:p 的 p 是这个系数最右边那位数字的指数,所以若一组数字落在指数 [q..q+k-1] 上,p 就是 q。遇到 0 位必须断开,不能跨越。最后无条件补一个 0:0;如果结果本身是 0,就只输出 0:0 而不能输出空行。
采样例验证一遍:567890 写成 567:3(占指数 5、4、3 上的 5、6、7)+ 89:1(指数 2、1 上的 8、9),444321 写成 444:3 + 321:0;逐位相加得 1、0、1、2、2、1、1,即 1012211。高位段是单独的 1,落在指数 6 上;接着是零位,断开;再往后 12211 按 3 位一组切成 122(指数 4..2)和 11(指数 1..0),拼起来正是 1:6 122:2 11:0 0:0。注意系数里不能出现 0——这就是为什么必须按零位真正断开,而不是把整串数字硬切三段。
两题串起来看,这场机考的取向很清楚:不考花哨算法,考你能不能把一句规则无损翻译成代码,并且把「恰好 vs 至多」「什么时候必须换新数组」「哪一位对应哪个指数」这类细节一次做对。平时刷题时养成写完先自己构造边界样例的习惯(L=1、S=T、只有一位数、结果进位后长度增加、结果为 0),比多刷十道同类题更有效。