大厂真题 / 蚂蚁
蚂蚁 4.19 笔试真题 - 研发岗
本场考试概述
考试时间：2026年4月19日 考试岗位：研发岗 难度评级：中等
考点分析：
- 第一题：贪心 + 计数（难度简单）
- 第二题：排序 + 二分查找（难度中等）
- 第三题：位运算（连续1合并）（难度中等）
建议策略：
- 第一题送分，找到”3 对等长木棍即可”的规律直接过
- 第二题核心是把问题拆解成筛选 + 二分，想清楚三个条件后代码不难写
- 第三题位运算技巧题，二进制连续 1 合并的 trick 值得记住
第一题：拼好房
题目描述
用木棍拼一个”房子”形状：下部是一个长方形，上部是一个等腰三角形，且两者共用一条边（即长方形的上边同时作为三角形的底边，三角形除底边的两条边要相等）。给定一堆正整数长度的木棍，每根最多使用一次，判断是否能从中挑出若干根恰好拼成这样的”房子”。
输入第一行为木棍数量 $n$，第二行为 $n$ 个正整数表示每根木棍的长度。输出 YES 或 NO。
样例
输入
6
4 4 3 3 5 5
输出
YES
思路分析
第一步：分析房子结构
房子由 6 根木棍构成：长方形的左右两边是一对等长木棍，上下两边是一对等长木棍，三角形的两条腰是一对等长木棍。总共需要 3 对等长木棍。
第二步：验证三角形不等式是否需要额外检查
任意取 3 对正整数长度的木棍，设三对长度为 $a \leq b \leq c$。三角形底边为 $a$（长方形上边），两腰为 $b$，长方形左右为 $c$。三角形需满足 $2b > a$，由于 $b \geq a$ 且都是正整数，所以 $2b \geq 2a > a$ 恒成立。实际上无论怎么分配角色，正整数条件都保证三角形不等式恒成立。
第三步：结论
只需要统计所有长度的配对数，总配对数 $\geq 3$ 就输出 YES。
题解代码
import sys
input = sys.stdin.readline
def solve():
n = int(input())
a = list(map(int, input().split()))
cnt = {}
for x in a:
cnt[x] = cnt.get(x, 0) + 1
pairs = sum(freq // 2 for freq in cnt.values())
print("YES" if pairs >= 3 else "NO")
solve()
复杂度分析
时间复杂度：$O(n)$ 空间复杂度：$O(n)$
第二题：不降序序列
题目描述
给定 $n$ 个整数序列（长度可能不同），定义序列拼接 $A+B$ 为先写出 $A$ 再紧接写出 $B$ 所得到的序列。称一个序列是”不降序”的，当且仅当对所有相邻元素都满足前一个 $\leq$ 后一个。
计算所有有序序列对 $(i, j)$（允许 $i = j$）中，使得拼接序列 $S_i + S_j$ 为不降序的序列对数量。
多组测试数据，每组第一行为序列个数 $n$，之后每个序列先给长度再给元素。
样例
输入
2
3
2 1 3
3 2 4 6
2 5 7
2
1 5
1 3
输出
1
3
思路分析
第一步：分析拼接后不降序的条件
拼接 $S_i + S_j$ 不降序等价于同时满足三个条件：
- $S_i$ 本身是不降序的
- $S_j$ 本身是不降序的
- $S_i$ 的末尾元素 $\leq$ $S_j$ 的首元素
如果 $S_i$ 或 $S_j$ 自身不是不降序的，无论怎么拼接都不可能让整体不降序。
第二步：问题转化
先筛选出所有自身不降序的序列，对每个合法序列只需记录其首元素和末尾元素。问题转化为：在这些合法序列中，有多少有序对 $(i, j)$ 满足 $\text{last}_i \leq \text{first}_j$？
第三步：排序 + 二分查找
把所有合法序列的首元素收集起来并排序。对于每个合法序列的末尾元素 $\text{last}$，用二分查找找到排序后首元素数组中第一个 $\geq \text{last}$ 的位置 $pos$，则从 $pos$ 到末尾共有 $len - pos$ 个序列可以作为 $S_j$ 与之配对。
暴力枚举所有对是 $O(n^2)$，排序+二分将其优化到 $O(n \log n)$。
题解代码
import sys
from bisect import bisect_left
input = sys.stdin.readline
def solve():
T = int(input())
for _ in range(T):
n = int(input())
firsts = []
lasts = []
for _ in range(n):
seq = list(map(int, input().split()))
length = seq[0]
elements = seq[1:]
# 检查序列自身是否不降序
is_sorted = True
for j in range(1, length):
if elements[j] < elements[j - 1]:
is_sorted = False
break
if is_sorted:
firsts.append(elements[0])
lasts.append(elements[length - 1])
# 排序首元素数组，用二分查找配对
sorted_firsts = sorted(firsts)
ans = 0
for last in lasts:
pos = bisect_left(sorted_firsts, last)
ans += len(sorted_firsts) - pos
print(ans)
solve()
复杂度分析
时间复杂度：$O(n \log n + L)$，其中 $L$ 是所有序列长度之和 空间复杂度：$O(n)$
第三题：二次幂变换2
题目描述
给定两个整数 $x$ 与 $y$，每次操作可以选择任意非负整数 $k$，选择 $x$ 或 $y$ 中的一个数，将其值加上 $2^k$。求使 $x$ 与 $y$ 相等所需的最少操作次数。
多组测试数据，每组输入两个整数 $x, y$。
样例
输入
5
0 0
7 0
5 14
-3 5
3 10
输出
0
2
2
1
2
思路分析
第一步：将问题转化为差值分析
要使 $x$ 和 $y$ 相等，设差值 $d = \lvert y - x \rvert$。如果 $d = 0$ 直接返回 0。每次操作给较小的一方加上某个 $2^k$，等价于从差值中”凑出” $d$。
如果只往一边加，问题就是用最少个 2 的幂凑出 $d$，答案就是 $d$ 的二进制表示中 1 的个数（popcount）。
第二步：发现两边同时加可以做得更好
但题目允许两边都加。考虑 $d = 7 = 0b111$（三个 1），如果只往一边加需要 3 次。但可以这样做：给 $x$ 加 $2^0 = 1$ 使差变成 $8 = 2^3$，然后给 $y$ 加 $2^3$ 抹平差值。这利用了 0111 + 0001 = 1000 的进位效果，将连续的 1 串合并为一次进位操作。
第三步：连续 1 合并的贪心策略
从最低位扫描 $d$ 的二进制：
- 遇到一个孤立的 1（下一位是 0），操作次数 +1，正常右移
- 遇到连续的 1（当前位是 1 且下一位也是 1），说明有一串连续 1。此时操作次数 +1（代表在低位加一个 $2^k$ 触发进位），同时执行
d += 1模拟进位。进位会把连续的 1 串变成一个更高位的 1，后续只需再一次操作来抹平
以 $d = 7 = 0b111$ 为例：
- 位 0：是 1，看下一位也是 1 → count=1，$d += 1$ → $d=8=0b1000$
- 右移 → $d=4=0b100$
- 位 1：是 0，跳过。右移 → $d=2=0b10$
- 位 2：是 0，跳过。右移 → $d=1=0b1$
- 位 3：是 1，下一位是 0 → count=2
- 最终答案 2，和前面分析一致
题解代码
import sys
input = sys.stdin.readline
def min_ops(d):
if d < 0:
d = -d
count = 0
while d > 0:
if d & 1:
count += 1
# 连续1串：加1触发进位合并
if (d >> 1) & 1:
d += 1
d >>= 1
return count
def solve():
T = int(input())
for _ in range(T):
x, y = map(int, input().split())
print(min_ops(y - x))
solve()
复杂度分析
时间复杂度：$O(\log d)$，$d$ 为两数差值的绝对值 空间复杂度：$O(1)$
小结
- 第一题是经典的计数签到题，关键观察是正整数条件保证三角形不等式恒成立，只需配对数 $\geq 3$
- 第二题的核心转化是将拼接不降序拆解为三个独立条件，然后通过排序 + 二分将 $O(n^2)$ 配对优化到 $O(n \log n)$
- 第三题是位运算技巧题，核心 trick 是二进制中连续 1 串可以通过”低位加 1 进位”合并为高位单个 1，从而减少操作次数。这个技巧在竞赛中出现频率较高，值得牢记