大厂真题 / 得物

得物 4.18 笔试真题 - 暑期实习

本场考试概述

考试时间：2026年4月18日 考试岗位：暑期实习（通用） 难度评级：中等偏难

考点分析：

1. 第一题：状态压缩 + 记忆化搜索（难度困难）
2. 第二题：状态机 DP（难度中等）
3. 第三题：BFS + 优先队列 / 接雨水 2D（难度中等）

建议策略：

1. 第二题状态机 DP 是经典模型，建议优先拿满分
2. 第三题是 Trapping Rain Water II 变体，熟悉模板可快速 AC
3. 第一题 n <= 15 暗示状态压缩，需要仔细设计状态和转移，考场上能理清收益分配逻辑就很好

第一题：栈的统计

题目描述

给定两个长度为 n 的数组 a 和 b。有一个初始为空的栈，需要进行 2n 次操作，每次操作为以下两种之一：

• 操作 1：将数组 a 中尚未入栈的下一个元素压入栈中（按 a[0], a[1], …, a[n-1] 的顺序依次入栈）。
• 操作 2：弹出栈顶元素，获得收益 b[当前栈大小 - 1] * a[栈顶元素]。

要求所有元素必须恰好入栈一次、出栈一次（即 2n 次操作后栈为空）。求所有合法操作方案的总收益之和。

n <= 15。

样例

输入

2
1 2
2 3

输出

14

思路分析

第一步：理解操作语义

操作序列本质上是一个”入栈-出栈”的调度方案。n 个元素必须按顺序入栈（a[0] 先于 a[1] 先于 a[2]…），但出栈时机可以灵活选择——只要栈非空就可以弹出。每次弹出时，收益取决于当时栈的大小和弹出的元素值。

例如 n=2 时，合法方案有两种：

• push(a[0]), pop(a[0]), push(a[1]), pop(a[1])：收益 = b[0]a[0] + b[0]a[1] = 21 + 22 = 6
• push(a[0]), push(a[1]), pop(a[1]), pop(a[0])：收益 = b[1]a[1] + b[0]a[0] = 32 + 21 = 8

总收益 = 6 + 8 = 14。

第二步：状态设计——用 bitmask 表示栈内元素

因为入栈顺序固定（a[0] 到 a[n-1]），我们可以用一个变量 pushed 记录当前已经入栈了多少个元素，用一个 bitmask mask 记录当前哪些元素仍在栈中（第 i 位为 1 表示 a[i] 在栈中）。

状态 (pushed, mask) 唯一确定了当前的局面。注意 mask 中为 1 的位一定都 < pushed（只有已入栈的元素才可能在栈中）。

第三步：记忆化搜索的返回值

定义 dfs(pushed, mask) 返回一个二元组 (ways, total_benefit)：

• ways：从当前状态到终态（pushed=n, mask=0）的合法操作方案数
• total_benefit：所有这些方案的收益总和

终态：pushed == n 且 mask == 0 时，返回 (1, 0)。

第四步：转移——push 和 pop 两种选择

从状态 (pushed, mask)：

1. Push 操作（条件：pushed < n）：将 a[pushed] 入栈，转移到 (pushed+1, mask

   (1«pushed))。这步操作本身没有收益。

2. Pop 操作（条件：mask != 0）：弹出栈顶元素。栈顶是 mask 中编号最大的那一位（因为入栈顺序递增，后入的编号更大，且栈是后进先出）。设栈顶位置为 top，当前栈大小为 popcount(mask)，收益为 gain = b[popcount(mask) - 1] * a[top]。转移到 (pushed, mask ^ (1«top))。

对于 pop 操作，后续子问题返回 (ways_after, benefit_after)，那么：

• 方案数贡献：ways_after
• 收益贡献：ways_after * gain + benefit_after（每条后续方案都会累加当前 pop 的收益）

第五步：汇总两个分支

将 push 分支和 pop 分支的 (ways, benefit) 分别累加，得到当前状态的总方案数和总收益。

第六步：复杂度验证

