大厂真题 / 上海AILab

上海AILab 5.26 笔试真题 - 通用岗

本场考试概述

考试时间：2026年5月26日 考试岗位：通用 难度评级：中等偏难（第三题数学推导难度较大）

考点分析：

1. 第一题：榨汁机——模拟（难度简单）
2. 第二题：栈中熔合——栈模拟 + GCD（难度中等）
3. 第三题：排列mex计数——mex 单调性 + 最小覆盖窗口去重（难度困难）

建议策略：

1. 前两题题面较长但思路明确，先按描述把状态机模拟清楚，再下手写代码
2. 第三题需要先发现”$\text{mex} \geq v$ 等价于窗口包含 ${0, 1, \ldots, v-1}$”这一对偶，把问题转成最小覆盖窗口长度的去重计数

第一题：榨汁机

题目描述

有 $n$ 个水果，体积为 $a_1, a_2, \ldots, a_n$。按下标从小到大依次尝试将水果放入榨汁机，榨汁机一次榨汁前可承载的水果总体积至多为 $m$。

规则如下：

• 当准备放入的水果使机内容量之和超过 $m$ 时，将这个水果直接给贪吃鬼吃掉
• 随后若榨汁机里已有水果（机内总体积 $> 0$），则立刻启动一次榨汁并清空
• 所有水果处理完后，若机内仍有水果，还需再启动一次榨汁

求榨汁机启动的总次数，以及贪吃鬼吃掉的水果总体积。

样例

输入

5 10
3 4 5 6 2

输出

2 5

思路分析

第一步：理清状态转移

维护一个变量 $\text{cur}$ 表示当前机内总体积。对每个水果 $x$：

• 若 $\text{cur} + x > m$：水果被贪吃鬼吃掉（累加到被吃总量），同时若 $\text{cur} > 0$，启动一次榨汁并清空
• 否则：$\text{cur} \mathrel{+}= x$

第二步：处理尾部残留

遍历结束后若 $\text{cur} > 0$，再启动一次。

全程只需一次线性扫描，没有需要回溯或查询的结构。

题解代码

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = list(map(int, input().split()))

cur = 0
eaten = 0
starts = 0

for x in a:
    if cur + x > m:
        eaten += x
        if cur > 0:
            starts += 1
            cur = 0
    else:
        cur += x

if cur > 0:
    starts += 1

print(starts, eaten)

复杂度分析

时间复杂度：$O(n)$ 空间复杂度：$O(n)$（存储输入数组）

第二题：栈中熔合

题目描述

给定正整数序列 $a_1, a_2, \ldots, a_n$ 和正整数阈值 $S$。从空栈开始，按顺序将 $a_i$ 依次压入栈中。

每次压入新元素后，执行如下熔合过程直至不能继续：

• 若栈顶元素为 $x$，其下方相邻元素为 $y$，并且 $x + y > S$，则将 $y$ 替换为 $\gcd(x, y)$ 并移除 $x$
• 重复检查直至栈中不存在相邻两元素之和严格大于 $S$ 的相邻对

处理完整个序列后，输出最终栈大小以及自栈底到栈顶的所有元素。

样例

输入

4 5
3 4 2 6

输出

2
1 2

思路分析

第一步：观察熔合的本质

每次熔合把两个元素变成一个 $\gcd$，值不会变大。熔合后新栈顶变小，可能使得它与更下方的元素之和不再超过 $S$，所以一轮循环检查即可稳定。

第二步：为什么直接循环就够？

关键观察：熔合后 $\gcd(x, y) \leq y$（原下方元素），因此新栈顶不会比它替换的那个 $y$ 更大。这意味着新栈顶与再下方元素的和 $\leq$ 原本 $y$ 与再下方元素的和——如果原本没触发熔合，现在也不会触发。所以每次压入后最多做一轮从栈顶向下的检查即可。

第三步：复杂度保证

每个元素最多入栈一次、出栈一次（被 GCD 替换掉时相当于出栈），总操作数为 $O(n)$。

题解代码

import sys
from math import gcd
input = sys.stdin.readline

n, S = map(int, input().split())
a = list(map(int, input().split()))

stack = []
for x in a:
    stack.append(x)
    while len(stack) >= 2 and stack[-1] + stack[-2] > S:
        top = stack.pop()
        stack[-1] = gcd(top, stack[-1])

print(len(stack))
print(*stack)

复杂度分析

时间复杂度：$O(n)$，每个元素至多入栈一次、出栈一次 空间复杂度：$O(n)$

第三题：排列mex计数

题目描述

给定长度为 $n$ 的排列 $a$（由 $0, 1, \ldots, n-1$ 构成），对 $1 \leq k \leq n$ 定义：

求区间 $[1, n-1]$ 中有多少 $k$ 满足 $f(k) = f(k+1)$。

这里 $\text{mex}$ 是没有出现在数组中的最小非负整数。

样例

输入

5
2 3 1 0 4

输出

2

思路分析

第一步：观察 $f(k)$ 的单调性

随着 $k$ 增大，前缀包含的值越多，$\text{mex}$ 只能不降。所以 $f$ 是单调不减的。$f(k) = f(k+1)$ 意味着在位置 $k+1$ 没有发生跳变。

第二步：什么时候会发生跳变？

$f(k) < f(k+1)$ 当且仅当 $a_{k+1}$ 恰好等于当前的 $\text{mex}$ 值。但更本质的等价描述是：

长度为 $k$ 的前缀的 $\text{mex} \geq v$ 当且仅当前缀同时包含 ${0, 1, \ldots, v-1}$。

第三步：转化为最小覆盖窗口问题

设 $\text{pos}[v]$ 为值 $v$ 在排列中的下标。要让前缀包含 ${0, 1, \ldots, v-1}$（从而 $\text{mex} \geq v$），需要前缀长度 $\geq$ 这些值中最大下标 $+1$。

但题目问的是前缀（固定从位置 0 开始），所以包含 ${0, \ldots, v-1}$ 的最短前缀长度为：

$f$ 在位置 $L(v)$ 发生从 $< v$ 到 $\geq v$ 的跳变。跳变点的总数等于 $L(1), L(2), \ldots, L(n)$ 中不同值的个数。

第四步：答案

总共 $n-1$ 个位置对，减去跳变点数即为 $f(k) = f(k+1)$ 的个数：

实现时只需要用一个变量追踪前缀最大下标，逐步加入值 $0, 1, \ldots, n-1$，将每步的 $L$ 值加入集合去重，最后用 $n-1$ 减去集合大小。

题解代码

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))

pos = [0] * n
for i, v in enumerate(a):
    pos[v] = i

distinct_L = set()
mx = pos[0]
for v in range(1, n):
    if pos[v] > mx:
        mx = pos[v]
    distinct_L.add(mx + 1)

print((n - 1) - len(distinct_L))

复杂度分析

时间复杂度：$O(n)$ 空间复杂度：$O(n)$

小结

• 第一题（榨汁机）：纯模拟题，按规则维护机内状态即可，注意处理结束后的残留
• 第二题（栈中熔合）：栈模拟 + GCD，关键洞察是 GCD 替换后值不增，不会引发向下方的连锁反应，保证了 $O(n)$ 总复杂度
• 第三题（排列mex计数）：本场最难，核心是发现”$\text{mex}$ 跳变点 = 最小覆盖前缀长度的不同值”这一等价转化，把看似复杂的 mex 问题降维为一个线性扫描 + 集合去重