大厂真题 / 蚂蚁
蚂蚁 5.7 笔试真题 - 开发岗
本场考试概述
考试时间：2026年5月7日 考试岗位：开发岗（暑期实习/春招） 难度评级：中等偏难
考点分析：
- 第一题：前缀和（难度中等）
- 第二题：多源BFS（难度中等）
- 第三题：动态规划（难度困难）
建议策略：
- 第一题枚举分界点 + 前缀和，合法串只有两种形态，想清楚就能直接写
- 第二题是经典多源 BFS 模板题，所有源点同时入队即可
- 第三题 DP 状态只需记录”是否被禁赛”，转移公式不复杂，关键是理解禁赛机制
第 1 题：好看的二进制字符串
题目描述
给定一个只包含 0 和 1 的字符串。”好看”的字符串要求：所有 0 字符形成一个连续的块，所有 1 字符也形成一个连续的块。
每次操作可以把字符串中任意一个位置的字符改成 0 或 1。求把给定字符串变为”好看”所需的最少操作次数。
多组测试数据，所有 $n$ 的总和不超过 $2 \times 10^5$。
样例
输入
3
5
01010
4
1111
7
1011000
输出
2
0
1
思路分析
第一步：观察合法串的形态
“好看”要求所有相同字符连成一块，因此整个串中 0/1 的切换至多发生一次。合法串只有两种形态：000...111...（前缀全 0 后缀全 1）或 111...000...（前缀全 1 后缀全 0），全 0 和全 1 是其特殊情况。
第二步：枚举分界点
枚举分界位置 $k$（$0 \leq k \leq n$），将字符串分为前缀 $[0, k)$ 和后缀 $[k, n)$ 两段。对两种形态分别计算代价：
- 形态
0...01...1：前缀中的1需要改为0，后缀中的0需要改为1 - 形态
1...10...0：前缀中的0需要改为1，后缀中的1需要改为0
第三步：前缀和加速
预处理 pre0[i] 和 pre1[i] 分别表示前 $i$ 个字符中 0 和 1 的个数，每个分界点的代价可 $O(1)$ 计算。遍历所有 $n+1$ 个分界点取最小值。
题解代码
import sys
input = sys.stdin.readline
def solve():
n = int(input())
s = input().strip()
# pre1[i]: 前i个字符中'1'的个数
pre1 = [0] * (n + 1)
pre0 = [0] * (n + 1)
for i in range(n):
pre1[i + 1] = pre1[i] + (1 if s[i] == '1' else 0)
pre0[i + 1] = pre0[i] + (1 if s[i] == '0' else 0)
total0 = pre0[n]
total1 = pre1[n]
ans = n
for k in range(n + 1):
# 形态 0...01...1：前缀1改0 + 后缀0改1
cost_01 = pre1[k] + (total0 - pre0[k])
# 形态 1...10...0：前缀0改1 + 后缀1改0
cost_10 = pre0[k] + (total1 - pre1[k])
ans = min(ans, cost_01, cost_10)
print(ans)
T = int(input())
for _ in range(T):
solve()
复杂度分析
时间复杂度：$O(n)$，预处理前缀和 + 枚举分界点各一遍 空间复杂度：$O(n)$，前缀和数组
第 2 题：地图上的最短别墅距离
题目描述
给定一张 $n$ 行 $m$ 列的地图，字符 0 表示别墅位置，字符 1 表示其他位置。对于每个位置，求到最近别墅的最短曼哈顿步数（上下左右四方向，每步距离 1）。若该位置本身就是别墅，则距离为 0。
$1 \leq n, m \leq 1000$。
样例
输入
3 4
0111
0011
1111
输出
0 1 2 3
0 0 1 2
1 1 2 3
思路分析
第一步：暴力为什么不行
对每个格子单独 BFS 求最近别墅，复杂度为 $O(n^2 m^2)$，对于 $n = m = 1000$ 的数据量会超时。
第二步：多源 BFS 的思路
反向思考——不从每个格子出发找别墅，而是从所有别墅同时出发向外扩展。将所有 0 格子作为 BFS 的初始源点，距离设为 0，同时入队。BFS 按距离逐层扩展，每个格子第一次被访问时记录的距离就是它到最近别墅的最短距离。
第三步：正确性
多源 BFS 等价于在图中新增一个虚拟超级源点，向所有别墅连一条权为 0 的边，然后从超级源做单源 BFS。每个格子最多入队一次，总复杂度为 $O(nm)$。
题解代码
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)]
queue = deque()
# 所有别墅同时作为BFS起点
for i in range(n):
for j in range(m):
if grid[i][j] == '0':
dist[i][j] = 0
queue.append((i, j))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while queue:
x, y = queue.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
queue.append((nx, ny))
out = []
for i in range(n):
out.append(' '.join(map(str, dist[i])))
print('\n'.join(out))
solve()
复杂度分析
时间复杂度：$O(nm)$，每个格子最多入队一次 空间复杂度：$O(nm)$，距离数组和 BFS 队列
第 3 题：最大化打铁次数的期望
题目描述
ICP 赛季共 $n$ 周，每周有一场比赛。第 $i$ 场比赛成功打铁的概率为 $p_i$。参加第 $i$ 场后，有 $q_i$ 的概率被禁止参加第 $i+1$ 场（禁令在第 $i+1$ 周结束后自动解除）。可自由选择参加哪些比赛，求打铁次数的最大期望值。
$1 \leq n \leq 10^5$，$0 \leq p_i, q_i \leq 1$。误差不超过 $10^{-6}$ 即被接受。
样例
输入
2
0.5 0.5
0.5 0.0
输出
0.75
思路分析
第一步：分析决策结构
每场比赛面临”参加/跳过”的选择，且参加后可能影响下一场的可用性。这是一个带后效性的序列决策问题，适合用 DP。
第二步：定义状态
设 $f_i$ 表示从第 $i$ 周开始、当前未被禁赛时，到赛季结束能获得的最大期望打铁次数。从后往前递推。
第三步：状态转移
对于第 $i$ 场有两个选择：
- 跳过：不参赛，无收益也无禁赛风险，期望为 $f_{i+1}$
- 参加：本场贡献期望 $p_i$。赛后有 $(1 - q_i)$ 概率下周仍可参加（对应 $f_{i+1}$）；有 $q_i$ 概率被禁赛跳过第 $i+1$ 周（对应 $f_{i+2}$）
参加的期望为 $p_i + (1 - q_i) \cdot f_{i+1} + q_i \cdot f_{i+2}$。
取两者较大值：$f_i = \max(\text{skip}, \text{take})$。
第四步：实现优化
转移只依赖 $f_{i+1}$ 和 $f_{i+2}$，用两个变量滚动即可，空间 $O(1)$。
题解代码
import sys
input = sys.stdin.readline
def solve():
n = int(input())
p = [0.0] * n
q = [0.0] * n
for i in range(n):
parts = input().split()
p[i] = float(parts[0])
q[i] = float(parts[1])
# next1 = f[i+1], next2 = f[i+2]，从后往前递推
next1 = 0.0
next2 = 0.0
for i in range(n - 1, -1, -1):
take = p[i] + (1.0 - q[i]) * next1 + q[i] * next2
skip = next1
cur = max(take, skip)
next2 = next1
next1 = cur
print(f"{next1:.10f}")
solve()
复杂度分析
时间复杂度：$O(n)$，从后向前遍历一次 空间复杂度：$O(n)$，存储输入数组（DP 本身只需 $O(1)$ 额外空间）
小结
- 第一题是前缀和的经典应用：观察到合法串只有两种形态后，枚举分界点 + 前缀和即可 $O(n)$ 求解
- 第二题是多源 BFS 模板题：所有源点同时入队，一次 BFS 解决所有点到最近源的距离
- 第三题是带约束的序列决策 DP：禁赛机制使得参加第 $i$ 场可能跳过第 $i+1$ 场，状态转移需考虑两步后的收益