状态数：pushed 有 n+1 种取值，mask 最多 2^n 种。但有效状态远少于 (n+1) * 2^n，因为 mask 中的 1 位必须 < pushed。总有效状态约 O(3^n)（每个元素三种状态：未入栈、在栈中、已出栈）。对于 n=15，3^15 约 1430 万，加上 lru_cache 的开销，在时限内可行。

每个状态的转移中，找栈顶需要 O(n) 扫描，因此总时间 O(n * 3^n)。

题解代码

import sys
from functools import lru_cache
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    @lru_cache(maxsize=None)
    def dfs(pushed, mask):
        # 终态：所有元素已入栈且已出栈
        if pushed == n and mask == 0:
            return (1, 0)
        total_ways, total_benefit = 0, 0
        # 选择1：Push 下一个元素
        if pushed < n:
            ways, benefit = dfs(pushed + 1, mask | (1 << pushed))
            total_ways += ways
            total_benefit += benefit
        # 选择2：Pop 栈顶元素
        if mask != 0:
            # 栈顶是 mask 中最高位（最后入栈的）
            top = -1
            for i in range(pushed - 1, -1, -1):
                if mask & (1 << i):
                    top = i
                    break
            # 当前栈大小 = popcount(mask)
            x = bin(mask).count('1')
            gain = b[x - 1] * a[top]
            ways, benefit = dfs(pushed, mask ^ (1 << top))
            total_ways += ways
            # 每条后续方案都累加当前 pop 的收益
            total_benefit += ways * gain + benefit
        return (total_ways, total_benefit)

    _, ans = dfs(0, 0)
    print(ans)

solve()

复杂度分析

时间复杂度：O(n * 3^n)。有效状态数约 3^n（每个元素三种状态），每个状态内找栈顶需 O(n)。n=15 时约 2100 万次操作。 空间复杂度：O(3^n)，记忆化缓存存储所有有效状态。

第二题：爬山

题目描述

有 n 天可以爬山，每天爬山能获得 a[i] 的快乐值。爬山规则：如果某天爬了山，那么第二天必须休息，除非使用一次”例外机会”跳过休息。总共有 k 次例外机会可以使用。求能获得的最大快乐值总和。

样例

输入

7 1
1 2 3 4 5 6 7

输出

19

思路分析

第一步：理解约束

正常情况下，如果第 i 天爬山，第 i+1 天必须休息（不能连续两天爬山）。但如果使用一次例外机会，就可以连续爬山（即第 i 天和第 i+1 天都爬山）。总共可以使用 k 次例外。

这是一个典型的”带资源限制的选择问题”，适合用状态机 DP 解决。

第二步：状态定义

定义 f[i][j][s]：考虑前 i 天，已使用 j 次例外机会，第 i 天状态为 s 时的最大快乐值。

状态 s 取值：

• s = 0：第 i 天休息
• s = 1：第 i 天爬山

第三步：状态转移

对于第 i 天休息（s=0）：

• 前一天可以是任意状态（休息或爬山都行，因为休息不受限制）
• f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1])

对于第 i 天爬山（s=1），有两种情况：

1. 前一天休息（正常爬山，不消耗例外）：f[i-1][j][0] + a[i]
2. 前一天也爬山（连续爬山，消耗一次例外）：f[i-1][j-1][1] + a[i]（需要 j >= 1）

• f[i][j][1] = max(f[i-1][j][0], f[i-1][j-1][1] if j >= 1) + a[i]

第四步：初始化和答案

初始化：f[0][0][0] = 0（第 0 天休息，0 次例外，快乐值为 0）。其余为负无穷。

如果下标从 1 开始：

• f[1][0][0] = 0（第 1 天休息）
• f[1][0][1] = a[1]（第 1 天爬山）

答案：max(f[n][j][s]) 对所有 j <= k, s in {0,1}。

第五步：验证样例

n=7, k=1, a=[1,2,3,4,5,6,7]。

不使用例外的最优：选第 1,3,5,7 天，快乐值 = 1+3+5+7 = 16。 使用 1 次例外：可以让某两天连续。最优是选第 2,3,5,7 天（第 2 和 3 天连续，消耗 1 次例外），快乐值 = 2+3+5+7 = 17。或者选第 1,3,5,6,7 天（第 6 和 7 天连续），快乐值 = 1+3+5+6+7 = 22？

