4.12饿了么笔经
本次笔试难度中等偏上，最后一题不好做。
第一题基础的思维题，难度不大，关键是分析到 通过异或构造结果为1的y，利用1的普遍因子特性简化问题。
第二题贪心题，要分析好题目要求，将问题转化为最大化移除收益，通过计算单首歌曲的独立贡献（减少的等待时间）并贪心选择最优k个。
第三题 换根 dp，难度较大，两遍DFS实现换根DP，第一遍计算子树信息，第二遍换根更新全局状态，最小化整树染色代价。
1.小红的小苯
第一题基础的思维题，难度不大，关键是分析到 通过异或构造结果为1的y，利用1的普遍因子特性简化问题。
第二题贪心题，要分析好题目要求，将问题转化为最大化移除收益，通过计算单首歌曲的独立贡献（减少的等待时间）并贪心选择最优k个。
第三题 换根 dp，难度较大，两遍DFS实现换根DP，第一遍计算子树信息，第二遍换根更新全局状态，最小化整树染色代价。
1.小红的小苯
小红拿到了一个正轮数x，小苯希望小红找到一个正整数y，满足x⊕y既是x的因子，也是y的因子，你能帮帮小红吗?在这里，⊕表示位运算中的按位异或操作。
2.音乐队列
小红的播放器里一共有n首歌待放，歌单里第i首歌的长度为ai秒。小红会按顺序播放歌单里的歌，如果当前歌放完了，会自动插放下一首，两首歌曲之间没有缓冲的时间。第i首歌曲的等待时长为a1+…+ai-1秒，第一首歌曲等待时间为0秒。小红想知道，如果她选择k首歌移除播放队列，那么播放队列中剩下的歌曲的等待时长之和最小能达到多少?
3.小红的加权三色数
小红得到一棵树，该树有n个节点。每个节点具有三种颜色之一，分别为R、G与B。每个节点还拥有一个正整数权值，用wi表示第i个节点的权值。小红需要选择一个节点作为根节点。选定后，该根节点的颜色保持不变，不能被修改。对于其他非根节点，小红可以进行修改操作。每次修改操作的规则为：
选择一个非根节点，将以该节点为根的子树内所有节点的颜色统一修改为目标颜色，目标颜色为根节点的初始颜色。在一次修改中，该操作的代价为被修改子树内所有节点权值之和。小红希望通过合理选择根节点并规划修改方案，使得最终全树所有节点均为根节点的颜色，同时使总代价最小。
详细真题及答案
在第三sheet
#笔试##饿了么笔试##暑期实习#
米哈游公司福利 3760人发布
TCL一面46人在聊