蚂蚁笔试2024.3.30

24届要毕业的我，不小心又做了实习笔试。一直以为是算法的笔试，然后搞了个开发的笔试，算了当回忆了，记录一下。
有一说一，今天的选择题比前几天算法选择题简单很多，基本能对75%以上吧。

第一题题意：对于n个顶点，判断m条边能否构成图切不包含重边自环。
做法：临界n-1，n*(n-1)/2

第二题题意：给定一个长度为n(<1e5)的数组，最多操作m(<1e5)次，每次选连续的k(小于n)个数加1，求操作完之后数组最小值的最大值。
做法：看到最小最大放在一起时，一般就是二分答案。区间加单点查询，搞个八百年没写了的线段树从左到右扫一遍。时间复杂度O(nloglog)。

第三题题意：给定一个长度为n(<1e5)的数组，值为-1或者0或者1，求分别有多少子序列乘积为-1，0，1。
做法：和数组本身没多大关系，记num0表示0的个数，num1表示1的个数，num2表示-1的个数。
乘积为0的公式为(2^num0 - 1) * (2^(num1+num2))
乘积为-1的公式为(\sum_{i为奇数} (C(num2, i)) * (2^(num1))
乘积为1的公式为(\sum_{i为偶数} (C(num2, i)) * (2^(num1)) - 1
逆元前缀乘积 + 快速幂。时间复杂度O(n)