大厂真题 / 美团

美团 2026-08-29 笔试真题 - 算法岗

本场考试概述

考试时间：2026 年 8 月 29 日

考试岗位：算法岗

题型：10 道选择题、1 道编程题

难度评级：中等偏难

考点分析：

选择题：栈、开放定址哈希、拉链哈希、对称二叉树、稀疏注意力、预训练目标、自监督学习、LSTM、macro-F1、单样本 t 检验。
编程题：最大公约数恒等变换、欧拉函数、约数枚举、等差数列（难度困难）。

建议策略：

哈希题按插入顺序逐项记录槽位和比较次数，不要混淆线性探测与拉链法。
macro-F1 应先分别计算每一类的 F1，再做不加权算术平均。
编程题先利用两数之差不随区间下标变化，将超长区间求和转成对固定差值约数的求和；两数相等时必须单独处理。

选择题

选择题 1：双栈出栈顺序

有两个栈 S1、S2。S1 容量为 2，S2 容量为 1。四个元素 A、B、C、D 必须从 S1 入栈；S1 满后须先出栈才能继续入栈，且 S1 的出栈元素进入 S2；S2 满则从 S2 出栈作为最终输出。最终出栈顺序为（）。

A. ABCD
B. DCBA
C. BACD
D. BCDA

答案：D

解析：A、B 先进入 S1。为放入 C，先将 B 从 S1 弹入容量为 1 的 S2，随后 B 从 S2 输出；同理，放入 D 前先输出 C。之后依次输出 D、A，故最终顺序是 BCDA。

选择题 2：稀疏注意力

下面关于稀疏注意力（Sparse Attention）的说法，错误的是（）。

A. 稀疏注意力通过限制注意力计算模式来降低计算量并节省内存
B. 稀疏注意力可能需要多层传播信息，从而削弱对长距离依赖的直接建模
C. BigBird 的随机注意力用于提升注意力图的连通性并增强信息传播能力
D. Longformer 的局部窗口注意力可以在单层内直接建模任意两个位置的全局依赖

答案：D

解析：Longformer 的局部窗口只连接邻近 token，远距离位置必须经过多层逐跳传播；其全局 token 是另一种连接机制。因此，单靠局部窗口不能在单层内直接连接任意两个位置。稀疏模式则可将标准注意力的 $O(n^2)$ 计算与存储开销显著降低。

选择题 3：线性探测哈希

将序列（8，10，9，12，15，20）散列存储到下标从 0 开始的一维数组中。散列函数为

\[H(\mathrm{key})=(2\cdot \mathrm{key})\bmod 6,\]

冲突用线性探测再散列处理，装填因子按 0.6 取表长。等概率情况下，查找成功的平均查找长度为（）。

A. 1.5
B. 2
C. $11/6$
D. $7/6$

答案：C

解析：6 个关键字、装填因子 0.6，表长取 10。虽然数组长度为 10，题设散列函数的模数明确为 6。按顺序插入时：8、10、9 的探测次数均为 1；12 从槽 0 探测至槽 1，共 2 次；15 依次探测槽 0、1、2、3，共 4 次；20 从槽 4 探测至槽 5，共 2 次。因此

\[\mathrm{ASL}_{\text{成功}}=\frac{1+1+1+2+4+2}{6}=\frac{11}{6}.\]

选择题 4：大模型预训练目标

下面关于大模型预训练目标的说法，错误的是（）。

A. BERT 使用掩码语言模型（MLM）时，会将一部分 token 随机替换为 [MASK]
B. GPT 使用自回归目标，根据当前 token 去预测它的前一个 token
C. T5 用统一的编码器—解码器结构处理文本到文本的转换任务
D. 对比学习在多模态预训练中被用来增强跨模态表示能力

答案：B

解析：GPT 根据已有前缀 $x_{<t}$ 预测下一个 token $x_t$，建模的是 $P(x_t\mid x_{<t})$，不是预测前一个 token。其余三项均正确。

选择题 5：单样本 t 检验

某券商风控部门用单样本 t 检验，检验一只债券型基金最近 30 个交易日的日均净值与理论净值 10.01 是否存在显著差异。原假设 $H_0:\mu=10.01$，备择假设 $H_1:\mu\ne 10.01$。统计软件输出如下：

One Sample t-test

