Zero2Leetcode

大厂真题 / 蚂蚁

蚂蚁 2026 春招笔试真题 - 研发岗（3.29）

本场考试概述

考试时间：2026年3月29日 考试岗位：研发岗 难度评级：中等偏难

考点分析：

  • 第一题：排序 + 贪心（难度中等）
  • 第二题：素数筛 + 计数（难度中等）
  • 第三题：逐位贪心 + 上界约束枚举（难度困难）

建议策略：

  • 前两题是常规算法题，掌握排序贪心和素数筛即可拿满
  • 第三题位运算贪心有一定思维难度，需要熟悉”数位枚举”套路

第一题：巴巴博弈

题目描述

n 份礼物价值为 a[i]。天才同学先拿走 k 份，AK机看到剩余礼物后从中选取不超过 m 份使总价值至少为 y。求最小的 m，使得无论天才怎么拿，AK机都能达标。若不可能输出 -1。

样例

输入

2
5 2 10
1 2 3 4 5
4 1 7
5 2 4 3

输出

-1
2

题解：排序 + 贪心

天才的最优策略：拿走价值最大的 k 个。AK机从剩余中贪心选最大的累加直到 >= y。

时间复杂度：O(n log n)。

import sys
input = sys.stdin.readline

def solve(a, k, y):
    a.sort(reverse=True)
    s = 0
    for i in range(k, len(a)):
        s += a[i]
        if s >= y:
            return i - k + 1
    return -1

t = int(input())
out = []
for _ in range(t):
    n, k, y = map(int, input().split())
    a = list(map(int, input().split()))
    out.append(str(solve(a, k, y)))
print("\n".join(out))

第二题：质数合数

题目描述

给定长度为 n 的全素数数组，计算满足 a[i]+a[j] 为合数的有序二元组 (i,j) 的数量（i != j）。

样例

输入

5
2 2 3 3 2

输出

8

题解：正难则反 + 素数奇偶性分析

合数对数 = 总对数 n*(n-1) - 和为素数的对数。

两个质数之和：奇+奇 >= 6 一定是合数；偶+偶 = 4 是合数；只有 2+p 且 p+2 也是素数时和才是素数。

设 cnt2 为 2 的个数，cntTwin 为满足 p+2 是素数的奇素数个数。答案 = n(n-1) - 2cnt2*cntTwin。

时间复杂度：O(n + V)。

import sys
input = sys.stdin.readline

def sieve(max_v):
    is_prime = [True] * max_v
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(max_v**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, max_v, i):
                is_prime[j] = False
    return is_prime

is_prime = sieve(200003)
n = int(input())
a = list(map(int, input().split()))
cnt2 = cnt_twin = 0
for x in a:
    if x == 2:
        cnt2 += 1
    elif is_prime[x + 2]:
        cnt_twin += 1
print(n * (n - 1) - 2 * cnt2 * cnt_twin)

第三题：位运算权值

题目描述

给定长度为 n 的整数序列 a 和操作字符串 s（每个字符为 1/2/3，分别对应 AND/XOR/OR）。在 [1, r] 中选一个整数 x，最大化所有位运算结果之和。

样例

输入

3
3 7
1 2 3
123
4 3
1 1 1 1
1111
5 10
5 6 7 8 9
23231

输出

15
4
60

题解：逐位贪心 + 上界约束枚举

位运算的第 b 位只影响所有 a[i] 第 b 位的结果，因此可以对每一位独立计算贡献 g1[b]（x 该位为 1）和 g0[b]（x 该位为 0）。

处理 x <= r 的约束：枚举 r 二进制中哪一位”脱离”（将 1 改为 0 使 x < r），高位保持与 r 一致，低位自由选最优。

时间复杂度：O(n * B + B^2)，B = 30。

import sys
input = sys.stdin.readline

BITS = 30

def solve(a, s, r):
    n = len(a)
    g1 = [0] * BITS
    g0 = [0] * BITS
    for i in range(n):
        for b in range(BITS):
            bit_a = (a[i] >> b) & 1
            pw = 1 << b
            if s[i] == '1':
                g1[b] += bit_a * pw
            elif s[i] == '2':
                g1[b] += (1 - bit_a) * pw
                g0[b] += bit_a * pw
            else:
                g1[b] += pw
                g0[b] += bit_a * pw

    best = sum(g1[b] if (r >> b) & 1 else g0[b] for b in range(BITS))

    for split in range(BITS):
        if not ((r >> split) & 1):
            continue
        val = 0
        x_val = 0
        for b in range(BITS - 1, split, -1):
            if (r >> b) & 1:
                val += g1[b]
                x_val |= 1 << b
            else:
                val += g0[b]
        val += g0[split]
        for b in range(split - 1, -1, -1):
            if g1[b] >= g0[b]:
                val += g1[b]
                x_val |= 1 << b
            else:
                val += g0[b]
        if x_val == 0:
            val = val - g0[0] + g1[0]
        best = max(best, val)
    return best

t = int(input())
out = []
for _ in range(t):
    n, r = map(int, input().split())
    a = list(map(int, input().split()))
    s = input().strip()
    out.append(str(solve(a, s, r)))
print("\n".join(out))

小结

  • 第一题排序 + 贪心，关键是想清楚天才的最优策略：拿走最大的 k 个
  • 第二题正难则反 + 素数奇偶性分析，只有 2+p 且 p+2 是素数的对才不是合数
  • 第三题逐位贪心 + 上界约束枚举是位运算题的经典套路，需要熟悉”数位 DP”思想