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