data: sample
t = 0.47014, df = 29, p-value = 0.6418
alternative hypothesis: true mean is not equal to 10.01
95 percent confidence interval:
 9.995933 10.032464
sample estimates:
mean of x
 10.0142

该风控部门可以得到什么结论？

A. p 值大于 0.05，该基金的日均净值与理论净值存在显著差异
B. p 值小于 0.05，该基金的日均净值与理论净值存在显著差异
C. p 值小于 0.05，该基金的日均净值与理论净值无显著差异
D. p 值大于 0.05，该基金的日均净值与理论净值无显著差异

答案：D

解析：$p=0.6418>0.05$，在 0.05 显著性水平下不能拒绝原假设，没有足够证据认为总体均值与 10.01 不同。95% 置信区间 $[9.995933,10.032464]$ 也包含 10.01。

选择题 6：拉链法哈希

已知一组关键字为（24，32，35，40，43，8，12，11），哈希函数为

\[H(\mathrm{key})=\mathrm{key}\bmod 13,\]

采用拉链法处理冲突。等概率情况下，查找成功的平均查找长度为（）。

A. $9/8$
B. $8/7$
C. $3/2$
D. 1.0

答案：A

解析：对应槽位依次为 11、6、9、1、4、8、12、11。只有 24 与 11 冲突，二者在长度为 2 的同一条链中，成功查找所需比较次数分别为 1 和 2；其余六个关键字各比较 1 次。因此总比较次数为 $7\times 1+2=9$，平均查找长度为 $9/8$。链首插入或链尾插入只会交换冲突二者的比较次数，不影响平均值。

选择题 7：视觉自监督预训练

希望在大规模无标注图像上做视觉预训练，以增强模型对图像语义的抽象能力。下列哪类预训练任务最有助于学习图像语义？

A. 旋转预测，判断图像被旋转了多少度
B. 拼图重组，还原被打乱的图像块顺序
C. 自编码器，把输入压缩后再原样重构
D. 对比学习，拉近语义相近样本、推开语义不同样本

答案：D

解析：对比学习直接约束表示空间，使语义一致的增强视图靠近、不同样本远离，更有利于学习对低层像素变化不敏感的语义表示。旋转和拼图任务可能依赖低层线索，普通重构也更关注像素细节。

选择题 8：LSTM 激活函数

在 LSTM 单元中，遗忘门、输入门和输出门使用 Sigmoid，细胞状态更新与隐状态输出使用 tanh。这两种激活函数的主要作用分别是（）。

A. Sigmoid 在输出和状态上对数据处理，tanh 产生 0～1 之间的数作为门控
B. Sigmoid 缓解饱和度产生的梯度消失，tanh 控制信息流的方向
C. Sigmoid 控制信息流的方向，tanh 缓解饱和度产生的梯度消失
D. Sigmoid 产生 0～1 之间的值作为门控，tanh 在输出和状态上对数据处理

答案：D

解析：Sigmoid 的值域为 $(0,1)$，适合表示门控比例；tanh 的值域为 $(-1,1)$ 且以 0 为中心，用于生成候选状态和隐状态输出。LSTM 缓解长程梯度问题主要依靠细胞状态的加性路径，而不是某个激活函数单独完成。

选择题 9：macro-F1

有 9 个样本，其真实类别分别为 A,A,A,A,B,B,B,C,C，模型预测结果为 A,A,B,C,B,B,C,B,C。该模型本次预测结果的 macro-F1-Score 约为（）。

A. 0.5560
B. 0.5670
C. 0.5460
D. 0.5720

答案：C

解析：逐类按“一对其余”统计：

A 类：$TP=2,FP=0,FN=2$，故 $P_A=1,R_A=1/2,F1_A=2/3\approx0.6667$。
B 类：$TP=2,FP=2,FN=1$，故 $P_B=1/2,R_B=2/3,F1_B=4/7\approx0.5714$。
C 类：$TP=1,FP=2,FN=1$，故 $P_C=1/3,R_C=1/2,F1_C=2/5=0.4$。

所以

\[\mathrm{macro\text{-}F1}=\frac{2/3+4/7+2/5}{3}=\frac{172}{315}\approx0.5460.\]

选择题 10：对称二叉树遍历

已知一棵对称二叉树，其左子树的先序遍历序列（不含根节点）为 BCDEFG，右子树的中序遍历序列（不含根节点）为 EGFDBC，根节点为 A，则该二叉树的后序遍历序列为（）。

