拼多多笔试思路分享

1.差分2.贪心+二分 最大值最小化/最小值最大化一般都是用二分3.应该是个用前缀和+二分 nlogn，飞船不用返航，卡的时间有点久了4.一眼树形dp但是没思路，时间也不是很够了

1.第一题，赛车，参差板子题记录一个参差数组data,起点0，终点n+1对于每个水泥路段，data[left] += 1,data[right+1] -= 1遍历完后计算一下1-n区间，看看那部分水泥路最长就是对的那条。

2.第二题，赛后想到的思路不一定对。可以二分法插入角色。

3.第三题，我用了前缀和加速。对于每个s，维护一个左边的燃料收集点集合，每个元素形式是[绝对距离差，能量数量]，然后前缀和累加一下加速。每次遍历一下，先往右，可以最远到哪，同时计算一下最远的往左收集的燃料数量。

加一些剪枝就能100%。

4.第四题 染色法+拓扑排序

对每个边，如果u v的freq有差距，就设置一条从freq小到freq大的边，还要维护它的入度和出度。最后用拓扑，遍历入度为0的节点做一个bfs（dfs会卡10%左右，深度太深）。每次入度为0的节点设为能量石1个，然后遍历，链条长1个点就加一个石头，如果加一个还不能多余那个节点当前最低石头数量，就return。

欢迎使用我的内推链接加入拼多多~：https://careers.pddglobalhr.com/campus/intern?t=vSypT8yAuQ 内推码：vSypT8yAuQ