蚂蚁笔试,难度中等(0326春招实习笔试真题解析)

关注我们，每天更新大厂最新笔试题解析

前言

文末给大家推荐一下我们的活动，针对校招笔面试全覆盖的全程真一对一的提高，参加活动前会给你安排一个全面的摸底，摸底后会针对你的情况进行分析和对于参加活动的介绍，然后你再决定是否参加!

在线做题链接：https://niumacode.com/

• 第一题（排列拼接）：基于贪心策略与相对位置映射，通过预处理排列  的索引数组来顺序匹配 。只需敏锐捕捉相邻元素索引的“倒挂”现象（即下一个元素位置不增），每次倒挂即意味着必须开启新副本，从而以  复杂度轻松锁定最小拼接次数。
• 第二题（该回家了）：打破“从人找房”的常规思维，祭出多源 BFS（广度优先搜索）进行逆向扩散。将所有目标别墅作为初始零点同时推入队列，利用波纹蔓延的特性，将极易超时的暴搜完美降维至 ，一次性求出全图的最短曼哈顿距离。
• 第三题（破译者）：融合了按位贪心与数学同余的高阶位运算题。将异或极值问题转化为“带模数约束的区间存在性判定”，从最高位逐位试探最优 01 选值，并通过  的向下取整公式快速验证候选区间内是否含有  的合法倍数，步步为营锁定全局最优解。

第1题-排列拼接

题目内容

给定两个长度为  的排列  与 。你可以进行如下操作一次： 选择一个正整数  ，构造数组  ，将排列  按原顺序在  的末尾依次复制  份，得到长度为  的数组  ；形式化地，对任意  与  ，都有  。 你希望数组  中存在至少一个子序列，其按顺序拼接后与排列  完全相同。请计算满足该条件的最小  。 排列：长度为  的排列是由  ~  这  个整数按任意顺序组成的数组，其中每个整数恰好出现一次。 子序列：子序列为从原序列中删除任意个(可以为零，也可以为全部)元素后，保持相对顺序得到的新序列。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下： 第一行输入一个整数  表示排列长度； 第二行输入  个整数  表示排列  ； 第二行输入  个整数  表示排列  。 除此之外，保证单个测试文件的  之和不超过  。

输出描述

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

样例1

输入

252 3 1 5 43 5 4 2 141 2 3 44 3 2 1

输出

24

思路与代码

本题的核心目标是让排列** 成为拼接数组的子序列，且要求重复次数最小。因为和都是长度为的排列（元素完全没有重复），我们可以记录下每个元素在排列中的索引位置pos。采取贪心策略遍历排列 **：

1. 我们要在数组** 中按顺序找到 **中的每一个元素。
2. 假设当前我们在排列** 中的第curr_pos 个位置匹配了。接下来要匹配，我们查找在排列中的位置 **next_pos。
3. 如果** next_pos > curr_pos，说明在中出现的位置比靠后，我们可以在同一个副本中顺便把 **也匹配掉。
4. 如果** next_pos <= curr_pos，说明在当前这一个的副本里，找完后，后面已经没有了。我们必须开启一个新的** 的副本，也就是重复次数**  **必须加 1。
5. 遍历完** 数组即可得到最小的 **。

import sysdef solve():# 使用快速输入    input = sys.stdin.readline    T = int(input())    out = []for _ in range(T):        n = int(input())        a = list(map(int, input().split()))        b = list(map(int, input().split()))# 记录 a 中每个元素对应的索引位置# 由于元素是 1 到 n，开一个 n+1 长度的数组即可        pos = [0] * (n + 1)for i in range(n):            pos[a[i]] = i        k = 1        curr_pos = pos[b[0]]for i in range(1, n):            next_pos = pos[b[i]]# 如果要找的下一个元素在 a 中的位置小于等于当前位置，说明必须新开一个 a 的副本if next_pos <= curr_pos:                k += 1            curr_pos = next_pos        out.append(str(k))    sys.stdout.write('\n'.join(out) + '\n')solve()

第2题-该回家了

题目内容

给定一张由  行、  列组成的地图。用字符  表示天才同学的别墅位置，用字符  表示其他位置。对于地图上的每一个位置，定义其到最近别墅的距离为：从该位置出发，每次可以向上、下、左、右四个方向走一步(曼哈顿距离的一步)，到达任意一个  所需要的最少步数。若该位置本身就是  ，则距离为  。

输入描述

在一行上输入两个整数  ，表示地图的行数与列数此后  行，每行输入一个长度为  的字符串  ，仅由字符  和  组成。保证至少存在一个位置为  。

输出描述

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

样例1

输入

3 4011100111111

输出

0 1 2 30 0 1 21 1 2 3

说明

对于样例中第  行第  列位置是  ，因此距离为  ；第  行第  列到最近  的最短路径长度为  (一种方法是向左走三步)。

思路与代码

这道题是一个非常经典的**多源最短路径问题 (Multi-source BFS)**，在无权网格图上求最短曼哈顿距离。

1. 我们不需要对每一个** '1' 都跑一遍搜索，那样会导致 **的复杂度，绝对会超时。
2. 正确的做法是“反向思考”：把所有别墅** '0' 视为起点（Source），将它们的初始距离设为 0，并同时推入队列**。
3. 通过队列进行广度优先搜索 (BFS)，每次弹出一个位置，向上下左右四个方向扩展。只要遇到了还没有被访问过的位置，就将它的距离设为当前节点的距离** **+ 1，并推入队列。
4. 这样就能保证每一个点都是被离它最近的** '0' 给搜索到的，时间复杂度为 **，非常高效。