A. CGFEDBGFEDCBA
B. BCDEFGGFEDBCA
C. CFGEDBGFEDBCA
D. CBDEFGGFEDBCA

答案：A

解析：右子树是左子树的镜像，镜像会反转中序序列，所以左子树中序为 EGFDBC 的逆序 CBDFGE。由左子树先序 BCDEFG 和中序 CBDFGE 可还原左子树，其后序为 CGFEDB。镜像树的后序等于原树先序的逆序，因此右子树后序为 GFEDCB。最后加根 A，得到 CGFEDBGFEDCBA。

第 1 题：公约数区间和

题目描述

给定四个整数 $a,b,l,r$，定义

\[f(i)=\gcd(a+i,b+i),\]

其中 $\gcd$ 表示最大公约数。计算

\[\sum_{i=l}^{r}\gcd(a+i,b+i)\]

并将答案对 $10^9+7$ 取模后输出。

输入描述

每个测试文件包含多组测试数据。

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

接下来 $T$ 行，每行输入四个整数 $a,b,l,r$，满足：

\[1\le a,b\le10^5,\qquad 0\le l\le r\le10^{18}.\]

输出描述

对每组测试数据输出一行一个整数，表示上述区间和对 $10^9+7$ 取模后的结果。

样例 1

输入

输出

样例解释：四组分别为

$\gcd(10,12)+\gcd(11,13)+\gcd(12,14)+\gcd(13,15)=2+1+2+1=6$；
$\gcd(5,10)+\gcd(6,11)+\gcd(7,12)=5+1+1=7$；
$\gcd(2,8)+\gcd(3,9)+\gcd(4,10)=2+3+2=7$；
$\gcd(11,25)+\gcd(12,26)+\gcd(13,27)+\gcd(14,28)=1+2+1+14=18$。

样例 2

输入

2
7 7 3 5
100000 1 0 1000000000000000000

输出

33
602733043

样例解释：第一组中 $a=b$，三项为 10、11、12，和为 33。第二组共有 $10^{18}+1$ 项，不能逐项枚举。

思路分析

第一步：固定最大公约数的一个参数

利用辗转相减性质：

\[\gcd(a+i,b+i)=\gcd(a+i,b-a).\]

当 $a\ne b$ 时，令 $D=\lvert b-a\rvert$、$x=a+i$，原问题变为

\[\sum_{x=a+l}^{a+r}\gcd(x,D).\]

此时 $D\le10^5$，而且不再随 $x$ 变化。虽然区间仍可能很长，但只需研究固定整数 $D$ 的约数。

第二步：用欧拉函数展开 gcd

欧拉函数满足恒等式

\[\sum_{d\mid n}\varphi(d)=n.\]

令 $n=\gcd(x,D)$，得到

\[\gcd(x,D)=\sum_{d\mid\gcd(x,D)}\varphi(d).\]

条件 $d\mid\gcd(x,D)$ 等价于 $d$ 同时整除 $x$ 和 $D$。交换求和次序后，前缀和为

\[F(N)=\sum_{x=1}^{N}\gcd(x,D) =\sum_{d\mid D}\varphi(d)\left\lfloor\frac{N}{d}\right\rfloor.\]

所以区间答案为

\[F(a+r)-F(a+l-1) =\sum_{d\mid D}\varphi(d) \left( \left\lfloor\frac{a+r}{d}\right\rfloor- \left\lfloor\frac{a+l-1}{d}\right\rfloor \right).\]

通过试除到 $\sqrt D$，可以成对枚举 $D$ 的所有约数；完全平方数的平方根只能计算一次。所有询问共用一张预处理至 $10^5$ 的欧拉函数表。

第三步：单独处理 $a=b$

此时 $D=0$，不能枚举 0 的约数，但有

\[\gcd(a+i,a+i)=a+i.\]

答案退化为等差数列和：

\[\frac{(a+l+a+r)(r-l+1)}{2}.\]

模意义下除以 2 应乘 $2$ 关于 $10^9+7$ 的逆元 $(10^9+8)/2$。

正确性证明

下面证明算法对每组数据均输出正确答案。

情形一：$a\ne b$。 由最大公约数的性质，任意 $i\in[l,r]$ 均有

\[\gcd(a+i,b+i)=\gcd(a+i,(b+i)-(a+i))=\gcd(a+i,D).\]

