3.30 拼多多笔试

第一题线性dp，对每个点，价值的最大值要么是不卖东西，继承上一个点，要么这里是个商人，在上一个获得这个水晶的地方到这个商人都不卖掉，那我们只要记录获取每个宝石最后的位置即可。 dp[i] = max(dp[i-1],dp[mp[k]] + value) 第二题dfs，对每个节点，他的价值是 它的子树的边价值之和 和 他自己到他的上一个节点的边(0或1)的较大值，因为如果你的子树需要走，那你前面的路肯定也走过了 第三题 全为8的情况会爆longlong，8的1e5次方炸到姥姥家去，我是把乘法转为2的幂次的加法然后特殊处理符号和仅有一个负号、一个都不取的情况。 第四题 可以看出最后如果不修改，只能是最后一个元素从右到左递减，还不能和之前的元素重复，先判断一下能不修改的元素的最右端点在哪里，然后判断一下去掉出现过的元素之后能不修改的最右端点在哪里，然后判断最右端点左边这些要修改的元素需要操作多少次。 来，点赞。

跟你一样1.16

我1.12太难了

蹲第一题题解

请问一下第四题是啥思路呀

m

哥们，我也只做出一题，第一志愿已经没了，你呢

拼多多校招在哪投呀