大厂真题 / 滴滴

滴滴 2026-8-23 笔试真题 - 通用岗

本场考试概述

考试时间：2026 年 8 月 23 日

考试岗位：通用岗

难度评级：中等偏难

考点分析：

• 第 1 题：二维前缀和、长度受限的最大子段和、矩阵转置（中等）
• 第 2 题：值域压缩、离线倒推 DP、前缀和与二分查找（困难）

建议策略：

• 第 1 题先证明播种机最少运行次数为矩形高宽的较小值，再按高不大于宽、宽不大于高拆成两个对称方向。
• 第 2 题重点利用每个人的财富值、回馈和施舍金额都不超过 500，将大量询问共享到同一份小值域 DP 中。
• 两题都需要 64 位整数思维；Python 整数不会溢出，但 NumPy 数组必须使用 int64。

第 1 题：农田播种

题目描述

一块农田由 $n$ 行 $m$ 列地块组成，第 $i$ 行第 $j$ 列的土壤肥力为 $w_{i,j}$。

播种机每次可以从任意格子出发，沿一行或一列直线运行，到任意格子结束。现在需要选择一个非空连续子矩形进行播种。若矩形内所有肥力之和为 $S$，覆盖该矩形所需的最少运行次数为 $k$，则满意度为 $S\times k$。

求所有非空连续子矩形中的最大满意度。

输入描述

第一行输入两个正整数 $n,m$，表示农田大小，满足 $1\le n,m\le400$。

接下来 $n$ 行，每行输入 $m$ 个整数，其中 $-1000\le w_{i,j}\le1000$。

输出描述

输出一个整数，表示最大满意度。

样例

输入

3 4
-5 3 4 -1
-1 9 0 2
-2 -6 -5 -2

输出

34

解释

选择左上角为第 1 行第 2 列、右下角为第 2 行第 4 列的矩形。肥力之和为 $17$，矩形高为 $2$、宽为 $3$，最少运行 $2$ 次，满意度为 $17\times2=34$。

思路分析

第一步：确定最少运行次数

设所选矩形高为 $h$、宽为 $w$。逐行覆盖需要 $h$ 次，逐列覆盖需要 $w$ 次，因此至多需要 $\min(h,w)$ 次。

这个上界也是下界。若运行次数同时少于 $h$ 和 $w$，就至少存在一行没有被横向覆盖、一列没有被纵向覆盖，它们的交点必然漏播。因此

第二步：拆成两个对称方向

先只计算 $h\le w$ 的矩形，此时 $k=h$。固定高度 $h$ 后，乘数已经确定，只需要寻找宽度不少于 $h$、元素和最大的矩形。

$w\le h$ 的情况可以把矩阵转置后运行同一套算法。正方形会被计算两次，但不会影响最大值。

第三步：把二维矩形压成一维区间

固定高度 $h$ 和上边界 top，把这 $h$ 行按列求和，得到数组 $c$。选择一个宽度不少于 $h$ 的矩形，等价于在 $c$ 中选择一个长度不少于 $h$ 的连续子数组。

令前缀和为 $P$。区间 $(l,r]$ 的和是 $P_r-P_l$，长度限制是 $r-l\ge h$。对固定右端点 $r$，最优左端点就是合法范围 $0\le l\le r-h$ 中前缀和最小的位置：

从左到右扫描并维护这个前缀最小值，即可在线性时间内完成当前横条的计算。

第四步：实现优化

使用逐列前缀和，可以一次减法得到固定高度下所有上边界对应的列和。NumPy 再沿列方向批量计算前缀和与累积最小值，避免在 Python 层执行最重的三重循环。

答案可能达到 $400\times400\times1000\times400=6.4\times10^{10}$，所以 NumPy 数组必须使用 int64。

正确性证明

引理 1：高为 $h$、宽为 $w$ 的矩形最少需要 $\min(h,w)$ 次运行。

证明：逐行或逐列覆盖分别给出 $h$ 次和 $w$ 次的方案。若少于两者的较小值，则既有未横向覆盖的行，也有未纵向覆盖的列，两者交点无法被覆盖，矛盾。因此最少次数恰为 $\min(h,w)$。

引理 2：固定高度 $h$ 和上边界后，算法找到所有宽度不少于 $h$ 的子矩形中的最大元素和。

证明：每个候选矩形唯一对应列和数组中的一个长度不少于 $h$ 的连续区间。对每个右端点，算法从全部合法左端点中选择前缀和最小者，因此得到以该右端点结束的最大区间和；遍历所有右端点即可覆盖全部候选区间。

引理 3：两个方向的计算覆盖所有非空子矩形。

证明：任意矩形必满足 $h\le w$ 或 $w\le h$。前者由原矩阵计算，后者在矩阵转置后变成高不大于宽的情况，因此所有矩形均被覆盖。