对每个 $x=a+i$，欧拉函数恒等式保证

\[\gcd(x,D)=\sum_{d\mid\gcd(x,D)}\varphi(d).\]

某个 $D$ 的约数 $d$ 出现在上式中，当且仅当 $d\mid x$。区间 $[a+l,a+r]$ 中 $d$ 的倍数个数恰为

\[\left\lfloor\frac{a+r}{d}\right\rfloor- \left\lfloor\frac{a+l-1}{d}\right\rfloor.\]

因此，算法对每个 $d\mid D$ 累加“$\varphi(d)$ 乘以区间内 $d$ 的倍数个数”，恰好将每一项 $\gcd(x,D)$ 的欧拉函数展开全部计入且只计一次，所得总和等于题目要求的区间和。

情形二：$a=b$。 对每个 $i$，$\gcd(a+i,a+i)=a+i$。这些项构成首项 $a+l$、末项 $a+r$、项数 $r-l+1$ 的等差数列，算法使用的公式正是该数列之和。

两种情形覆盖全部输入，故算法正确。

题解代码

import sys

input = sys.stdin.readline

MOD = 1_000_000_007
MAX_VALUE = 100_000
INV_TWO = (MOD + 1) // 2


def build_totients(limit):
    phi = list(range(limit + 1))
    for prime in range(2, limit + 1):
        if phi[prime] == prime:
            for multiple in range(prime, limit + 1, prime):
                phi[multiple] = phi[multiple] // prime * (prime - 1)
    return phi


def gcd_range_sum(phi, difference, left, right):
    answer = 0
    divisor = 1
    while divisor * divisor <= difference:
        if difference % divisor == 0:
            count = right // divisor - (left - 1) // divisor
            answer = (answer + phi[divisor] * (count % MOD)) % MOD

            paired = difference // divisor
            if paired != divisor:
                count = right // paired - (left - 1) // paired
                answer = (answer + phi[paired] * (count % MOD)) % MOD
        divisor += 1
    return answer


def solve():
    phi = build_totients(MAX_VALUE)
    test_cases = int(input())
    answers = []

    for _ in range(test_cases):
        a, b, left_index, right_index = map(int, input().split())

        if a == b:
            count = (right_index - left_index + 1) % MOD
            endpoints = ((a + left_index) % MOD + (a + right_index) % MOD) % MOD
            answer = count * endpoints % MOD * INV_TWO % MOD
        else:
            difference = abs(b - a)
            left_value = a + left_index
            right_value = a + right_index
            answer = gcd_range_sum(phi, difference, left_value, right_value)

        answers.append(str(answer))

    print("\n".join(answers))


if __name__ == "__main__":
    solve()

复杂度分析

设 $A=10^5$。

时间复杂度：预处理欧拉函数表需要 $O(A\log\log A)$；每组询问需要 $O(\sqrt{\lvert b-a\rvert})$，当 $a=b$ 时为 $O(1)$。因此总时间复杂度为 $O(A\log\log A+T\sqrt A)$。

空间复杂度：$O(A)$，用于存储欧拉函数表。

易错点

$a=b$ 时差值为 0，不能沿用约数枚举，必须改用等差数列求和。
枚举成对约数时，若 $D$ 是完全平方数，$\sqrt D$ 只能贡献一次。
区间内 $d$ 的倍数个数是 $\lfloor R/d\rfloor-\lfloor(L-1)/d\rfloor$，注意左端点偏移。
$r$ 可达 $10^{18}$。Python 整数不会溢出，但贡献仍应及时取模；在定长整数语言中尤其要防止乘法溢出。
复杂度中的差值必须使用 $\lvert b-a\rvert$；公式中不使用裸竖线，以免与 Markdown 表格语法冲突。

小结

选择题覆盖数据结构、深度学习、大模型、统计检验与分类评价指标，计算题的关键是严格按定义逐步统计。
编程题通过 $\gcd(a+i,b+i)=\gcd(a+i,b-a)$ 固定差值，再用 $\sum_{d\mid n}\varphi(d)=n$ 交换求和次序，将最多 $10^{18}+1$ 项的区间求和压缩为对一个不超过 $10^5$ 的整数枚举约数。
对 $a=b$ 的退化情形单独使用等差数列，是完整解法不可缺少的边界处理。

这篇文章有帮助吗？

| GitHub 留言