09-21 20:54 中国科学技术大学 C++ 发布于浙江
关注
0921电信秋招笔试复盘
#牛客AI配图神器#1.
题目大意：从两组带时间属性的任务中各选一个，自由安排顺序，求完成两个任务的最早结束时间。
思路：暴力枚举O(nm)会超时。对一类课程按开始时间排序并预处理前缀/后缀最优值，然后遍历另一类课程，通过二分查找快速匹配最优的后续课程。双向计算取最终结果。
2.
题目大意：给定一个序列，可选择在某些位置安放标记。未安放标记的位置，若其相邻位置有标记，则该位置的值计入总和。求最大总和。
思路：先将网格按列求和降维成一维序列问题。然后DP
3.
题目大意：在网格中寻找带成本的最短路，其中包含k次特殊的零成本“跳跃”机会，跳跃受限于格子成本。
思路：将状态定义为（坐标，已用跳跃次数），跑一下dijkstra
#发面经攒人品#
题目大意：从两组带时间属性的任务中各选一个，自由安排顺序，求完成两个任务的最早结束时间。
思路：暴力枚举O(nm)会超时。对一类课程按开始时间排序并预处理前缀/后缀最优值，然后遍历另一类课程，通过二分查找快速匹配最优的后续课程。双向计算取最终结果。
2.
题目大意：给定一个序列，可选择在某些位置安放标记。未安放标记的位置，若其相邻位置有标记，则该位置的值计入总和。求最大总和。
思路：先将网格按列求和降维成一维序列问题。然后DP
3.
题目大意：在网格中寻找带成本的最短路，其中包含k次特殊的零成本“跳跃”机会，跳跃受限于格子成本。
思路：将状态定义为（坐标，已用跳跃次数），跑一下dijkstra
#发面经攒人品#
全部评论
相关推荐
投递中国电信等公司10个岗位 09-13 10:20
中国科学技术大学 Java 点赞 评论 收藏
分享