import sysfrom collections import dequedef solve():    input = sys.stdin.readline    line = input().split()    n, m = int(line[0]), int(line[1])    grid = [input().strip() for _ in range(n)]    dist = [[-1] * m for _ in range(n)]    q = deque()# 找到所有别墅 '0' 的位置，作为多源 BFS 的起点for i in range(n):for j in range(m):if grid[i][j] == '0':                dist[i][j] = 0                q.append((i, j))# 方向数组：上、下、左、右dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]# 开始 BFSwhile q:        r, c = q.popleft()        d = dist[r][c]for dr, dc indirs:            nr, nc = r + dr, c + dc# 如果没有越界且没有被访问过if 0 <= nr < n and 0 <= nc < m and dist[nr][nc] == -1:                dist[nr][nc] = d + 1                q.append((nr, nc))# 集中输出以提升速度    out = []for row in dist:        out.append(" ".join(map(str, row)))    sys.stdout.write('\n'.join(out) + '\n')solve()

第3题-破译者

题目内容

对于给定的三个整数  ，你需要找到一个整数  ，使其在满足  的前提下，能够最小化  的值。 请你输出这个最小的异或结果。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下： 在一行上输入三个整数  。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示最小的异或结果。

样例1

输入

310 10 321 13 55 10 0

输出

0215

思路与代码

题目要求找到整数** ，使得，且 **最小。

1. 首先处理特殊情况：如果** ，那么无论是多少，结果都是固定值，直接输出 **。

2. 当** 时，满足条件的等价于：** 是一个非负整数，且 **。我们将记为 **。

3. 问题转化为：在所有的非负整数** 且中，找出一个使得最小的 **。

4. 按位贪心 (Bit-by-Bit Greedy)：

• 设** ，它们在二进制下都不会超过 61 位（）。我们可以从最高位（第 61 位）到最低位（第 0 位）逐位确定 **的值。
• 为了让异或结果最小，如果在第** 位上，** 的这一位是 0，我们最好也让** 的这一位是 0；如果是 1，最好让 **也是 1。
• 假设我们期望** 的第位是bit_a。我们把这个期望位加上之前确定的前缀，就能得出一个尝试区间 **。
• 接着判断：在这个区间内，是否存在一个且的整数？
• 如果存在，说明我们当前的期望可行，**** 的这一位就固定下来。
• 如果不存在，说明只能被迫取相反的位，必定会产生代价（异或结果的当前位变为了 1）。

5. 判断区间内是否包含合法的倍数： 对于区间** ，合法数字相当于是在判断之间是否包含的倍数，用就能在 **的时间内迅速验证。

import sysdef solve():    input = sys.stdin.readline    T = int(input())    out = []for _ in range(T):        a, b, c = map(int, input().split())# 边界情况：如果 c 为 0，数值不会改变，直接算if c == 0:            out.append(str(a ^ b))continue        b0 = b % c        X = 0# 从最高位开始，贪心地确定 x 的每一位# 2^61 > 2*10^18，足以覆盖题目数据范围for i in range(61, -1, -1):# 获取 a 在第 i 位的值            bit_a = (a >> i) & 1# 假设我们让 x 的第 i 位也等于 bit_a，以达到最优（异或为0）            X_test = X + (bit_a << i)# x_test 确定的前缀对应的数字范围： [L, R]            L = max(X_test, b0)            R = X_test + (1 << i) - 1            valid = Falseif L <= R:                L_sh = L - b0                R_sh = R - b0# 如果区间正好跨过 0 (意味着 b0 在原区间内)，或者包含 c 的倍数if L_sh <= 0 <= R_sh:                    valid = Trueelif R_sh // c > (L_sh - 1) // c:                    valid = True# 如果当前选择可以让区间内存在合法解，则采纳，否则取反if valid:                X = X_testelse:                X = X + ((1 - bit_a) << i)        out.append(str(a ^ X))    sys.stdout.write('\n'.join(out) + '\n')solve()

我们是一个针对技术岗（前后端开发、测试、测开、大数据开发、大模型、ai等相关岗位）校招一对一进阶提高的工作室。我们从2020年2月份开始，迄今整整六年的时间，带领900+学员斩获4000+中大厂offer，参加活动的同学人均5个中大厂offer以上，以下是我们活动内容的介绍！

万诺coding

我们主要是针对有一定基础的同学提供全程一对一笔试、面试辅导，针对每个同学不同的情况定制内容，包括但不限于“笔试及面试算法”/“基础八股/“项目及实习梳理”/“面试技巧”/“面试复盘”等内容。

摸底测试：如果有兴趣深入了解我们的活动，需要先参加我们的“摸底测试”（类似面试），方便我们了解你的具体情况（主要是code能力和计算机素养），定制出相应的辅导计划。摸底测试后，我们会定制化一个针对性的提高计划。然后你再考虑是否参加我们的活动。 

承诺保offer：通过摸底测试后，我们会针对每个同学的情况给定一个“保offer”计划。然后同学可以根据自己的实际情况考虑参不参加我们的活动。

有兴趣的同学可以扫码添加我们的微信（whynotlab）