大厂真题 / 得物

得物 2026-08-29 笔试真题 - 算法岗 B 卷

本场考试概述

考试时间：2026 年 8 月 29 日

考试岗位：算法岗 B 卷

难度评级：简单偏中等

考点分析：

第一题：模拟、线性扫描（难度简单）
第二题：计数动态规划、预处理（难度中等）

建议策略：

第一题每个拨打电话的位置互不影响，读清改道规则后直接计算时间差。
第二题只需记录末尾连续相同字符的个数，状态数恒为 3。
第二题有多组询问，应读完询问后预处理到最大字符串长度，再逐项查表。

第 1 题：外卖下楼等待时长

题目描述

外卖员原计划依次经过 $n$ 个建筑，第 $n$ 个建筑是用户的宿舍楼。第 $1,2,\ldots,n$ 个建筑到宿舍楼的距离依次为

\[d_1,d_2,\ldots,d_{n-2},d_{n-1},0。\]

由于外卖员还有其他送餐任务，数组 $d$ 不一定单调递减。

假设外卖员在到达第 $i$ 个建筑时拨打电话，其中 $1\le i\le n$。外卖员会在挂断电话后才出发；如果此时还未到宿舍楼，就把下一个目的地改为宿舍楼，因此还需行进 $d_i$ 个单位距离。

外卖员行进 1 个单位距离恰好需要 1 个单位时间。用户会在挂断电话后的 $m$ 个单位时间到达楼下。求外卖员分别在每个建筑拨打电话时，用户到达楼下后还需等待多久。

输入描述

第一行输入正整数 $T$，表示测试数据组数，满足 $1\le T\le 1000$。

每组测试数据包含两行：

第一行输入两个整数 $n,m$，分别表示建筑数量和用户挂断电话后到达楼下所需的时间，满足 $1\le n\le 10^5$、$0\le m\le 10^9$。
第二行输入 $n$ 个整数 $d_1,d_2,\ldots,d_n$。对于前 $n-1$ 个建筑，满足 $1\le d_i\le 10^9$；第 $n$ 个建筑是宿舍楼，因此 $d_n=0$。

所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

输出描述

对于每组测试数据，输出一行 $n$ 个整数。第 $i$ 个整数表示外卖员在第 $i$ 个建筑拨打电话时，用户到达楼下后还需等待的时长。如果外卖已先到或双方同时到达，等待时长记为 0。

样例

输入

输出

9 6 0
0 3 0

样例解释：

第一组中，用户挂断电话后立即到达楼下，所以各位置的等待时间就是对应的 $d_i$，依次为 9、6、0。
第二组中，用户需要 6 个单位时间到达楼下。在三个建筑拨打电话时，外卖分别还需 6、9、0 个单位时间，因此等待时间依次为 0、3、0。

思路分析

第一步：确定双方的到达时刻

外卖员在第 $i$ 个建筑挂断电话后直接前往宿舍楼，距离为 $d_i$，速度条件说明其到达耗时也是 $d_i$。用户到达楼下的耗时固定为 $m$。

第二步：计算等待时间

只有外卖员比用户晚到时，用户才需要等待。两者的到达时刻之差为 $d_i-m$，所以第 $i$ 个答案为

\[\max(0,d_i-m)。\]

电话一旦挂断，外卖员便从当前建筑直接改道，原计划中的后续建筑不再影响本次结果。因此每个位置可以独立计算，数组是否单调也不会影响答案。

正确性证明

对任意位置 $i$，外卖员从挂断电话到送达需要 $d_i$ 个单位时间，用户到楼下需要 $m$ 个单位时间。

若 $d_i\le m$，外卖不晚于用户到达，用户无需等待，算法输出 0。
若 $d_i>m$，用户先到达，必须等待到第 $d_i$ 个单位时间，等待时长恰为 $d_i-m$，算法也输出该值。

两种情况覆盖所有可能性，因此算法对每个位置都给出正确答案，最终输出的整行答案正确。

题解代码

import sys

input = sys.stdin.readline


def solve():
    test_cases = int(input())
    output = []

    for _ in range(test_cases):
        n, m = map(int, input().split())
        distances = list(map(int, input().split()))
        waits = [max(0, distance - m) for distance in distances]
        output.append(" ".join(map(str, waits)))

    sys.stdout.write("\n".join(output))


solve()

复杂度分析

设所有测试数据的建筑数之和为 $S$。

时间复杂度：$O(S)$。每个距离只处理一次。

空间复杂度：$O(S)$。代码缓存全部输出；除输出外，单组计算使用 $O(n)$ 空间存储输入和答案。

易错点

外卖员挂断电话后会从当前建筑直接前往宿舍楼，不需要考虑原路线中的后续建筑。
等待时间不能为负数，必须取 $\max(0,d_i-m)$。
当 $d_i=m$ 时双方同时到达，答案是 0。
第 $n$ 个建筑就是宿舍楼，$d_n=0$，对应答案恒为 0。
多组数据的总规模较大，应使用缓冲输入输出。

第 2 题：密码强度字符串计数

题目描述

构造一个长度为 $n$、仅含小写英文字母的字符串。字符串中不能出现超过三个连续相同的字符，也就是不能包含四个连续相同字符。例如，aaaa、bbbb 不符合要求，而 aaabaaa 符合要求。

求满足条件的字符串数量，并对 $10^9+7$ 取模后输出。

输入描述

第一行输入整数 $T$，表示测试数据组数，满足 $1\le T\le 2\times 10^5$。