等等，让我重新分析。使用例外可以连续爬山，意味着可以多选一天。最优应该是选尽量多且大的值。选第 3,4,5,6,7 天：第 3-4 连续（1次例外），第 4-5 连续（又要1次例外），超出了。

k=1 只能有 1 对连续。最优：选第 1,3,5,6,7 天——第 5-6 连续用 1 次例外，第 6-7 连续又需要 1 次。不行。

实际只能有 1 次连续：选第 1,3,5,7 天加上第 6 天，需要第 5-6 连续消耗例外，但第 6-7 又连续需要再一次。不可行。

正确理解：选第 1,3,4,6 天：第 3-4 连续用 1 次例外，快乐值 = 1+3+4+6 = 14。或选第 2,4,5,7 天：第 4-5 连续，快乐值 = 2+4+5+7 = 18。或选第 1,3,5,6 天：第 5-6 连续，快乐值 = 1+3+5+6 = 15。或选第 2,4,6,7 天：第 6-7 连续，快乐值 = 2+4+6+7 = 19。

答案 19，与样例一致。

第六步：空间优化

由于第 i 天只依赖第 i-1 天，可以用滚动数组将空间从 O(nk) 优化到 O(k)。但 O(nk) 通常已足够。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    # f[j][s]: 到当前天为止，用了 j 次例外，当天状态 s 的最大快乐值
    # s=0 休息，s=1 爬山
    NEG_INF = float('-inf')

    # 初始化：第 0 天之前，j=0, 休息状态，快乐值 0
    prev = [[NEG_INF, NEG_INF] for _ in range(k + 1)]
    prev[0][0] = 0

    for i in range(n):
        cur = [[NEG_INF, NEG_INF] for _ in range(k + 1)]
        for j in range(k + 1):
            # 当天休息：前一天任意状态
            val = max(prev[j][0], prev[j][1])
            if val > cur[j][0]:
                cur[j][0] = val
            # 当天爬山
            # 情况1：前一天休息（不消耗例外）
            if prev[j][0] != NEG_INF:
                val = prev[j][0] + a[i]
                if val > cur[j][1]:
                    cur[j][1] = val
            # 情况2：前一天爬山（消耗 1 次例外，即从 j-1 转移）
            if j >= 1 and prev[j - 1][1] != NEG_INF:
                val = prev[j - 1][1] + a[i]
                if val > cur[j][1]:
                    cur[j][1] = val
        prev = cur

    ans = 0
    for j in range(k + 1):
        ans = max(ans, prev[j][0], prev[j][1])
    print(ans)

solve()

复杂度分析

时间复杂度：O(nk)，双层循环遍历天数和例外使用次数。 空间复杂度：O(k)，滚动数组只保留前一天的状态。

第三题：防水建材

题目描述

给定一个 n x m 的高度矩阵，表示一片区域的地面高度。下雨后，水会在低洼处积聚。边缘格子的水会流出，因此边缘格子无法积水。求雨后形成的独立水池数量（即被积水的连续区域构成的连通分量个数）。

样例

输入

4 4
2 3 5 1
4 1 2 3
1 5 4 2
1 2 2 2

输出

1

思路分析

第一步：问题本质——接雨水 II 的变体

这是经典的 Trapping Rain Water II（LeetCode 407）的变体。在二维地形上，水能不能积住取决于该区域周围的”围墙”是否足够高。具体来说，一个格子能积水当且仅当从它出发的所有路径到达边界前，都必须经过比它高的格子。

积水高度 = min(所有路径到边界需翻越的最高”矮墙”) - 格子自身高度。如果这个值 > 0，说明该格子被淹没。

第二步：最小堆 BFS 确定每个格子的水位

使用优先队列（最小堆）从边界向内扩展：

