✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

蚂蚁-2026.03.26-研发岗

这套题的梯度比较清楚。

第一题是顺序映射后的贪心统计，核心在于看清“什么时候必须开新的一份排列”。第二题是标准多源 BFS，属于比较直接的网格最短路。第三题是整套题的分水岭，要先把可选值化成固定同余类，再在二进制区间上做按位贪心。

题目一：小兰的轮班名单拼接

这题先把 中每个值映射到它在 中的位置，再去看这个位置序列会被切成多少段严格递增块。每次位置不再上升，就说明当前副本已经接不下了，答案自然加一。

题目二：小基 的归家导航图

表面上是对每个位置分别求最近的 0，但那样会把 BFS 重复很多遍。更直接的做法是把所有 0 一次性入队，从所有起点同时扩展，第一次到达某个格子时的距离就是答案。

题目三：小柯的偏移破译器

难点在于先把所有合法的 看成一个固定同余类里的非负整数集合。之后就可以从高位到低位贪心，每次判断“当前这个二进制前缀对应的区间里，是否还存在合法值”，从而得到最小异或值。

1. 小兰的轮班名单拼接

问题描述

小兰在整理一份轮班名单。

现在有两份长度都为 的排列 与 。她准备把名单 按原顺序重复贴到一张长表上：

• 先选择一个正整数 ；
• 再把排列 连续复制 份，得到长度为 的数组 。

形式化地说，对任意 与 ，都有：

她希望长表 中至少存在一个子序列，按顺序恰好等于排列 。

请你计算，满足条件的最小 是多少。

这里：

• 排列指由 这 个整数恰好各出现一次组成的数组；
• 子序列指从原序列中删除若干元素后，保持剩余元素相对顺序得到的新序列。

输入格式

每个测试文件均包含多组测试数据。

• 第一行输入一个整数 ，表示数据组数。
• 对于每组数据：
  • 第一行输入一个整数 ，表示排列长度。
  • 第二行输入 个整数 ，表示排列 。
  • 第三行输入 个整数 ，表示排列 。

保证单个测试文件内所有数据组的 之和不超过 。

输出格式

对于每组数据输出一行一个整数，表示使得 能作为 的一个子序列出现所需的最小 。

样例输入

2
5
2 3 1 5 4
3 5 4 2 1
4
1 2 3 4
4 3 2 1

样例输出

2
4

数据范围

• 
• 
• 
• 与 都是长度为 的排列
• 单个测试文件内所有数据组的 之和不超过

样例	解释说明
样例 1	第 1 组中，把 中每个值映射到它在 中的位置后得到序列 。只有从 跳到 时顺序被打断，所以需要两份 。第 2 组映射后是 ，每一步都会重新开一份，因此答案是 。

题解

这题表面上是在问“最少复制几份排列 ”，本质上是在问：

把 里的元素按顺序取出来时，它们在排列 中的位置序列会被切成多少段严格递增的连续块。

第一步：把值映射成位置

因为 是一个排列，每个值只会出现一次。

设 pos[x] 表示值 在排列 中的位置。

那么按 的顺序把这些位置写出来，就得到一个长度为 的新序列：

问题就变成了：

• 在一份 里，我们只能按下标从左到右地选元素；
• 所以同一份副本里，能取出的下标序列必须严格递增；
• 一旦下一个位置不比前一个大，就只能去下一份副本里重新开始。

第二步：最少份数怎么数

设当前已经取到的位置是 last。

扫描位置序列 ：

• 如果当前 ，说明它还能接在当前这份副本后面；
• 如果当前 ，说明这一份已经放不下它了，必须新开一份副本。

因此答案就是：

• 初始先开一份；
• 每遇到一次 ，答案加一。

也就是：

答案 = 1 + 位置序列中的“非递增断点”个数

为什么这样一定最优

同一份排列 的相对顺序是固定的。

如果两个相邻需要匹配的元素在 中的位置满足：

那么无论你怎么删中间元素，都不可能在同一份副本里先选到位置 ，再往后选到位置 。
所以这里一定要切开，至少多用一份。

反过来，只要当前位置比前一个大，就一定可以继续放在同一份副本里。

于是这个贪心没有任何浪费：

• 能不换副本时就继续放；
• 只有不得不换时才新开一份。

所以得到的份数就是最小值。

复杂度分析

每组数据只需要：

• 扫一遍 建位置表；
• 再扫一遍 统计断点。

时间复杂度是 ，空间复杂度是 。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()


def solve():
    t = int(input())
    out = []

    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))

        # pos[x] 记录值 x 在排列 a 中出现的位置。
        pos = [0] * (n + 1)
        for i, x in enumerate(a, 1):
            pos[x] = i

        # 至少要用一份 a。
        ans = 1
        last = 0
        for x in b:
            cur = pos[x]
            # 当前位置不能接在上一位置后面时，只能换到下一份副本。
            if cur <= last:
                ans += 1
            last = cur

        out.append(str(ans))

    # 按组输出答案。
    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n + 1), b(n + 1), pos(n + 1);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            // 记录每个值在 a 中的位置。
            pos[a[i]] = i;
        }
        for (int i = 1; i <= n; ++i) {
            cin >> b[i];
        }

        // 至少需要一份副本。
        int ans = 1;
        int last = 0;
        for (int i = 1; i <= n; ++i) {
            int cur = pos[b[i]];
            // 如果当前位置不在上一位置右边，就必须重新开一份。
            if (cur <= last) {
                ++ans;
            }
            last = cur;
        }

        cout << ans << '\n';
    }
    return 0;
}

• Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int t = fs.nextInt();
        StringBuilder sb = new StringBuilder();

        while (t-- > 0) {
            int n = fs.nextInt();
            int[] pos = new int[n + 1];
            int[] b = new int[n + 1];

            for (int i = 1; i <= n; i++) {
                int x = fs.nextInt();
                // pos[x] 记录值 x 在 a 中的位置。
                pos[x] = i;
            }
            for (int i = 1; i <= n; i++) {
                b[i] = fs.nextInt();
            }

            // 至少要准备一份排列副本。
            int ans = 1;
            int last = 0;
            for (int i = 1; i <= n; i++) {
                int cur = pos[b[i]];
                // 无法继续接在当前副本后面时，就要切到下一份。
                if (cur <= last) {
                    ans++;
                }
                last = cur;
            }

            sb.append(ans).append('\n');
        }

        // 统一输出所有测试数据的答案。
        System.out.print(sb);
    }

    static class FastScanner {
        private final InputStream in;
        private final byte[] buf = new byte[1 << 16];
        private int len = 0;
        private int ptr = 0;

        FastScanner(InputStream is) {
            in = is;
        }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            while ((c = read()) <= ' ') {
                if (c == -1) {
                    return -1;
                }
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
            return val * sgn;
        }
    }
}

2. 小基 的归家导航图

问题描述

小基 手里拿到一张回家导航图。

这张地图由 行、 列组成，每个位置要么是：

• 字符 0，表示一处可直接回家的落点；
• 字符 1，表示普通位置。

对于地图上的每一个位置，定义它到最近落点 0 的距离为：

• 从该位置出发；
• 每次只能向上、下、左、右四个方向走一步；
• 走到任意一个字符 0 的最少步数。

如果某个位置本身就是 0，那么它的距离就是 。

请你输出整张地图上每个位置到最近 0 的最短距离。

输入格式

第一行输入两个整数 ，表示地图的行数与列数。

接下来输入 行，每行一个长度为 的字符串 ，只由字符 0 和 1 组成。

保证至少存在一个位置为 0。

输出格式

输出 行。

第 行输出 个整数，分别表示第 行每个位置到最近 0 的最短步数，相邻整数之间使用一个空格分隔。

样例输入

3 4
0111
0011
1111

样例输出

0 1 2 3
0 0 1 2
1 1 2 3

数据范围

• 
• 地图只包含字符 0 和 1
• 保证至少存在一个位置为 0

样例	解释说明
样例 1	第二行前两列本身就是 0，距离为 。第一行第二列离最近的 0 只要走一步，因此输出 ；右下角位置离第二行第二列最近，共需要走 步。

题解

这题是一个很标准的“多源最短路”模型。

如果只从某一个 1 出发去找最近的 0，那就得对每个格子单独做一次 BFS，复杂度显然不划算。

真正应该反过来想：

把所有 0 一起当成起点，同时向外扩展。

这样谁先被扩展到，谁离最近的 0 就更近。

为什么可以把所有 0 一起入队

在普通 BFS 里：

• 起点先入队，距离记为 ；
• 之后每次从队头取点，把相邻格子的距离更新成当前距离加一。

如果我们把所有 0 都视作起点，那么它们的距离本来就都是 ，同时入队完全合法。
后面 BFS 一层一层往外扩展时，某个格子第一次被访问到的那一刻，就是它到最近 0 的最短距离。

这和“从多个起点同时出发跑最短路”是同一件事。

具体做法

1. 建一个同样大小的数组 dis，初始全设成 -1。
2. 扫描整张图：
   • 如果当前位置是 0，就把它加入队列；
   • 同时把它的距离设为 。
3. 开始 BFS。
4. 每次从队头取出一个格子，尝试往四个方向扩展：
   • 如果新格子还没被访问过，就把它的距离设为当前距离加一；
   • 再把它加入队列。

最终 dis 数组就是答案。

为什么第一次到达就是最短距离

BFS 的队列顺序保证了：

• 先处理距离为 的所有点；
• 再处理距离为 的所有点；
• 再处理距离为 的所有点……

所以某个格子第一次出现在队列里时，已经是从所有 0 中能走到它的最短步数了。
后面再从更远的位置绕回来，只会更长，不可能更优。

复杂度分析

每个格子最多入队一次，四个方向也只会检查常数次。

• 时间复杂度：
• 空间复杂度：

在 的范围内完全可以通过。

参考代码

• Python

import sys
from collections import deque
input = lambda:sys.stdin.readline().strip()


def solve():
    n, m = map(int, input().split())
    g = [input() for _ in range(n)]

    # dis[i][j] 记录当前位置到最近 0 的最短距离。
    dis = [[-1] * m for _ in range(n)]
    dq = deque()

    for i in range(n):
        for j in range(m):
            # 所有 0 都作为 BFS 的起点同时入队。
            if g[i][j] == '0':
                dis[i][j] = 0
                dq.append((i, j))

    dx = (-1, 1, 0, 0)
    dy = (0, 0, -1, 1)
    while dq:
        x, y = dq.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            # 越界位置直接跳过。
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 已经求出最短距离的格子不必重复入队。
            if dis[nx][ny] != -1:
                continue
            dis[nx][ny] = dis[x][y] + 1
            dq.append((nx, ny))

    out = []
    for row in dis:
        out.append(" ".join(