拼多多
Agent 开发工程师笔试记录
完整信息
本篇目录
可能会有记错的，请见谅，但应该没太大问题第一题：机器人初始有 0 把钥匙，传送带上有 n 个箱子排成一列，a[i] 表示打开第 i 个箱子需要的钥匙数。
每打开一个箱子获得 1 把钥匙。
机器人只能取自己面前的 传送带传来的 箱子，但可以随时反转传送带方向。
问：能否打开全部箱子？如果可以，最少反转几次方向？
Tips: 注意到从端到端是最优的，直接暴力一遍遍正反扫就行，n 很小，如果某一轮一个箱子都打不开，就说明不行
第二题：给定数组 a 和整数 k，选两个下标不同的元素，使 a[i] + a[j] 是 k 的倍数，求方案数（无序对）。
Tips: 桶的思想，取余后就简单了，注意一下余数0内部配对，和当k为偶数时，余数为k/2的内部配对
第三题：n 个点，m 条带权普通边（耗时 w），p 条耗时 0 的魔法边。
限制：全程最多用 k 次魔法边，且不能连续走两条魔法边。
允许自环和重边，求起点到终点最短用时。
Tips: 分层图。状态可以设为 {当前点，剩余能用的魔法边数量，上一次是否走了魔法边}，然后分类一下状态转移走普通还是魔法边，跑一个Dijkstra
第四题：左右各 N 匹马，battle[i][j] = 1 表示左 i 胜右 j（配对得 +1 分），-1 则得 -1 分。
每匹马只能出战一次，两两配对后消失，求最大总得分。
Tips: 带权二分图最大权完美匹配，二分图跑KM算法，因为N很小，所以O(N^3)也能接受
本篇目录
- 01
机器人初始有 0 把钥匙，传送带上有 n 个箱子排成一列，a[i] 表示打开第 i 个箱子需要的钥匙数。 > 每打开一个箱子获得 1 把钥匙。 > 机器人只能取自己面前的 传送带传来的 箱子，但可以随时反转传送带方向。 > 问：能否打开全部箱子？如果可以，最少反转几次方向？
- 02
给定数组 a 和整数 k，选两个下标不同的元素，使 a[i] + a[j] 是 k 的倍数，求方案数（无序对）。
- 03
n 个点，m 条带权普通边（耗时 w），p 条耗时 0 的魔法边。 > 限制：全程最多用 k 次魔法边，且不能连续走两条魔法边。 > 允许自环和重边，求起点到终点最短用时。
- 04
左右各 N 匹马，battle[i][j] = 1 表示左 i 胜右 j（配对得 +1 分），-1 则得 -1 分。 > 每匹马只能出战一次，两两配对后消失，求最大总得分。