9.16 美团笔试

拖了很久的美团笔试 最后还是决定做一下吧(当你面前有一件十分痛苦的事,那么之前觉得痛苦的事情突然不那么痛苦,甚至开始变的有意思起来了

(题外话 感觉美团笔试难度差距很大,今天这场应该是比较简单的,之前看别的场次的题感觉肯定做不了这么快

第一题

题意 有n道题,做对得一分,如果上一题也对会额外得一分,问总分

题解 。。。

第二题

题意 打靶子,给坐标,求靶数

题解 。。。

第三题

题意

小红有血量H和攻击力A,有n个怪物,第i个怪物有血量hi和攻击力ai,小红可以干掉血量和攻击力都严格小于她的怪物,同时血量和攻击力都变成怪物的数值。求小红最多干掉多少怪物。

题解

如果可以作为怪物i干掉怪物j,则将i和j之间建有向边。由于严格小于,因此建立的图是有向无环图。小红作为第0个怪物,则可以变成从0为起点开始的最长路,dp[i]表示第i个节点为起点的最长路长度。通过反向拓扑排序的顺序,可以保证维护第i个节点的时候,其每一个下一跳可选的节点j都已经维护完dp[j]了。dp[i] = max(dp[j]) + 1。最后要注意答案是dp[0]-1,因为小红其实不是怪物hhh

第四题

题意

有若干个数,可以选其中的一或若干个,然后将这些数&运算,运算结果可以被2^m整除。求m最大。

题解

&运算结果能被2^m整除,则说明其最低m个二进制位都是0。根据位运算性质,只需要从小到大每一个二进制位都找到一个是0的数。维护一下每一个二进制位上为0的数是否存在,找到从小到大第一个不存在的为0的二进制位即可。

第五题

题意

图有若干个节点和若干条边,边有花费,有些边是可选边,有些边是必选边。必选边必须选,可选边可以选一部分或者不选,使得选后的图需要让所有点都互相可达,求最小花费。

题解

回忆克鲁斯卡尔最小生成树的构造方法。用并查集维护可达关系。首先把所有必选边选入,必选边的两个端点合并并查集。然后贪心的按花费从小往大找边,首先看边的两端是否已经可达,如果不可达则选择这条边,更新可达关系。注意最后要check一下整个图是否联通(

---------------------------------------------------------------------------------------------------------------------

更新一下,第三题好像写丑了,排序做最长下降子序列的话复杂度是nlogn。感谢美团数据范围只有1e3

#美团笔试#
全部评论
做完才发现漏了第四道
2 回复 分享
发布于 2023-09-16 21:19 山东
大佬nb
1 回复 分享
发布于 2023-09-16 21:06 广东
第三题用dp数组怎么做能再详细说说吗,用递归做的没全通过
1 回复 分享
发布于 2023-09-16 21:46 河北
捞 第三题可以给我看看源码吗 lc上哪道题比较类似哇😭
1 回复 分享
发布于 2023-09-17 08:04 上海
这一场确实算是比较简单了,其他场没见过第二题这么简单的...
1 回复 分享
发布于 2023-09-18 20:43 上海
举报了哥
点赞 回复 分享
发布于 2023-09-16 21:08 北京
第四题为什么输出最大的二进制低位0个数结果只能过50%呢
点赞 回复 分享
发布于 2023-09-16 21:12 法国
牛逼,大佬
点赞 回复 分享
发布于 2023-09-16 21:12 黑龙江
怎么这么强啊
点赞 回复 分享
发布于 2023-09-16 21:13 湖南
第五题思路一样,但是超时了。大佬能教教python并查集怎么操作快吗?更新可达关系时我是用一个列表储存各个连通图的端点的集合。对于新来的两个端点,如果两个端点都不在已建立的联通图中,则在列表中append这两个端点的集合;如果两个端点都在一个连通图中跳过;如果两个端点在两个不同的连通图中,合并并pop掉一个另一个连通图。
点赞 回复 分享
发布于 2023-09-16 21:17 北京
大概做对多少能过啊
点赞 回复 分享
发布于 2023-09-16 21:57 重庆
大佬太强了
点赞 回复 分享
发布于 2023-09-16 23:28 云南
同一场,第二第三第四题都没全过,这样的算分吗
点赞 回复 分享
发布于 2023-09-17 13:18 新加坡
a了3.8道,今天一看终止了,难受
点赞 回复 分享
发布于 2023-09-21 17:46 山东

相关推荐

17 23 评论
分享
牛客网
牛客企业服务