定理：算法输出最大满意度。

证明：由引理 1，算法使用的乘数等于真实最少运行次数；由引理 2，每个固定高度和上边界下都取得最优元素和；由引理 3，全部候选矩形均被枚举。因此最终最大值就是题目要求的最大满意度。

ACM Python 代码

import sys

import numpy as np


def best_for_orientation(matrix):
    n, m = matrix.shape
    row_prefix = np.zeros((n + 1, m), dtype=np.int64)
    np.cumsum(matrix, axis=0, out=row_prefix[1:])

    answer = None
    for height in range(1, min(n, m) + 1):
        column_sums = row_prefix[height:] - row_prefix[: n - height + 1]

        prefix = np.zeros((column_sums.shape[0], m + 1), dtype=np.int64)
        np.cumsum(column_sums, axis=1, out=prefix[:, 1:])

        prefix_min = np.minimum.accumulate(
            prefix[:, : m - height + 1], axis=1
        )
        best_sum = int((prefix[:, height:] - prefix_min).max())
        score = best_sum * height
        if answer is None or score > answer:
            answer = score

    return answer


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m = data[0], data[1]
    matrix = np.asarray(data[2:], dtype=np.int64).reshape(n, m)

    answer = max(
        best_for_orientation(matrix),
        best_for_orientation(matrix.T),
    )
    print(answer)


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度为 $O(n^2m+nm^2)$，两个方向分别枚举高度与上边界，并对每个横条执行线性向量运算。

空间复杂度为 $O(nm)$，用于保存矩阵、逐列前缀和和当前批次的前缀数组。

易错点

• 最少运行次数不是面积，也不是固定按行或按列覆盖，而是高宽的较小值。
• 子矩形不能为空；即使所有肥力都是负数，也必须选择至少一个格子。
• 长度限制是“宽度不少于高度”，维护前缀最小值时只能加入下标不超过 $r-h$ 的位置。
• NumPy 默认类型不能依赖平台推断，应显式指定 np.int64。

第 2 题：侠客行

题目描述

一名侠客将依次遇到 $N$ 个人。第 $i$ 个人有三个参数：财富值 $W_i$、感激回馈 $A_i$ 和施舍金额 $B_i$。

侠客遇到第 $i$ 个人时：

• 若 $W_i$ 小于侠客当前的钱，即侠客的钱严格大于 $W_i$，侠客施舍 $B_i$；若钱不足 $B_i$，则把钱全部给出，余额变为 $0$。
• 若 $W_i$ 大于等于侠客当前的钱，对方赠送侠客 $A_i$，余额增加 $A_i$。

共有 $Q$ 个询问。每个询问给出初始金额 $X_j$，求侠客按顺序遇完所有人后的余额。

输入描述

第一行输入整数 $N$，满足 $1\le N\le10000$。

接下来 $N$ 行，每行输入 $W_i,A_i,B_i$，满足

随后输入整数 $Q$，满足 $1\le Q\le10^5$。

接下来 $Q$ 行，每行输入一个初始金额 $X_j$，满足 $0\le X_j\le10^9$。

输出描述

对每个询问输出一行，表示最终余额。

样例

输入

3
10 5 3
20 8 4
15 6 2
5
0
5
10
15
20

输出

19
16
21
18
23

解释

以初始金额 $10$ 为例：遇到第一个人时 $10\le10$，收到 $5$ 后变成 $15$；遇到第二个人时 $15\le20$，收到 $8$ 后变成 $23$；遇到第三个人时 $23>15$，施舍 $2$ 后变成 $21$。

思路分析

逐个询问模拟需要 $O(NQ)$ 次状态转移，最坏达到 $10^9$ 次，无法通过。关键是规则参数的值域很小。

第一步：找到封闭的小值域

当余额不超过 $500$ 时，如果进入收礼分支，最多增加 $500$，所以新余额不超过 $1000$；如果进入施舍分支，余额只会减少。

当余额位于 $[0,1000]$ 时，经过任意一个人后仍在该区间内。因此令 LIMIT = 1000，这是一个封闭值域，只有 $1001$ 个状态。

第二步：让大额询问快速落入小值域

若当前余额大于 LIMIT，它必然大于所有 $W_i$，所以只会连续进入施舍分支。又因为此时余额大于 $1000$、而 $B_i\le500$，减法不会触发截断到零。

定义施舍金额前缀和

对初始金额 $X$，二分寻找最小的 $k$，使得

前 $k$ 个人可以一次性跳过，余额落到 $X-P_k$。若遍历完所有人仍大于 $1000$，则全程只会施舍，答案直接是 $X-P_N$。

第三步：对小值域做倒推 DP

