美团众包考试答案（美团众包考试答案5题）

这题打卡题，先扫描一遍原本有n个M和T，然后总数减一下，剩下m个，再看可以添加k个，返回n+min(m,k)

• Python解答

依旧是打卡题，最大最小理所应当的是当未知数分别取l和r时成立。

本题解法为二维前缀和，数据量较小，前缀和+暴力就行了，第一遍扫描的时候统计左上角顶点为(0,0),右下角顶点为(i,j)的矩形中0-1的差值，map[i][j]=map[i-1][j]+map[i][j-1]-map[i-1][j-1]的0和1。第二遍扫描的时候左下角差值和右上角差值进行比较就行了，时间复杂度O(n³)

首先，想要得到末尾是0就必须有一对2和5，简单的数学知识。然后接下来有两种解法，第一是使用线段树，查找每个区域2和5的数量，不过这里不需要，且时间复杂度比第二种高；第二种使用前缀和+双指针，可以优化到O(n)复杂度。
具体看注释

压轴题，帮美团笔试挽尊。但是不要被10⁹的节点数量级骗了，美团众包考试答案注意边最多只有10⁵，也就是存在大量节点是孤立的，筛选后需要考虑的也就10⁵数量级。
很显然，检查两个节点是否连接的话，使用最小连通图的算法时间复杂度必然是不够的，而且我们也不需要知道二者之间有多少跳，只要使用并查集就行了。（不会并查集的可以直接跳了，先去学并查集）
但是并查集存在一个问题，就是当每次删除一条边之后，无法直接判断有没有出现新的集合。而我们也不可能每次删掉边之后重新计算一遍集合，该时间复杂度无法接受O(qm）。
但是，本题不要以流处理的想法来思考，而是应当看清，这题是批处理的题目。换句话说，我们可以把减法变为加法，倒过来计算每一次查询。而对于并查集而言，每次加入一条边，进行合并的复杂度仅为O(1).