大厂真题 / 携程
携程 5.21 笔试真题 - 算法岗
本场考试概述
考试时间：2026年5月21日 考试岗位：算法岗 难度评级：中等
考点分析：
- 第一题：模拟（难度简单）
- 第二题：三维网格枚举（难度中等）
- 第三题：sklearn GridSearchCV + StandardScaler（难度中等）
- 第四题：中途相遇法 + 哈希计数（难度中等偏难）
建议策略：
- 第一题模拟题秒杀，注意”严格大于”对应
>而非>=，64 位整数累加 - 第二题立方体方向枚举要数清 26 个方向 + 合法起点的笛卡儿积，初值用负无穷保险
- 第三题熟悉 sklearn 管线：StandardScaler 只在训练集 fit、StratifiedKFold 保比例、GridSearchCV 字典序选优
- 第四题异或四元组的关键是把暴力按”中途相遇”拆成两组各 $O(n^2)$，配滑动分界点保证下标约束
第一题：拿石子
题目描述
有 $n$ 堆石子。你只做一次统计：对每一堆，如果这堆石子的数量严格大于 $x$，你就从这堆里拿走 $y$ 颗石子；否则这堆不拿。请计算你一共会拿走多少颗石子。
输入描述
一行输入三个整数 $n, x, y$。
接下来一行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示第 $i$ 堆的石子数量。
输出描述
输出一个整数，表示总共拿走的石子数量。
样例
输入
5 3 2
1 3 4 5 3
输出
4
样例解释：共有 5 堆，阈值为 3，每次从满足条件的堆拿 2 颗。第 3 堆数量 4 > 3 拿走 2 颗，第 4 堆数量 5 > 3 拿走 2 颗，其余三堆数量不严格大于 3 都不拿，共拿走 4 颗。
思路分析
第一步：理解条件。对每堆判断数量是否严格大于阈值 $x$，满足条件的堆各贡献 $y$ 颗石子，求总贡献。各堆独立，单次线性扫描即可。
第二步：计数累乘。扫描数组，统计满足 $a_i > x$ 的堆数 $\text{cnt}$，答案为 $\text{cnt} \times y$。
第三步：注意边界。题面强调”严格大于”，代码用 > 而非 >=，等于 $x$ 不计。Python 整数自动大数，无需关心位宽溢出。
题解代码
import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
x = int(data[1])
y = int(data[2])
a = list(map(int, data[3:3 + n]))
# 严格大于阈值才拿 y 颗（等于 x 不算）
ans = sum(y for v in a if v > x)
print(ans)
复杂度分析
时间复杂度：$O(n)$，单次线性扫描。 空间复杂度：$O(n)$，存储数组（可边读边累计降为 $O(1)$）。
第二题：立方体最大权值直线
题目描述
给出一个边长为 $n$ 的立方体网格。网格中每个小方块对应一个整数权值。你需要从立方体中选择一条长度为 $n$ 的直线。
允许选择的直线方向包括：沿坐标轴方向（分别与 x、y 或 z 轴平行的整行/整列/整柱）；沿任一坐标平面的面对角线方向（例如在 xy 平面中，每一步 x 与 y 同时加减、z 不变；其余两个平面同理）；沿空间对角线方向（每一步 x、y、z 同时加减）。
形式化地，设方向步长为 $(dx, dy, dz)$，其中各分量取自 ${-1, 0, 1}$ 且不全为零。选择方向后，起点 $(x_0, y_0, z_0)$ 需要满足：对所有 $k \in [0, n-1]$，都有 $0 \le x_0 + k \cdot dx < n$（y、z 同理），从而得到一条恰好经过 $n$ 个小方块的直线。请计算在所有允许方向与所有合法起点中，经过的小方块权值之和的最大值。
输入描述
在一行上输入一个整数 $n$，表示立方体的边长。
此后按”层”的顺序给出权值。对于第 $k$ 个”层”，输入 $n$ 行：第 $i$ 行输入 $n$ 个整数，表示第 $k$ 层第 $i$ 行第 $j$ 列小方块的权值。
输出描述
输出一个整数，表示所有允许方向与所有合法起点中，经过的小方块权值之和的最大值。
样例
输入
2
1 2
3 4
5 6
7 8
输出
15
样例解释：立方体边长 2。第 0 层的两行为 [1,2] 和 [3,4]；第 1 层的两行为 [5,6] 和 [7,8]。枚举所有方向所有合法起点，沿空间对角方向 (1,1,1) 从 (0,0,0) 出发经过格子 1 和 8，权值和为 9；从 (0,1,1) 沿 (1,-1,-1) 经过 4 和 5，和为 9。最大的直线经过 7 和 8，权值和为 15。
思路分析
第一步：方向枚举。每维取自 ${-1, 0, 1}$，三维联合后扣除全零方向共 $3^3 - 1 = 26$ 个有效方向。
第二步：合法起点判定。直线上所有 $n$ 个格子坐标都必须落在 $[0, n-1]$ 内。对 $x$ 这一维独立看：
- $dx = 0$：起点 $x_0$ 可取 $[0, n-1]$
- $dx = +1$：$x_0$ 必须为 0（否则末端 $x_0 + (n-1)$ 越界）
- $dx = -1$：$x_0$ 必须为 $n-1$（否则末端 $x_0 - (n-1)$ 越界）
三个维度合法集合做笛卡儿积，即得该方向的全部合法起点。
第三步：沿线累加取全局最大值。固定方向与起点后，沿直线累加 $n$ 个格子权值，更新全局最大值。权值可负，初值必须用负无穷而非 0，否则全负权值的直线会被屏蔽。
第四步：复杂度估算。方向数 26 为常数，起点数 $O(n^2)$，每条直线累加 $O(n)$，总复杂度 $O(n^3)$。
题解代码
import sys
def solve():
data = sys.stdin.buffer.read().split()
n = int(data[0])
# 输入按 (k, i, j) 顺序给出，重排成 a[i][j][k]
flat = list(map(int, data[1:1 + n ** 3]))
a = [[[0] * n for _ in range(n)] for _ in range(n)]
idx = 0
for k in range(n):
for i in range(n):
for j in range(n):
a[i][j][k] = flat[idx]
idx += 1
# 初值用 -inf：权值可负，全负直线不能被 0 屏蔽
ans = -10 ** 18
# 三层循环枚举方向 (dx, dy, dz)，每维 in {-1, 0, 1}，共 27 种
for dx in (-1, 0, 1):
for dy in (-1, 0, 1):
for dz in (-1, 0, 1):
# 跳过全零方向，剩 26 个有效方向
if dx == 0 and dy == 0 and dz == 0:
continue
# 合法起点范围：
# d=0 -> 起点在该维可任取 [0, n-1]
# d=+1 -> 起点必为 0（否则末端越界右侧）
# d=-1 -> 起点必为 n-1（否则末端越界左侧）
xs = range(n) if dx == 0 else ([0] if dx == 1 else [n - 1])
ys = range(n) if dy == 0 else ([0] if dy == 1 else [n - 1])
zs = range(n) if dz == 0 else ([0] if dz == 1 else [n - 1])
# 遍历该方向全部合法起点
for x0 in xs:
for y0 in ys:
for z0 in zs:
# 沿方向 k 步累加，k 从 0 到 n-1 共 n 个格子
s = 0
for k in range(n):
s += a[x0 + k * dx][y0 + k * dy][z0 + k * dz]
if s > ans:
ans = s
print(ans)
solve()
复杂度分析
时间复杂度：$O(n^3)$。方向数 26 为常数，起点数 $O(n^2)$，每条直线累加 $O(n)$。 空间复杂度：$O(n^3)$，存储立方体权值。
第三题：SVM网格搜索
题目描述
请在仅依赖 numpy / pandas / scikit-learn 的前提下，实现一个线性支持向量机（SVM）分类器，并通过 Stratified 3-Fold 交叉验证 + 网格搜索自动选择最佳惩罚系数 $C$。完成后对给定测试样本输出类别预测。
1. 读取数据
- 训练集：二维列表，最后一列为标签（0/1），前 $m$ 列为数值特征。
- 测试集：二维列表，仅包含特征（与训练集同维度）。
2. 建模管线
- 预处理：StandardScaler（仅在训练集 fit，再 transform）。
- 基础模型使用 SVC，参数固定值：
kernel='linear'，random_state=42。 - 网格：
Cin[0.1, 1.0, 10.0]。 - Stratified 3-Fold 交叉验证参数固定值：
n_splits=3，shuffle=True，random_state=42。 - 评估指标：
accuracy。 - 使用 GridSearchCV 组合以上要素；当多组参数获得相同最高分时，GridSearchCV 会按参数字典序选择最先出现的那组（即较小的 $C$ 值）。
3. 模型训练与预测
在完整训练集上用最佳参数 $C$ 重新训练；对测试集直接预测得到标签序列。
4. 结果输出
仅输出测试部分的预测标签（0 / 1）。
输入描述
第一行输入两个整数 $n, m$，分别表示训练样本数和特征维度。
接下来 $n$ 行，每行包含 $m+1$ 个浮点数，前 $m$ 个为特征，最后一个为整数标签（0/1）。
接下来一行输入一个整数 $q$，表示测试样本数。
接下来 $q$ 行，每行包含 $m$ 个浮点数，表示一个测试样本的特征。
输出描述
输出 $q$ 行，每行一个整数（0 或 1），表示对应测试样本的预测标签。
样例
输入
20 2
-1.20 -0.40 0
-0.80 -1.10 0
-1.30 -0.90 0
-0.70 -0.60 0
-1.50 -0.30 0
-0.90 -1.40 0
-0.50 -0.80 0
-1.10 -0.20 0
-0.60 -1.30 0
-1.40 -0.70 0
1.20 0.40 1
0.80 1.10 1
1.30 0.90 1
0.70 0.60 1
1.50 0.30 1
0.90 1.40 1
0.50 0.80 1
1.10 0.20 1
0.60 1.30 1
1.40 0.70 1
3
1.00 1.00
-1.00 -1.00
0.50 0.50
输出
1
0
1
样例解释：训练集共 20 个样本，前 10 个标签为 0 分布在第三象限，后 10 个标签为 1 分布在第一象限。经 GridSearchCV 在 [0.1, 1.0, 10.0] 中网格搜索后选出最佳 $C$，对测试集预测：第 1 个样本落在正类区域得到 1；第 2 个样本落在负类区域得到 0；第 3 个样本距离决策超平面靠近正类侧得到 1。
思路分析
第一步：特征标准化。将每维特征减均值除标准差，使各维同尺度，避免某些维度因数值大而主导决策面。仅由训练集统计均值和标准差，再 transform 测试集。若先 fit 全集再切分，测试集统计量会泄漏进训练流程，导致评估偏乐观。
第二步：线性 SVC 目标函数。在标准化特征空间求最大间隔超平面，软间隔 SVM 优化目标中超参 $C$ 平衡间隔大小与分类错误：$C$ 越大越倾向贴近训练数据，越小越倾向大间隔。
第三步：Stratified K-Fold 评分。将训练集按标签比例切成 3 折。对每个候选 $C$，依次留 1 折当验证、另 2 折当训练，得到 3 个验证准确率取均值。每折保持正负样本比例与原始一致，避免随机切分导致某折正样本过少。参数 n_splits=3, shuffle=True, random_state=42。
第四步：网格搜索选优。在候选集 [0.1, 1.0, 10.0] 中取分数最高者。GridSearchCV 按候选列表顺序遍历，平分时保留首个出现的候选（即较小的 $C$ 值）。候选必须用有序结构（list），不能用 set，否则遍历顺序未定义。
第五步：refit 全集训练。选定 $C$ 后用完整训练集重新拟合（refit=True 默认行为），最终模型对测试集预测得到标签序列。
题解代码
import sys
import numpy as np
from sklearn.svm import SVC
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import GridSearchCV, StratifiedKFold
def solve():
data = sys.stdin.read().split()
idx = 0
# 第一行：训练样本数 n、特征维度 m
n, m = int(data[idx]), int(data[idx + 1])
idx += 2
# 训练集 n 行，前 m 列为特征、最后 1 列为标签 (0 / 1)
train = []
for _ in range(n):
row = [float(v) for v in data[idx:idx + m + 1]]
train.append(row)
idx += m + 1
# 测试样本数 q
q = int(data[idx])
idx += 1
# 测试集 q 行，每行 m 个特征（无标签，待预测）
test = []
for _ in range(q):
row = [float(v) for v in data[idx:idx + m]]
test.append(row)
idx += m
# 拆分特征与标签
train = np.array(train)
X_train = train[:, :m]
y_train = train[:, m].astype(int)
X_test = np.array(test)
# 标准化：仅用训练集统计 mu, sigma，避免测试集信息泄漏
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)
# Stratified 3-Fold：每折保持原始正负样本比例
skf = StratifiedKFold(n_splits=3, shuffle=True, random_state=42)
# 网格候选：list 有序，平分时 GridSearchCV 保留首个（较小的 C）
grid = {'C': [0.1, 1.0, 10.0]}
# 线性核 SVC
svc = SVC(kernel='linear', random_state=42)
# GridSearchCV：3 个 C x 3 折 = 9 次训练
# refit=True（默认）：选好 C 后用完整训练集再训一次
gs = GridSearchCV(svc, grid, cv=skf, scoring='accuracy', refit=True)
gs.fit(X_train_scaled, y_train)
# 用 refit 后的最终模型预测测试集
preds = gs.predict(X_test_scaled)
print('\n'.join(str(int(p)) for p in preds))
solve()
复杂度分析
时间复杂度：$O(n^2 m)$，共 9 次 SVC 训练，线性核单次 $O(n^2 m)$，规模下毫秒级完成。 空间复杂度：$O(nm)$，存训练与测试矩阵。
第四题：异或四元组计数
题目描述
给定一个长度为 $n$ 的整数数组 $a$ 与整数 $k$，请统计满足 $a_i \oplus a_j \oplus a_p \oplus a_q = k$ 的四元组 $(i, j, p, q)$ 数量。为避免重复计数，约定四个下标两两不同且按 $i < j < p < q$ 计数。
名词解释
- 按位异或（xor，记作 $\oplus$）：对每一位二进制独立计算，相同为 0，不同为 1。
- 两两不同：四个下标互不相同，不可复用同一位置的元素；本题按 $i < j < p < q$ 唯一计数。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ 代表数据组数，每组测试数据描述如下：
第一行输入两个整数 $n, k$。
第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$。
所有测试中 $\sum n \le 2000$。
输出描述
输出 $T$ 行，第 $i$ 行输出第 $i$ 组数据的答案（满足条件的四元组数量）。
样例
输入
2
4 0
1 2 1 2
5 2
1 1 2 2 3
输出
1
2
样例解释：第一组数据 $n=4$，$k=0$，数组为 [1,2,1,2]。唯一可选四元组下标 (0,1,2,3)，异或和 $1 \oplus 2 \oplus 1 \oplus 2 = 0$，满足条件，答案为 1。第二组数据 $n=5$，$k=2$，数组为 [1,1,2,2,3]。满足条件的四元组下标为 (0,1,2,4) 和 (0,1,3,4)，共 2 组。
思路分析
第一步：暴力分析。朴素做法枚举所有四元组验证，复杂度 $O(n^4)$，单组 $n = 2000$ 直接超时。
第二步：中途相遇拆分。利用异或消去律，把等式 $a_i \oplus a_j \oplus a_p \oplus a_q = k$ 改写为 $a_i \oplus a_j = k \oplus a_p \oplus a_q$。左侧只依赖 $(i, j)$ 对、右侧只依赖 $(p, q)$ 对。用哈希表把左右匹配，整体复杂度从 $O(n^4)$ 降为 $O(n^2)$。
第三步：下标约束处理。如果把全部 $n^2$ 对一次入表，可能会把同一下标同时当左侧和右侧使用，违反 $i < j < p < q$ 约束。解决办法是用滑动分界点：按 $p$ 从 2 推进到 $n-2$，时刻维护”分界点左侧”的哈希表。
第四步：滑动分界点实现。
- 每当 $p$ 推进一步，新增 $j = p-1$ 配对所有 $i < p-1$ 的对，将 $a_i \oplus a_j$ 入表（共 $p-1$ 个键），保证这些 $(i,j)$ 对的下标都严格小于 $p$。
- 右侧查询：对当前 $p$，枚举 $q > p$，所需的左侧异或值为 $k \oplus a_p \oplus a_q$，查哈希表累加贡献。
这样保证了 $i < j < p < q$ 的下标严格递增约束。
题解代码
import sys
def solve():
data = sys.stdin.buffer.read().split()
idx = 0
T = int(data[idx]); idx += 1
out = []
for _ in range(T):
n = int(data[idx]); k = int(data[idx + 1]); idx += 2
a = list(map(int, data[idx:idx + n])); idx += n
# cnt[v]：分界点 p 左侧已加入的 (i, j) 对中 a_i ^ a_j = v 的对数
cnt = {}
ans = 0
# 滑动分界点 p：作为四元组第三个下标，从 2 到 n-2
for p in range(2, n - 1):
# 推进 cnt：新增 j = p-1 配对所有 i < p-1 的对
jn = p - 1
for i in range(jn):
v = a[i] ^ a[jn]
cnt[v] = cnt.get(v, 0) + 1
# 右侧查询：对每个 q > p，所需左侧异或值 t = k ^ a[p] ^ a[q]
base = k ^ a[p]
for q in range(p + 1, n):
t = base ^ a[q]
if t in cnt:
ans += cnt[t]
out.append(str(ans))
print('\n'.join(out))
solve()
复杂度分析
时间复杂度：单组 $O(n^2)$。入表共 $O(n^2)$ 次写，查询共 $O(n^2)$ 次读。跨组合计 $O((\sum n)^2)$ 在 $\sum n \le 2000$ 下约 $4 \times 10^6$ 次操作。 空间复杂度：$O(n^2)$，哈希表最坏存所有 $(i,j)$ 对的异或值。
小结
- 第一题是纯模拟签到题，统计满足 $a_i > x$ 的堆数乘以 $y$ 即可，注意严格大于
- 第二题三维网格枚举的核心是 26 个方向 + 合法起点的笛卡儿积，初值用负无穷避免全负权值被屏蔽
- 第三题是 sklearn 管线题，严格按题目参数搭建 StandardScaler + SVC + StratifiedKFold + GridSearchCV 管线即可
- 第四题利用异或消去律将 $O(n^4)$ 暴力拆成”中途相遇”的 $O(n^2)$，滑动分界点巧妙保证下标严格递增约束