定义 $f_i[v]$ 表示从第 $i$ 个人开始、当前有 $v$ 元，遇完剩余所有人后的余额。边界为

第 $i$ 个人对余额的单步转移为

于是

从后向前计算，每层只处理 $1001$ 个状态，并使用滚动数组保存当前层。

第四步：按落点位置给询问分桶

一个大额询问二分后会在第 $k$ 个人处理完时落入小值域，后续应从第 $k+1$ 个人开始。将它放入 bucket[k]。倒推 DP 得到对应后缀时，立即用落地余额查表回答该桶内所有询问。

这样，所有询问只共享一趟倒推，而不是分别模拟完整流程。

正确性证明

引理 1：区间 $[0,1000]$ 在任意单步转移后保持封闭。

证明：进入施舍分支时余额不增且不会低于 $0$；进入收礼分支时必有 $v\le W_i\le500$，且 $A_i\le500$，所以 $v+A_i\le1000$。因此转移结果仍在该区间内。

引理 2：二分跳过的前 $k$ 个人均进入施舍分支，且落地余额计算正确。

证明：由 $k$ 的最小性，对任意 $i<k$ 都有 $X-P_i>1000\ge W_{i+1}$，所以第 $i+1$ 个人必然触发施舍。此时余额大于 $1000$ 且 $B_{i+1}\le500$，不会出现余额不足而截断为零，因此连续减去这些 $B$ 后余额恰为 $X-P_k$。

引理 3：倒推数组 $f_i$ 正确表示从第 $i$ 个人开始的最终余额。

证明：边界 $f_{N+1}[v]=v$ 显然成立。若 $f_{i+1}$ 正确，遇到第 $i$ 个人后余额变为 $t_i(v)$，随后结果为 $f_{i+1}[t_i(v)]$，正是转移式。由逆向归纳，所有 $f_i$ 都正确。

定理：算法对每个询问输出正确的最终余额。

证明：若询问始终未落入小值域，引理 2 说明全程余额为 $X-P_N$。否则，引理 2 给出正确的落点与落地余额，引理 1 保证后续状态始终在 DP 值域内，引理 3 保证对应后缀查表结果正确。因此所有询问答案均正确。

ACM Python 代码

import sys
from bisect import bisect_left


LIMIT = 1000


def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    iterator = iter(data)

    n = next(iterator)
    people = [(next(iterator), next(iterator), next(iterator)) for _ in range(n)]
    q = next(iterator)
    queries = [next(iterator) for _ in range(q)]

    prefix_b = [0] * (n + 1)
    for i, (_, _, give) in enumerate(people):
        prefix_b[i + 1] = prefix_b[i] + give

    answers = [0] * q
    landing = [0] * q
    buckets = [[] for _ in range(n + 1)]

    for query_id, money in enumerate(queries):
        position = bisect_left(prefix_b, money - LIMIT)
        if position > n:
            answers[query_id] = money - prefix_b[n]
        else:
            landing[query_id] = money - prefix_b[position]
            buckets[position].append(query_id)

    dp = list(range(LIMIT + 1))
    for query_id in buckets[n]:
        answers[query_id] = dp[landing[query_id]]

    for i in range(n - 1, -1, -1):
        wealth, reward, give = people[i]
        next_dp = [0] * (LIMIT + 1)
        for money in range(LIMIT + 1):
            if money <= wealth:
                after = money + reward
            else:
                after = max(0, money - give)
            next_dp[money] = dp[after]
        dp = next_dp

        for query_id in buckets[i]:
            answers[query_id] = dp[landing[query_id]]

    print("\n".join(map(str, answers)))


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度为 $O(N\cdot1001+Q\log N)$，其中倒推 DP 处理固定小值域，每个询问只进行一次二分和一次查表。

空间复杂度为 $O(N+Q+1001)$，用于施舍前缀和、询问分桶、答案和滚动 DP。

易错点

• 分支条件是余额严格大于 $W_i$ 时施舍；余额等于 $W_i$ 时应收礼。
• 二分目标是第一个满足 $P_k\ge X-1000$ 的位置，bisect_left 的比较边界不能写错。
• 询问在前 $k$ 个人之后落入小值域，对应的是从第 $k+1$ 个人开始的后缀状态。
• 不能为每个询问单独模拟，也不能假设最终余额关于初始金额单调。

小结

• 第 1 题先证明覆盖次数为矩形高宽的较小值，再通过矩阵转置统一两个方向，并把二维矩形转成长度受限的最大子段和。
• 第 2 题利用参数上界构造 $[0,1000]$ 的封闭值域，大额询问先用施舍前缀和二分落点，再共享离线倒推 DP。
• 两题的共同点是先从约束和状态变化中找到可压缩的维度，再避免对每个候选或询问做完整模拟。