大厂真题 / 蚂蚁

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

本场考试概述

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

考点分析：

第一题：贪心 + 子序列匹配（难度简单）
第二题：多源 BFS（难度简单）
第三题：逐位贪心 + 模约束构造（难度困难）

建议策略：

前两题属于经典模板题，快速拿满分
第三题需要将”最小化 XOR”转化为”逐位贪心匹配 a 的每一位”，并结合模约束判断可行性，思维难度较高

第一题：排列拼接

题目描述

给定两个长度为 n 的排列 a 和 b。将 a 拼接 k 次形成一个新数组，求最小的 k 使得 b 是该数组的子序列。

样例

输入

输出

样例解释：a 拼接 2 次得到 [2,3,1,5,4,2,3,1,5,4]。可以从中选出子序列 [3,5,4,2,1]（取第一份的 3,5,4 再取第二份的 2,1），因此 k=2。

思路分析

由于 a 和 b 都是 1~n 的排列，每个值在 a 中恰好出现一次。记录每个值在 a 中的下标 pos[v]。

贪心地从左到右匹配 b 的每一个元素。在同一份 a 的拷贝中，我们维护一个”当前位置” cur，表示上一个被匹配元素在 a 中的下标。对于 b 的下一个元素 b[i]：

如果 pos[b[i]] > cur，说明在当前这份拷贝中 b[i] 出现在 cur 之后，可以直接匹配，更新 cur = pos[b[i]]
如果 pos[b[i]] <= cur，说明在当前拷贝中已经”路过”了 b[i] 的位置，必须开启新的一份拷贝，copies += 1，并将 cur 重置为 pos[b[i]]

由于 a 是排列，每个值一定能在新拷贝中被匹配到，所以答案一定存在且 k <= n。

时间复杂度：O(n)。

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    pos = [0] * (n + 1)
    for i in range(n):
        pos[a[i]] = i
    copies = 1
    cur = -1
    for i in range(n):
        if pos[b[i]] > cur:
            cur = pos[b[i]]
        else:
            copies += 1
            cur = pos[b[i]]
    print(copies)

T = int(input())
for _ in range(T):
    solve()

第二题：该回家了

题目描述

给定 n x m 的网格，每个格子为 ‘0’ 或 ‘1’。对于每个格子，输出它到最近的 ‘0’ 格子的曼哈顿距离。

样例

输入

输出

1 2 3
0 1 2
1 2 3

思路分析

这是经典的多源 BFS 问题（与 LeetCode 542. 01 Matrix 完全相同）。

核心思路：反转视角。不是从每个 ‘1’ 出发去找最近的 ‘0’，而是把所有 ‘0’ 同时作为起点，向外做一次 BFS。BFS 按层扩展的特性保证了每个格子第一次被访问时得到的就是最短距离。

具体步骤：

初始化距离矩阵 dist，所有 ‘0’ 格子距离为 0 并加入队列，其余为 -1（未访问）
从队列中逐层取出格子，向上下左右四个方向扩展
若相邻格子尚未被访问（dist == -1），则设其距离为当前格子距离 + 1，并入队

时间复杂度：O(n * m)，每个格子入队出队各一次。

import sys
from collections import deque
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    grid = []
    for _ in range(n):
        grid.append(input().strip())
    dist = [[-1]*m for _ in range(n)]
    q = deque()
    for i in range(n):
        for j in range(m):
            if grid[i][j] == '0':
                dist[i][j] = 0
                q.append((i, j))
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
    out = []
    for i in range(n):
        out.append(' '.join(map(str, dist[i])))
    print('\n'.join(out))

solve()

第三题：破译者

题目描述

给定三个非负整数 a, b, c。找到一个非负整数 x，满足 x ≡ b (mod c)（当 c = 0 时，x = b），使得 a XOR x 的值最小。输出最小的 a XOR x。

样例

输入

2
10 10 3
21 13 5

输出

0
2

样例解释：

