大厂真题 / 阿里巴巴
阿里 5.13 笔试真题 - 工程岗
本场考试概述
考试时间：2026年5月13日 考试岗位：工程岗 难度评级：中等偏难
考点分析：
- 第一题：位运算 popcount（难度简单）
- 第二题：线性 DP，26 字母末位状态（难度中等）
- 第三题：颜色超级节点 + 分层 Dijkstra（难度困难）
建议策略：
- 第一题抓住”二进制 1 的个数即最少操作次数”这一性质，一行
bin(y-x).count('1')即可 - 第二题状态设计为”填到第 $i$ 位、末位字母为 $c$”，用滚动数组 + 总数缓存避免重复求和
- 第三题先用并查集把同色连通块缩成超级节点，再叠一层 0/1 状态标记是否经过幸运房间，跑分层 Dijkstra
第一题：二次幂变换
题目描述
给定两个整数 $x$ 与 $y$，可以进行若干次操作使 $x$ 变为 $y$。一次操作定义为：选择任意非负整数 $k$，将当前数值加上 $2^k$。求使 $x$ 变为 $y$ 所需的最少操作次数。
多组测试数据，第一行输入整数 $T$，接下来 $T$ 行每行两个整数 $x, y$。
样例
输入
5
0 0
0 7
5 14
-3 5
-10 10
输出
0
3
2
1
2
思路分析
第一步：观察题目性质
每次操作加上某个 $2^k$，问最少几次从 $x$ 走到 $y$。本质是把差值 $d = y - x$ 拆成若干个 $2^k$ 之和，求拆分项数最少。
第二步：问题转化
任何正整数 $d$ 的二进制表示本身就是一种拆分——每个为 1 的位对应一个 $2^k$。如果某次拆分中有两个相同的 $2^k$，可以合并为一个 $2^{k+1}$，操作次数减少 1。不断合并直到没有重复指数，就得到了 $d$ 的标准二进制分解。
第三步：结论
最少操作次数 = $d$ 的二进制表示中 1 的个数，即 $\text{popcount}(y - x)$。
实现注意：Python 的整数是任意精度的，不存在溢出问题，直接 bin(y - x).count('1') 即可。
题解代码
import sys
input = sys.stdin.readline
def solve():
T = int(input())
for _ in range(T):
x, y = map(int, input().split())
d = y - x
print(bin(d).count('1'))
solve()
复杂度分析
时间复杂度：$O(T \log d)$，其中 $d = y - x$，bin().count('1') 与位数线性相关
空间复杂度：$O(1)$
第二题：字符串计数
题目描述
给定一个仅由小写字母与 ? 组成的字符串 $s$（长度为 $n$）。求有多少个不同的、仅由小写字母组成的字符串 $t$（长度为 $n$）满足：
- 对所有下标 $i$，若 $s_i \neq$
?，则 $t_i = s_i$ - 任意相邻字符均不相同，即对所有 $i$，有 $t_i \neq t_{i+1}$
答案对 $10^9 + 7$ 取模。多组测试数据，保证所有 $n$ 的总和不超过 $10^6$。
样例
输入
5
3
a?b
2
??
4
a??a
4
aabb
4
abab
输出
24
650
600
0
1
思路分析
第一步：观察题目性质
固定位置必须填对应字母，? 位置可自由选，但相邻字符不能相同。暴力枚举不可行（$26^n$），需要 DP。
第二步：状态设计
令 $f[i][c]$ 表示填到第 $i$ 位、末位字母为 $c$（$c \in [0, 25]$）的合法方案数。再记 $\text{total} = \sum_{c=0}^{25} f[i][c]$，用于快速转移。
第三步：转移方程
从第 $i-1$ 位转移到第 $i$ 位，相邻不同的约束意味着末位 $c$ 的方案数 = “上一轮所有非 $c$ 字母方案之和” = $\text{total} - f[i-1][c]$。
- 若 $s_i =$
?：所有 26 个字母都保留，$f[i][c] = \text{total} - f[i-1][c]$，新的 $\text{total}’ = 25 \times \text{total}$ - 若 $s_i$ 为固定字母 $a$：只有 $f[i][a] = \text{total} - f[i-1][a]$ 保留，其余清零，新的 $\text{total}’ = f[i][a]$
第四步：实现要点
用一个长度 26 的数组滚动，配合一个 $\text{total}$ 变量缓存总和，避免每次 $O(26)$ 求和。整体 $O(26n)$。
题解代码
import sys
input = sys.stdin.readline
def solve():
MOD = 10**9 + 7
T = int(input())
for _ in range(T):
n = int(input())
s = input().strip()
f = [0] * 26
if s[0] == '?':
for c in range(26):
f[c] = 1
total = 26
else:
f[ord(s[0]) - ord('a')] = 1
total = 1
for i in range(1, n):
ch = s[i]
if ch == '?':
g = [0] * 26
for c in range(26):
g[c] = (total - f[c]) % MOD
f = g
total = (25 * total) % MOD
else:
idx = ord(ch) - ord('a')
val = (total - f[idx]) % MOD
f = [0] * 26
f[idx] = val
total = val
print(total % MOD)
solve()
复杂度分析
时间复杂度：$O(26n)$，每组数据线性扫描字符串，每个位置遍历 26 个字母 空间复杂度：$O(26)$，仅保存当前字母频率数组
第三题：迷宫
题目描述
迷宫由 $n$ 个房间与 $q$ 条传送门构成，第 $i$ 条传送门双向连接房间 $x_i$ 与 $y_i$，颜色为 $c_i$。打开颜色 $c$ 的传送门需支付费用 $c$ 购买对应钥匙，每次仅能携带一把钥匙（可无限次使用），也可购买新钥匙替换旧钥匙。
迷宫中放置了 $k$ 只「七彩草蛉」作为幸运房间。如果某房间有草蛉，可立即免费制作一把任意颜色钥匙；其他房间制作钥匙需支付费用。
从房间 $1$ 出发，目标是经过至少一个草蛉房间并最终抵达房间 $n$。计算最小总花费；若无法完成输出 $-1$。
样例
输入
3 1 3
2
1 2 1
2 3 1
3 1 2
输出
1
思路分析
第一步：观察题目性质
普通最短路只关心”在哪个房间”，但本题花费由”钥匙颜色”和”是否经过幸运房间”共同决定。同一颜色的所有传送门只需购买一次钥匙，且同色连通块内的房间可以自由移动（持有该色钥匙时）。
第二步：颜色超级节点（关键转化）
对每种颜色 $c$，把所有颜色为 $c$ 的边的端点用并查集合并，每个连通分量变成一个”超级节点”。这样”买一把颜色 $c$ 的钥匙然后在同色块里走”就被拆成两步：
- 从房间 $u$ 进入超级节点 $S$：边权 = 0（如果 $u$ 是幸运房间）或 $c$（否则），代表购买钥匙的费用
- 从超级节点 $S$ 出去到块内任意房间 $v$：边权 = 0，代表持钥匙自由移动
第三步：分层状态
给每个节点加一个 0/1 比特，标记”路径上是否已经过幸运房间”。状态 $(u, \text{layer})$，其中 layer=0 表示还没经过幸运房间，layer=1 表示已经过。答案是 $\text{dist}[n][\text{layer}=1]$。
进入一个幸运节点（包括含幸运房间的超级节点）时，layer 从 0 变为 1。
第四步：Dijkstra 求解
所有边权非负（0 或颜色值 $c \geq 1$），用 Dijkstra 即可。节点总数 $\leq n + q$（每条边最多新增一个超级节点），边数 $O(q)$，加上 2 层状态，总复杂度 $O((n+q) \log(n+q))$。
题解代码
import sys
import heapq
input = sys.stdin.readline
def solve():
n, k, q = map(int, input().split())
lucky_rooms = set(map(int, input().split()))
edges = []
color_edges = {}
for _ in range(q):
x, y, c = map(int, input().split())
edges.append((x, y, c))
if c not in color_edges:
color_edges[c] = []
color_edges[c].append((x, y))
# 并查集
parent = {}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
# 为每种颜色建立超级节点
next_id = n + 1
super_id_map = {} # (color, root) -> super_node_id
edge_to_super = [0] * q
lucky_node = set()
# 标记幸运原始节点
for r in lucky_rooms:
lucky_node.add(r)
idx = 0
for color, epairs in color_edges.items():
parent.clear()
nodes_in_color = set()
for x, y in epairs:
nodes_in_color.add(x)
nodes_in_color.add(y)
parent.setdefault(x, x)
parent.setdefault(y, y)
for x, y in epairs:
union(x, y)
root_to_sid = {}
for node in nodes_in_color:
r = find(node)
if r not in root_to_sid:
root_to_sid[r] = next_id
next_id += 1
# 检查超级节点是否包含幸运房间
for node in nodes_in_color:
if node in lucky_rooms:
r = find(node)
sid = root_to_sid[r]
lucky_node.add(sid)
# 记录每条边对应的超级节点
for x, y in epairs:
r = find(x)
super_id_map[(color, id(epairs), x, y)] = root_to_sid[r]
# 重新构建：为每条边找到其超级节点
# 用更简单的方式重建
parent.clear()
edge_super = []
next_id = n + 1
lucky_node = set()
for r in lucky_rooms:
lucky_node.add(r)
color_groups = {}
for i, (x, y, c) in enumerate(edges):
if c not in color_groups:
color_groups[c] = []
color_groups[c].append(i)
super_for_edge = [0] * q
for color, indices in color_groups.items():
parent.clear()
for i in indices:
x, y, c = edges[i]
parent.setdefault(x, x)
parent.setdefault(y, y)
union(x, y)
root_to_sid = {}
for i in indices:
x, y, c = edges[i]
r = find(x)
if r not in root_to_sid:
root_to_sid[r] = next_id
next_id += 1
# 标记含幸运房间的超级节点
for i in indices:
x, y, c = edges[i]
for node in (x, y):
if node in lucky_rooms:
r = find(node)
lucky_node.add(root_to_sid[r])
for i in indices:
x, y, c = edges[i]
r = find(x)
super_for_edge[i] = root_to_sid[r]
# 建图：邻接表
NV = next_id
graph = [[] for _ in range(NV)]
for i, (x, y, c) in enumerate(edges):
sid = super_for_edge[i]
# 房间 -> 超级节点：费用 = 0(幸运房间) 或 c(普通房间)
wx = 0 if x in lucky_rooms else c
wy = 0 if y in lucky_rooms else c
graph[x].append((sid, wx))
graph[y].append((sid, wy))
# 超级节点 -> 房间：费用 = 0
graph[sid].append((x, 0))
graph[sid].append((y, 0))
# 分层 Dijkstra
INF = float('inf')
dist = [[INF, INF] for _ in range(NV)]
src = 1
init_layer = 1 if src in lucky_node else 0
dist[src][init_layer] = 0
pq = [(0, src, init_layer)]
while pq:
d, u, layer = heapq.heappop(pq)
if d > dist[u][layer]:
continue
if u == n and layer == 1:
print(d)
return
for v, w in graph[u]:
nl = 1 if (layer == 1 or v in lucky_node) else 0
nd = d + w
if nd < dist[v][nl]:
dist[v][nl] = nd
heapq.heappush(pq, (nd, v, nl))
print(-1)
solve()
复杂度分析
时间复杂度：$O((n + q) \log(n + q))$，建图 $O(q \cdot \alpha(n))$（并查集），Dijkstra $O((n+q) \log(n+q))$ 空间复杂度：$O(n + q)$，邻接表与两层距离数组
小结
- 第一题是经典的 popcount 应用：将 $2^k$ 拆分问题转化为二进制 1 的计数，一行搞定
- 第二题是线性 DP 的典型应用：26 字母末位状态 + total 缓存技巧，避免每步 $O(26^2)$ 的暴力转移
- 第三题是本场最难的综合图论题：颜色超级节点将”买钥匙+走同色块”建模为图上边权，分层 Dijkstra 处理”必须经过幸运房间”的约束，思路链条较长但每一步都有明确的动机