大厂真题 / 阿里巴巴
阿里 3.25 笔试真题 - 研发岗
本场考试概述
考试时间：2026年3月25日 考试岗位：研发岗 难度评级：中等偏难
考点分析：
- 第一题：数学/贪心 — 糖果分配的最大最小值（难度中等）
- 第二题：贪心 — 两个排列的最大公共子序列（难度中等）
- 第三题：二分查找 + 数位DP — 第 k 个”喜欢的正整数”（难度困难）
建议策略：
- 前两题是思维题，想清楚贪心策略后代码量很小，务必快速拿下
- 第三题数位DP是经典难点，建议提前练熟数位DP模板，考场上才能稳定输出
第一题：圣诞老人分糖果
题目描述
圣诞老人有 n 种糖果，第 i 种糖果有 c[i] 颗。现在要把所有糖果分给 k 个小朋友，要求对于每一种糖果，任意两个小朋友分到的该种糖果数量之差不超过 1。
求某个小朋友分到的糖果总数的最小值和最大值。
样例
输入
1
3 2
5 2 7
输出
6 8
样例解释：3 种糖果分给 2 个小朋友。
| 糖果种类 | 总数 | 每人基础量 (c[i]//k) | 余数 (c[i]%k) | 分配方式 |
|---|---|---|---|---|
| 1 | 5 | 2 | 1 | 一人得 3，一人得 2 |
| 2 | 2 | 1 | 0 | 每人得 1 |
| 3 | 7 | 3 | 1 | 一人得 4，一人得 3 |
- 最大值：让同一个小朋友尽可能多地拿到”+1”，糖果 1 和糖果 3 都有余数，所以最大值 = (2+1+3) + 2 = 8
- 最小值：让这个小朋友尽可能少地拿到”+1”，最小值 = (2+1+3) + 0 = 6
思路分析
对于第 i 种糖果，每个小朋友至少分到 base_i = c[i] // k 颗，还剩余 r_i = c[i] % k 颗需要分给 r_i 个小朋友（每人多得 1 颗）。
最大值：我们希望目标小朋友从尽可能多的糖果种类中拿到”+1”。每种糖果只要 r_i > 0，就存在至少一个名额可以给目标小朋友。因此：
\[\text{max} = \sum \text{base}_i + \text{count}(r_i > 0)\]最小值：我们希望目标小朋友尽可能少地被分到”+1”。对于每种糖果 i，有 r_i 个”+1”需要分配给 k 个人中的 r_i 个。我们优先把这些”+1”分给其他 k-1 个人。但每种糖果最多只能让 k-1 个”其他人”各吸收 1 个”+1”，所以 n 种糖果的其他人总共最多吸收 (k-1) * n 个”+1”。如果所有余数之和 sum(r_i) 超过了这个上限，目标小朋友就不得不承担多出来的部分：
\[\text{min} = \sum \text{base}_i + \max(0,\ \sum r_i - (k-1) \times n)\]时间复杂度：O(n)。 空间复杂度：O(n)。
import sys
input = sys.stdin.readline
def solve():
n, k = map(int, input().split())
c = list(map(int, input().split()))
base_sum = 0
cnt_pos = 0
extra_sum = 0
for ci in c:
base_sum += ci // k
r = ci % k
if r > 0:
cnt_pos += 1
extra_sum += r
max_val = base_sum + cnt_pos
min_val = base_sum + max(0, extra_sum - (k - 1) * n)
print(min_val, max_val)
T = int(input())
for _ in range(T):
solve()
第二题：公共子序列
题目描述
给定两个长度为 n 的排列 p 和 q（均为 1~n 的排列），请找出它们的字典序最大的公共子序列。
样例
输入
5
3 5 1 2 4
2 5 4 1 3
输出
2
5 4
样例解释：
- 在 p = [3, 5, 1, 2, 4] 中，5 在位置 1，4 在位置 4，子序列 [5, 4] 合法
- 在 q = [2, 5, 4, 1, 3] 中，5 在位置 1，4 在位置 2，子序列 [5, 4] 合法
- [5, 4] 是字典序最大的公共子序列
思路分析
要求字典序最大，自然希望尽可能先选大的值。贪心策略如下：
- 预处理每个值在 p 和 q 中的位置，记为 pos_p[v] 和 pos_q[v]
- 维护两个指针 ip 和 iq，分别表示在 p 和 q 中”当前已选到的位置之后”的起始位置
- 从大到小遍历值 v = n, n-1, …, 1：
- 如果 pos_p[v] >= ip 且 pos_q[v] >= iq，说明 v 在两个排列中都出现在当前指针之后，可以选入结果
- 选入后，更新 ip = pos_p[v] + 1，iq = pos_q[v] + 1
为什么贪心是正确的？ 因为我们是按值从大到小考虑的。对于当前值 v，如果它在两个排列中的位置都合法，选它一定不会比跳过它更差 — 选了它只会”消耗”两个排列中 v 之前的位置，而比 v 小的值无论如何都排在 v 后面（字典序意义上），不会因为选了 v 而产生更优的替代方案。
时间复杂度：O(n)。 空间复杂度：O(n)。
import sys
input = sys.stdin.readline
def solve():
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
pos_p = [0] * (n + 1)
pos_q = [0] * (n + 1)
for i in range(n):
pos_p[p[i]] = i
pos_q[q[i]] = i
result = []
ip = iq = 0
for v in range(n, 0, -1):
if pos_p[v] >= ip and pos_q[v] >= iq:
result.append(v)
ip = pos_p[v] + 1
iq = pos_q[v] + 1
print(len(result))
print(' '.join(map(str, result)))
solve()
第三题：喜欢的正整数
题目描述
定义一个正整数是”喜欢的”，当且仅当它同时满足以下两个条件：
- 不能被 3 整除
- 十进制表示中不包含数字 ‘3’
给定 k，求第 k 个”喜欢的”正整数。
样例
输入
5
1
2
3
4
5
输出
1
2
4
5
7
样例解释：
- 1: 不被 3 整除，不含数字 3 → 喜欢
- 2: 不被 3 整除，不含数字 3 → 喜欢
- 3: 被 3 整除 → 不喜欢
- 4: 不被 3 整除，不含数字 4… 不含数字 3 → 喜欢
- 5: 不被 3 整除，不含数字 3 → 喜欢
- 6: 被 3 整除 → 不喜欢
- 7: 不被 3 整除，不含数字 3 → 喜欢
所以前 5 个喜欢的正整数是 1, 2, 4, 5, 7。
思路分析
本题是经典的”求第 k 个满足条件的数”问题，标准解法是 二分答案 + 数位DP 计数。
第一步：二分答案
如果我们能快速计算 “1 到 x 之间有多少个喜欢的正整数”（记为 count_liked(x)），那么就可以二分找到最小的 x 使得 count_liked(x) >= k，这个 x 就是答案。
二分范围：下界 lo = 1，上界 hi 取一个足够大的值（如 2 * 10^19）。
第二步：数位DP计数
核心问题变成：给定上界 x，计算 [1, x] 中满足”不含数字 3 且不被 3 整除”的正整数个数。
状态设计：
逐位枚举 x 的每一位数字，维护以下状态：
| 状态 | 含义 | 取值范围 |
|---|---|---|
| rem | 当前已确定的数位之和对 3 取模的余数 | 0, 1, 2 |
| started | 是否已经填过非零数字（用于处理前导零） | 0, 1 |
| tight | 当前是否还受到上界 x 的约束 | 受限 / 自由 |
其中 tight 状态决定了当前位可以填的数字范围：
- 受限（tight）：当前位只能填 0 到 s[i]（x 的第 i 位数字）
- 自由（free）：当前位可以填 0 到 9
状态转移：
对于每一位，我们枚举当前位填的数字 d（跳过 d=3），然后更新状态：
new_rem = (rem + d) % 3new_started = 1 if (started or d > 0) else 0- 如果当前是 tight 且 d == s[i]，则下一位仍然是 tight；否则下一位变为 free
实现细节：
用两组二维数组 tight[rem][started] 和 free[rem][started] 分别记录处于受限/自由状态下各种 (rem, started) 组合的方案数。逐位推进，每一位产生新的 nt（新的受限状态）和 nf（新的自由状态）。
统计答案：
处理完所有位后，满足条件的数 = 所有 rem != 0 且 started == 1 的状态之和。rem != 0 保证不被 3 整除，started == 1 保证是正整数（排除了”全选 0”的情况，即排除 0 本身）。
\[\text{count\_liked}(x) = \sum_{r \in \{1,2\}} (\text{tight}[r][1] + \text{free}[r][1])\]时间复杂度：二分 O(log(2 * 10^19)) 轮，每轮数位DP遍历 O(20) 位，每位枚举 9 个数字（跳过3），状态数 3 * 2 = 6。总复杂度 O(T * 60 * 20 * 9 * 6)，非常快。
import sys
input = sys.stdin.readline
def count_liked(x):
if x <= 0:
return 0
s = str(x)
n = len(s)
# tight[rem][started], free[rem][started]
tight = [[0] * 2 for _ in range(3)]
free = [[0] * 2 for _ in range(3)]
tight[0][0] = 1 # 初始状态：余数0，未开始，受限
for i in range(n):
dlim = int(s[i])
nt = [[0] * 2 for _ in range(3)]
nf = [[0] * 2 for _ in range(3)]
for rem in range(3):
for st in range(2):
# 处理 tight 状态的转移
if tight[rem][st]:
cnt = tight[rem][st]
for d in range(dlim + 1):
if d == 3:
continue
nr = (rem + d) % 3
ns = 1 if (st or d > 0) else 0
if d == dlim:
nt[nr][ns] += cnt
else:
nf[nr][ns] += cnt
# 处理 free 状态的转移
if free[rem][st]:
cnt = free[rem][st]
for d in range(10):
if d == 3:
continue
nr = (rem + d) % 3
ns = 1 if (st or d > 0) else 0
nf[nr][ns] += cnt
tight = nt
free = nf
# 统计：rem != 0 且 started == 1
return sum(tight[r][1] + free[r][1] for r in range(1, 3))
def solve(k):
lo, hi = 1, 2 * 10**19
while lo < hi:
mid = (lo + hi) // 2
if count_liked(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo
t = int(input())
out = []
for _ in range(t):
k = int(input())
out.append(str(solve(k)))
print('\n'.join(out))
小结
- 第一题糖果分配是数学/贪心题，关键在于分析余数的分配策略，推导出最大值和最小值的计算公式
- 第二题公共子序列利用排列的性质，从大到小贪心选取，O(n) 即可解决
- 第三题是数位DP经典应用，”第 k 个满足条件的数”= 二分答案 + 数位DP计数，状态设计（余数 + 是否开始 + 是否受限）是数位DP的通用模板，建议熟练掌握