接下来 $T$ 行，每行输入一个整数 $n$，表示字符串长度，满足 $1\le n\le 2\times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示满足条件的字符串数量对 $10^9+7$ 取模后的结果。

样例

输入

2
2
4

输出

676
456950

样例解释：

当 $n=2$ 时，所有字符串都符合要求，答案为 $26\times 26=676$。
当 $n=4$ 时，总共有 $26^4$ 个字符串。不合法的字符串只有 aaaa、bbbb、……、zzzz 这 26 个，因此答案为 $26^4-26=456950$。

思路分析

第一步：寻找决定后续转移的信息

向一个合法字符串末尾添加字符时，能否继续保持合法，只与当前末尾连续相同字符的长度有关。该长度只能是 1、2、3，因此无需保存整个字符串。

定义 $f_{i,j}$ 表示长度为 $i$，且末尾恰有 $j$ 个连续相同字符的合法字符串数量，其中 $j\in{1,2,3}$。

长度为 1 时：

\[f_{1,1}=26,\qquad f_{1,2}=f_{1,3}=0。\]

第二步：分类讨论新字符

从长度 $i-1$ 扩展到长度 $i$：

如果新字符与原末尾字符不同，共有 25 种选择，新的连续段长度变为 1：
\[f_{i,1}=25\cdot(f_{i-1,1}+f_{i-1,2}+f_{i-1,3})。\]
如果新字符与原末尾字符相同，选择唯一，连续段长度增加 1：
\[f_{i,2}=f_{i-1,1},\qquad f_{i,3}=f_{i-1,2}。\]
原末尾长度为 3 时不能再添加相同字符，否则会产生四个连续相同字符。

长度为 $i$ 的答案为

\[ans_i=f_{i,1}+f_{i,2}+f_{i,3}。\]

所有计算都需要对 $10^9+7$ 取模。

第三步：一次预处理回答多次询问

先读入全部 $n$，找到最大值 $n_{\max}$。使用三个滚动变量维护当前三种状态，并保存每个长度的总答案。这样只需递推一次，之后每个询问都能直接查表。

正确性证明

使用数学归纳法证明：对每个 $i\ge 1$ 和 $j\in{1,2,3}$，算法计算的 $f_{i,j}$ 恰为长度为 $i$、末尾连续相同字符数量恰为 $j$ 的合法字符串数。

基础情形：当 $i=1$ 时，可以选择任意一个小写字母，共 26 种，且末尾连续段长度只能为 1。因此 $f_{1,1}=26$、$f_{1,2}=f_{1,3}=0$ 正确。

归纳步骤：假设长度为 $i-1$ 时各状态均正确。

末尾连续段长度为 1 的字符串，必然由任意长度为 $i-1$ 的合法字符串添加一个不同于原末尾的字符得到。每个原字符串恰有 25 种选择，所以转移到 $f_{i,1}$ 的计数既无遗漏也无重复。
末尾连续段长度为 2 的字符串，删去最后一个字符后，其末尾连续段长度必为 1；反之，在该字符串末尾添加相同字符会唯一得到前者。因此 $f_{i,2}=f_{i-1,1}$。
同理，末尾连续段长度为 3 的字符串与长度为 $i-1$、末尾连续段长度为 2 的字符串一一对应，因此 $f_{i,3}=f_{i-1,2}$。
不从长度为 3 的末尾状态继续添加相同字符，恰好排除了所有新产生四连相同字符的情况。

所以长度为 $i$ 的三个状态均正确。它们互斥并覆盖所有合法字符串，故三者之和就是长度为 $i$ 的合法字符串总数。归纳完成，算法正确。

题解代码

import sys

input = sys.stdin.readline
MOD = 10**9 + 7


def solve():
    test_cases = int(input())
    lengths = [int(input()) for _ in range(test_cases)]
    max_length = max(lengths)

    answers = [0] * (max_length + 1)
    end_one, end_two, end_three = 26, 0, 0
    answers[1] = 26

    for length in range(2, max_length + 1):
        total = (end_one + end_two + end_three) % MOD
        end_one, end_two, end_three = (
            total * 25 % MOD,
            end_one,
            end_two,
        )
        answers[length] = (end_one + end_two + end_three) % MOD

    sys.stdout.write("\n".join(str(answers[length]) for length in lengths))


solve()

复杂度分析

设询问中的最大字符串长度为 $n_{\max}$。

时间复杂度：$O(n_{\max}+T)$。预处理每个长度一次，每次询问为 $O(1)$ 查表。

空间复杂度：$O(n_{\max}+T)$。答案表占 $O(n_{\max})$，询问和输出占 $O(T)$；DP 状态本身仅占 $O(1)$。

易错点

“不能超过三个连续一样”表示允许连续 1、2、3 个相同字符，但禁止连续 4 个。
添加不同字符时不是 26 种选择，而是排除当前末尾字符后的 25 种。
从末尾连续长度为 3 的状态不能再添加相同字符。
递推和答案求和都要对 $10^9+7$ 取模。
$T$ 和 $n$ 都可达到 $2\times 10^5$，不能为每个询问重新执行一遍 DP。

小结

第一题将故事规则转化为两个到达时刻之差，对每个位置计算 $\max(0,d_i-m)$。
第二题利用“后续合法性只由末尾连续段长度决定”的性质，设计三个状态并一次预处理全部答案。

这篇文章有帮助吗？

| GitHub 留言