第一组：x = 10 满足 10 mod 3 = 1 = 10 mod 3，a XOR x = 10 XOR 10 = 0。
第二组：x = 23 满足 23 mod 5 = 3 = 13 mod 5，a XOR x = 21 XOR 23 = 2。

思路分析

这道题的目标是最小化 a XOR x，本质上就是让 x 尽可能”接近” a（在异或度量下），同时满足 x mod c = b mod c 的约束。

核心观察：要最小化 a XOR x，我们希望 x 的每一位都和 a 相同（这样该位异或结果为 0）。高位的权重远大于低位，所以应该从最高位开始贪心。

特殊情况：c = 0

当 c = 0 时，x 被固定为 b，答案直接就是 a XOR b。

一般情况：逐位贪心

从第 59 位（足够覆盖题目数据范围）到第 0 位，逐位确定 x 的每一位：

贪心策略：对于当前的第 bit 位，优先让 x 的这一位等于 a 的这一位（这样异或结果该位为 0）。但我们需要验证这个选择是否可行——即在已经确定了高位的前提下，剩余低位是否还能凑出一个满足模约束的合法 x。

可行性检查：假设已经确定了从高位到第 bit 位的前缀 prefix，那么最终的 x 一定落在区间 [prefix, prefix + mask] 中，其中 mask = (1 « bit) - 1（低位全部自由取值的范围）。

在区间 [lo, hi] 中，是否存在满足 x mod c = r 的整数？只需要检查：

first = lo + ((r - lo % c) % c + c) % c

这个 first 是区间内第一个余数为 r 的整数。如果 first <= hi，则该区间内存在满足条件的 x，选择可行。

为什么这个检查是正确的？

满足 x mod c = r 的整数形成一个等差数列 r, r+c, r+2c, …。在区间 [lo, hi] 中，我们需要找到最小的 x >= lo 且 x mod c = r。计算方法：

lo 除以 c 的余数是 lo % c
需要再往上走 (r - lo % c) % c 步才能对齐到余数 r
如果这个值 first = lo + 调整量 <= hi，则区间内存在合法解

逐位决策的流程：

取 a 在当前位的值 a_bit，令候选前缀 new_prefix = prefix (a_bit « bit)
检查 [new_prefix, new_prefix + mask] 内是否有 x mod c = r 的解
如果有，采纳这个选择（prefix = new_prefix），当前位异或为 0
如果没有，被迫翻转这一位（prefix = prefix ((1 - a_bit) « bit)），当前位异或为 1

由于高位权重大于所有低位之和（2^k > 2^0 + 2^1 + … + 2^(k-1)），每一位的贪心决策都是全局最优的。

时间复杂度：O(B)，其中 B = 60 为位数，每组测试数据常数时间。

import sys
input = sys.stdin.readline

def solve():
    a, b, c = map(int, input().split())
    if c == 0:
        print(a ^ b)
        return
    r = b % c
    prefix = 0
    for bit in range(59, -1, -1):
        mask = (1 << bit) - 1
        a_bit = (a >> bit) & 1
        new_prefix = prefix | (a_bit << bit)
        lo = new_prefix
        hi = new_prefix + mask
        first = lo + ((r - lo % c) % c + c) % c
        if first <= hi:
            prefix = new_prefix
        else:
            prefix = prefix | ((1 - a_bit) << bit)
    print(a ^ prefix)

T = int(input())
for _ in range(T):
    solve()

小结

第一题贪心子序列匹配，利用排列性质记录每个值的位置，顺序扫描判断是否需要新拷贝
第二题多源 BFS 是经典模板，把所有源点同时入队即可一次 BFS 求出所有最短距离
第三题逐位贪心构造是本场难点，关键在于理解”高位优先 + 区间可行性检查”的范式——每一位贪心匹配 a，通过检查剩余范围内是否存在满足模约束的整数来验证可行性

这篇文章有帮助吗？

| GitHub 留言