03-30 11:45 已编辑 复旦大学 计算机类
关注
蚂蚁笔试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)
有一说一，今天的选择题比前几天算法选择题简单很多，基本能对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)
全部评论
shadox
浙江大学 计算机类
第二题没必要上线段树，二分加差分就行
送花
回复
分享
huhuhu3
门头沟学院 计算机类
ww问问这套题在大厂笔试里算难吗
送花
回复
分享
滴滴
校招火热招聘中
官网直投
喜欢唱跳rap牛油果在看机会
蚌埠坦克学院 计算机类
啊，我第三题用的动态规划，不知道咋初始化哎,...
送花
回复
分享
寻冠的小虎牙
东南大学 仪器类
太牛啦
送花
回复
分享
相关推荐
投递蚂蚁集团等公司10个岗位 > 点赞 评论 收藏
转发
蚂蚁集团一面112人在聊 点赞 评论 收藏
转发