携程2026春招笔试真题（3.12）
AK机给大家整理了一份高质量的互联网大厂、大模型独角兽的内推和暑期实习/春秋招投递信息汇总，每日更新，建议收藏：
https://docs.qq.com/smartsheet/DUXJLSnZoTVFhVUVs?tab=sc_K49vrh
携程的笔试一向以考察范围广著称，这场考试也不例外——从签到模拟到高维前缀和（SOS），难度梯度分明。AK机第一时间整理了完整题解和代码，帮大家拆解每道题的核心考点。
本场考试概述
考试时间：2026年3月12日
难度评级：中等偏难
考点分析：
1. 第一题：模拟（难度 Easy，签到题） 2. 第二题：贪心 + 数论（难度 Medium） 3. 第三题：前缀和 + 二分查找（难度 Medium-Hard） 4. 第四题：位运算 + 高维前缀和/子集和变换（难度 Hard）
建议策略：
1. 第一题是纯签到，1分钟搞定 2. 第二题贪心+奇偶分析，想清楚只用2和3凑就行 3. 第三题递归切割，关键是发现前缀和严格递增所以切割点唯一 4. 第四题是经典的SOS（Sum over Subsets），需要提前掌握高维前缀和模板
第一题：n的阶乘
题目描述
众所周知 很像一个尾巴，表示 的阶乘即 。
给定一个整数 ，AK机想知道 的个位数字是多少，请输出这个值。
输入描述
输入一行一个整数 表示询问值。
输出描述
输出一个整数表示 的个位数字。
样例1
输入
1输出
1样例2
输入
3输出
6样例解释
，个位是 。
题解：模拟
题目问题拆解
给定 ，求 的个位数字。由于 最大只有 ，直接模拟即可。
算法实现
算法主策略：本题采用直接模拟，从 乘到 ，最后取个位。
注意到当 时，一定包含因子，因此个位一定是。所以只需要关心的情况：，，，（个位）。
时空复杂度分析
时间复杂度：，最多循环 次。
空间复杂度：，只用常数变量。
Python
# n的阶乘 - 模拟
n = int(input())
defsolve(n):
# n >= 5 时阶乘包含因子 10，个位一定是 0
result = 1
for i inrange(1, n + 1):
result *= i
return result % 10
print(solve(n))第二题：素数
题目描述
给定一个正整数 与一个正整数 。你需要把 拆分为若干个素数之和（可以重复选择同一个素数），设最终使用的素数个数为 。
同时要求：所选素数中奇素数（除 以外的素数）的数量必须是 的正整数倍（不能为 ）。
请在满足约束的前提下，使 最大化，并输出这个最大的 。若不存在任何满足要求的拆分方案，输出 。
名词解释：
素数：大于 且只有 与其本身两个正因子的整数。奇素数：除 以外的素数。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数 表示测试数据组数，每组测试数据描述如下：
在一行上输入两个整数 。
输出描述
对于每一组测试数据，新起一行输出一个整数：满足要求的最大的素数个数 ；若无解，则输出 。
样例1
输入
4
6 2
2 1
30 4
1000000000000 1输出
2
-1
13
499999999999样例解释
对于第一组样例 可以拆分为 。
题解：贪心 + 数论
题目问题拆解
将 拆分为若干素数之和，使素数个数最大，且奇素数数量必须是的正整数倍。高达，需要 单组查询。
核心观察：要最大化 ，应尽量使用最小的素数。偶素数只有 ，最小奇素数是 。因此最优方案是用若干个 （作为奇素数）和若干个 （作为偶素数）来凑出 。
算法实现
算法主策略：本题采用贪心 + 数论分析。
设使用 个奇素数（全选 ，最小化开销）， 个偶素数（全选 ），则 ，。
为了最大化 ，需要最小化 。 必须是 的正整数倍，所以优先尝试 ，不满足奇偶性则尝试 。
可行性条件：（奇素数总和不超过）且为偶数（剩余部分能被整除）。注意到和的奇偶性相同，所以条件等价于和 奇偶性相同。
若 和都不满足，则无解输出（例如为偶数而为奇数时，所有的倍数都是偶数，永远无法匹配奇数）。
时空复杂度分析
时间复杂度：，每组查询 。
空间复杂度：，只用常数变量。
Python
# 素数 - 贪心 + 数论
defsolve(n, m):
# 用最小素数凑：偶素数 2 和最小奇素数 3
# n = 2*a + 3*b，b 为 m 的正整数倍，最大化 k = (n - b) / 2
for mult in [1, 2]:
b = m * mult
if3 * b > n: # 奇素数总和超过 n
break
if (n - b) % 2 == 0: # 剩余能被 2 整除
return (n - b) // 2
return -1
t = int(input())
results = []
for _ inrange(t):
n, m = map(int, input().split())
results.append(str(solve(n, m)))
print('\n'.join(results))第三题：切割数组
题目描述
给定一个长度为 的数组 。你将对数组进行若干次"切割"操作，操作规则如下：
一开始，数组段集合仅包含整段 。
每次操作，必须从"当前数组段集合"中选择一段完整的数组段 （该段长度需严格大于 ），然后选择一个位置 ，若满足：
则可以把该数组段分成两段 与 ，并以这两段替换原来的 ，继续加入到数组段集合中。
一旦一个数组段被切割，它将从集合中移除并被两个新的子段取代。你只能选择当前集合中存在的完整段进行下一次切割，不允许跨越段边界或在段内截取任意子段进行操作。
所有区间均以原数组的下标表示，不进行重新编号；切割后得到的两个区间互不重叠，且并集为原区间。请你计算，在最优策略下，总共最多能进行多少次切割。
输入描述
第一行输入一个整数 表示数组的长度。
第二行输入 个整数 表示数组中的元素。
输出描述
输出一个整数，表示最多的切割次数，若不存在任何合法的切割方案，输出 。
样例1
输入
6
1 2 1 1 1 2输出
2样例解释
对全段 ，可在处切割，因为。得到与。随后在处再次切割，因为。总共进行了 次切割。
题解：前缀和 + 二分查找
本题涉及到前缀和，不熟悉该算法的同学可以先做一下模板题：
区间和
题目问题拆解
给定长度为 的正整数数组，每次可将一段区间从"左右和相等"的位置切成两半，求最多切割次数。
算法实现
算法主策略：本题采用前缀和 + 递归二分查找。
第一步：预处理前缀和。 构建前缀和数组 ，使得 ，。这样任意区间 的和都可以 计算：。
第二步：递归寻找切割点。 对于区间，要把它切成左右和相等的两半：左半和 = 右半和 =。如果是奇数，显然无法切割。如果是偶数，我们要找一个位置，使得，即。
关键性质：由于 （全正数），前缀和数组严格递增。这意味着对于任意目标值，最多只有一个位置满足条件。因此每个区间要么恰好有一个切割点，要么没有，不需要枚举多种选择。
第三步：二分查找定位。 在严格递增的前缀和数组上，用二分查找在 时间内快速找到满足条件的位置 。找到后，将区间切成 和 ，对两半分别递归处理，答案 = （本次切割）+ 左半结果 + 右半结果。
样例推导：数组 ，前缀和 。
处理 ：总和 ，目标 。二分查找得 ，切割为 和 。
处理 ：总和 ，目标 。，，没有等于 的位置，无法切割。
处理 ：总和 ，目标 。，找到！切割为 和 ，两段长度 ，不能继续。
总切割次数 = 。
时空复杂度分析
时间复杂度：，其中 为数组总和（），递归至多 层，每层二分查找总代价 。
空间复杂度：，前缀和数组。递归栈深度 。
Python
# 切割数组 - 前缀和 + 递归二分
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
prefix = [0] * (n + 1)
for i inrange(1, n + 1):
prefix[i] = prefix[i - 1] + a[i - 1]
defsolve(l, r):
if r - l + 1 <= 2:
return0
S = prefix[r] - prefix[l - 1]
if S % 2 != 0:
return0
target = prefix[l - 1] + S // 2
# a_i >= 1，前缀和严格递增，二分查找唯一切割点
pos = bisect_left(prefix, target, l, r)
if pos < r and prefix[pos] == target:
return1 + solve(l, pos) + solve(pos + 1, r)
return0
print(solve(1, n))第四题：按位或运算
题目描述
给定一个整数 和一个长度为 的序列 。接下来有 次询问，每次给出一个整数 ，需要计算
即所有满足 & 的下标 所对应的 之和。
名词解释：
符号 "&" 表示按位与运算（对两个数的二进制逐位与），对应位均为 时结果位为，否则为。例如与满足&。
输入描述
输入包含多组测试数据。
第一行包含整数 表示测试组数。每组数据描述如下：
第一行包含两个整数 。
第二行包含 个整数 。
第三行包含 个整数 。
保证所有测试中 的总和不超过 。
输出描述
对于每组测试数据，按询问顺序输出 行，每行一个整数，表示对应查询的答案。
样例1
输入
3
5 3
1 2 3 4 5
0 7 5
3 2
10 -5 7
3 2
6 3
0 1 2 3 4 5
6 4 7输出
0
15
10
12
-5
9
3
15样例解释
样例一： 时无合法下标，和为；时都满足，和为；时，和为。
样例二： 时 ，和为 ； 时仅 ，和为 。
样例三： 时，和为；时，和为；时，和为。
题解：位运算 + 高维前缀和
题目问题拆解
对于每个查询 ，求所有满足&的下标对应的之和。，如果每次查询都暴力枚举所有，总复杂度 会超时，需要预处理加速。
什么是 & ？ 把和写成二进制，条件要求的每一个为的位，在中也必须是。换句话说，的二进制是的二进制的"子集"。例如，满足条件的有：，，，（每个的位都被的 位"覆盖"）。
算法实现
算法主策略：本题采用子集和变换（高维前缀和），是位运算题目中的经典技巧。
暴力思路与瓶颈。 对每个查询，遍历所有检查&，单次，总共 太慢。
优化思路：预处理。 如果能提前算好"对于每个可能的，所有子掩码对应的之和"，查询时直接查表就是。定义= 所有的子掩码对应的之和。问题转化为：如何高效计算所有？
子集和变换（逐位累加）。 初始化（），其余为。然后从低位到高位，逐位处理：对于第位，扫描所有，若的第位是，就让累加（去掉该位后的值）。
直觉理解：处理第 位后，包含了"第位可选可不选"的子集和；再处理第位后，包含了"第位可选可不选"的子集和……处理完所有位后，就包含了 的所有子掩码的贡献。
由于 ，数组大小为 ，共处理 位，预处理总操作约 万次，非常高效。
时空复杂度分析
时间复杂度： 预处理 + 查询，其中 。预处理约 次操作。
空间复杂度：，子集和数组大小约 。
Python
# 按位或运算 - 子集和变换 (高维前缀和)
T = int(input())
results = []
for _ inrange(T):
n, q = map(int, input().split())
a = list(map(int, input().split()))
queries = list(map(int, input().split()))
max_val = n
for x in queries:
if x > max_val:
max_val = x
# 确定位数和子集和数组大小
bits = max_val.bit_length() if max_val > 0else1
sz = 1 << bits
f = [0] * sz
for i inrange(1, n + 1):
if i < sz:
f[i] = a[i - 1]
# 子集和变换：f[mask] = 所有 mask 子掩码对应 a 值之和
for bit inrange(bits):
for mask inrange(sz):
if mask & (1 << bit):
f[mask] += f[mask ^ (1 << bit)]
for x in queries:
results.append(str(f[x]))
print('\n'.join(results))想要获取本场笔试代码，以及沟通交流求职等内容，可以加入下方AK机的校招交流群