1. 将所有边界格子加入最小堆，它们的水位等于自身高度（边界不能积水）
2. 标记所有边界格子为已访问
3. 每次从堆中取出水位最小的格子 (water_level, x, y)
4. 遍历其四个邻居：若邻居未访问，则邻居的水位 = max(water_level, 邻居自身高度)
   • 若邻居自身高度 >= water_level，水流不过来，邻居水位就是自身高度
   • 若邻居自身高度 < water_level，水会漫过来淹没它，邻居水位等于 water_level
5. 将邻居加入堆，标记已访问

这个过程保证了每个格子被确定水位时，用的是”最优路径”——即从边界到它的所有路径中，瓶颈最小的那条。

第三步：判断哪些格子被淹没

处理完所有格子后，如果某格子的水位 > 自身高度，说明它被水覆盖了。将所有被淹没的格子标记出来。

第四步：BFS 统计连通分量

对所有被淹没的格子做连通分量计数：遍历矩阵，遇到未统计的被淹格子就启动一次 BFS/DFS，将相邻的被淹格子归为同一个水池。最终连通分量的数量即为独立水池数。

第五步：验证样例

2 3 5 1
4 1 2 3
1 5 4 2
1 2 2 2

边界格子：第一行、最后一行、第一列、最后一列的所有格子。

从边界向内扩展后，内部格子 (1,1) 高度为 1，周围边界最低为 2（来自左边的格子 (1,0)=4 或上方 (0,1)=3 等路径）。经过堆 BFS 确定后，(1,1) 的水位 = 2（由周围路径的最小瓶颈决定），自身高度 1 < 2，被淹没。

格子 (1,2) 高度为 2，水位也为 2（或恰好等于自身），不被淹没。

经过完整计算，只有 (1,1) 被淹没（水位 2 > 自身高度 1），构成 1 个独立水池。输出 1。

题解代码

import sys
import heapq
from collections import deque
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    grid = []
    for _ in range(n):
        grid.append(list(map(int, input().split())))

    # Step 1: 最小堆 BFS 确定每个格子的水位
    water = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    heap = []

    # 将边界格子加入堆
    for i in range(n):
        for j in range(m):
            if i == 0 or i == n - 1 or j == 0 or j == m - 1:
                heapq.heappush(heap, (grid[i][j], i, j))
                visited[i][j] = True
                water[i][j] = grid[i][j]

    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while heap:
        wl, x, y = heapq.heappop(heap)
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                visited[nx][ny] = True
                # 邻居水位 = max(当前水位, 邻居自身高度)
                water[nx][ny] = max(wl, grid[nx][ny])
                heapq.heappush(heap, (water[nx][ny], nx, ny))

    # Step 2: 标记被淹没的格子
    flooded = [[False] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if water[i][j] > grid[i][j]:
                flooded[i][j] = True

    # Step 3: BFS 统计连通分量数
    count = 0
    for i in range(n):
        for j in range(m):
            if flooded[i][j]:
                count += 1
                # BFS 标记整个连通分量
                queue = deque()
                queue.append((i, j))
                flooded[i][j] = False
                while queue:
                    cx, cy = queue.popleft()
                    for dx, dy in dirs:
                        nx, ny = cx + dx, cy + dy
                        if 0 <= nx < n and 0 <= ny < m and flooded[nx][ny]:
                            flooded[nx][ny] = False
                            queue.append((nx, ny))

    print(count)

solve()

复杂度分析

时间复杂度：O(nm log(nm))。堆 BFS 中每个格子入堆出堆各一次，每次操作 O(log(nm))；后续连通分量 BFS 为 O(nm)。 空间复杂度：O(nm)，存储水位矩阵、访问标记和堆。

小结

• 第一题是状态压缩 + 记忆化搜索的典型题，核心难点在于状态设计：用 bitmask 精确描述栈内容，dfs 返回 (方案数, 总收益) 二元组来正确分配每步 pop 的收益贡献
• 第二题状态机 DP 是面试高频题型，关键在于正确定义”前一天爬山 + 今天爬山”需消耗一次例外机会的转移关系，滚动数组优化空间
• 第三题是 Trapping Rain Water II 的经典拓展，最小堆 BFS 从边界向内确定水位是核心模板，再用 BFS 统计被淹格子的连通分量即为水池数量