携程笔试 携程秋招 0904
笔试时间：2025年9月4日
往年笔试合集：
第一题：运行时速
已知三类列车的运行时速区间如下(单位: km/h):
- 高铁: [250,350];
- 动车: [160,250];
- 城际列车: [200,300]。
给定某列车的运行时速v，请判断该车可能属于以上哪几类。由于区间存在交叠，v可能同时属于多类；若不属于任意一类，则认为是“其它”。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数T(1 ≤ T ≤ 2 × 10^5)表示数据组数，每组测试数据描述如下:
每行输入一个整数v(0 ≤ v ≤ 400)表示当前列车时速(单位: km/h)。
输出描述
对每组测试数据，新起一行输出该车可能的类别；若同时属于多类，则按以下固定顺序以单个空格分隔输出全部命中的类别:
- 高铁，输出G;
- 动车，输出D;
- 城际列车，输出C。
若不属于任意一类，则输出 other。区间两端点均计入 (闭区间)。
样例输入
6
250
170
120
300
351
200
样例输出
G D C
D
other
G C
other
D C
参考题解
处理海量输入/输出 (I/O) 瓶颈：由于测试数据量巨大（T 可达 20 万），使用 Scanner 读取输入和在循环内频繁使用 System.out.println 输出会导致超时。解决方案：采用 BufferedReader 加快输入速度，并使用一个 StringBuilder 收集所有输出结果，在所有计算结束后一次性打印，以大幅提升 I/O 效率。实现分类逻辑：对每一个输入的运行速度 v，使用独立的 if 语句来判断它是否落在高铁 (G)、动车 (D) 和城际列车 (C) 各自的速度区间内。将所有匹配到的类别代号（G, D, C）按固定顺序追加到一个临时的字符串中，并用空格隔开。如果没有任何区间匹配，则最终结果为 "other"。
C++：
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int main() {
int T;
cin >> T;
stringstream output;
for (int i = 0; i < T; i++) {
int v;
cin >> v;
stringstream result;
if (v >= 250 && v <= 350) {
result << "G";
}
if (v >= 160 && v <= 250) {
if (result.str().length() > 0) {
result << " ";
}
result << "D";
}
if (v >= 200 && v <= 300) {
if (result.str().length() > 0) {
result << " ";
}
result << "C";
}
if (result.str().length() == 0) {
output << "other\n";
} else {
output << result.str() << "\n";
}
}
cout << output.str();
return 0;
}
Java：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
publicclass Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder output = new StringBuilder();
for (int i = 0; i < T; i++) {
int v = Integer.parseInt(br.readLine());
StringBuilder result = new StringBuilder();
if (v >= 250 && v <= 350) {
result.append("G");
}
if (v >= 160 && v <= 250) {
if (result.length() > 0) {
result.append(" ");
}
result.append("D");
}
if (v >= 200 && v <= 300) {
if (result.length() > 0) {
result.append(" ");
}
result.append("C");
}
if (result.length() == 0) {
output.append("other\n");
} else {
output.append(result.toString()).append("\n");
}
}
System.out.print(output.toString());
}
}
Python：
import sys
def main():
T = int(sys.stdin.readline())
output = []
for _ in range(T):
v = int(sys.stdin.readline())
result = []
if 250 <= v <= 350:
result.append("G")
if 160 <= v <= 250:
result.append("D")
if 200 <= v <= 300:
result.append("C")
if len(result) == 0:
output.append("other")
else:
output.append(" ".join(result))
for line in output:
print(line)
if __name__ == "__main__":
main()
第二题：排列修补
游游有一个原始排列，但部分元素丢失，剩余元素形成长度为n的数组{a1,a2,...,an}。
对于每个1 ≤ i ≤ n，将前缀{a1,a2,...,ai}看作新的数组，要把它补全成一个排列，至少需要插入多少个元素?换句话说，对于每个1 ≤ i ≤ n，考虑由前缀a1,a2,...,ai构成的元素集合。要将这个集合补全为一个长度为m的排列(即包含1,2,...,m)，m的值必须不小于该集合中的任何元素)。为了使插入的元素数量最少，你需要选择一个最优的m。请问在这种最优选择下，至少需要插入多少个元素?
请输出每个前缀所需插入的最少元素数。
【名词解释】
长度为n的排列:由1,2,...,n这n个整数、按任意顺序组成的数组(每个整数均恰好出现一次)。例如，{2,3,1,5,4}是一个长度为5的排列，而{1,2,2}和{1,3,4}都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
输入描述
第一行输入一个整数n(1 ≤ n ≤ 2 × 10^5)，表示数组的长度；
第二行输入n个整数a1,a2,...,an(1 ≤ ai ≤ 10^9)，表示数组的元素。
输出描述
在一行上输出n个整数，用空格分隔。其中第i个整数表示前缀{a1,a2,...,ai}需要插入的最少元素数。
样例输入
3
3 1 6
样例输出
2 1 3
参考题解
依次遍历输入的数组，对于每一个元素，都考虑从数组开头到该元素的“前缀”子数组。要将这个前缀补充为一个完整的 1 到 m 的排列，最优的 m 值必须等于当前前缀中的最大元素值。因此，对于每个前缀，我们只需要实时维护两个关键信息：当前前缀中所有元素的最大值。当前前缀中不同元素的个数。最少需要插入的元素数量，就是 “当前最大值” 与 “当前不同元素的个数” 两者之差。在遍历过程中，使用一个变量来更新最大值，同时使用一个集合（Set）来高效地统计不同元素的数量。
C++：
#include <iostream>
#include <set>
#include <sstream>
using namespace std;
int main() {
int n;
cin >> n;
set<int> uniqueElements; // set 默认就是有序的，类似 TreeSet
int maxElement = 0;
stringstream sb;
for (int i = 0; i < n; i++) {
int currentElement;
cin >> currentElement;
uniqueElements.insert(currentElement);
if (currentElement > maxElement) {
maxElement = currentElement;
}
int insertions = maxElement - uniqueElements.size();
sb << insertions;
if (i < n - 1) {
sb << " ";
}
}
cout << sb.str() << endl;
return 0;
}
Java：
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
publicclass Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 使用 TreeSet 替代 HashSet，确保操作的时间复杂度为 O(log n)
Set<Integer> uniqueElements = new TreeSet<>();
int maxElement = 0;
// 使用 StringBuilder 优化I/O性能
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
int currentElement = sc.nextInt();
uniqueElements.add(currentElement);
if (currentElement > maxElement) {
maxElement = currentElement;
}
int insertions = maxElement - uniqueElements.size();
sb.append(insertions);
if (i < n - 1) {
sb.append(" ");
}
}
System.out.println(sb.toString());
sc.close();
}
}
Python：
n = int(input())
unique_elements = set()
max_element = 0
result = []
elements = list(map(int, input().split()))
for i in range(n):
current_element = elements[i]
unique_elements.add(current_element)
if current_element > max_element:
max_element = current_element
insertions = max_element - len(unique_elements)
result.append(str(insertions))
print(" ".join(result))
第三题：数字个数
游游有四个整数l, r, k, x，求区间[l, r]中有多少个整数i满足：i (mod k) = x。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数T(1 ≤ T ≤ 10^4)代表数据组数，每组测试数据描述如下：
在一行上输入四个整数l, r, k, x(1 ≤ l ≤ r ≤ 10^9; 1 ≤ k ≤ 10^9; 0 ≤ x ≤ k - 1)，表示查询的区间、模数、余数。
输出描述
对于每一组测试数据，新起一行给出一个整数，表示符合条件的数字个数。
样例输入
3
1 5 2 1
10 20 3 2
1 114514 2 0
样例输出
3
4
57257
参考题解
这个问题的核心是计算一个给定区间 [l, r] 内，有多少个整数 i 满足 i mod k = x 的条件。
1. 转化问题：直接在 [l, r] 区间内计数比较麻烦。一个常用的技巧是利用前缀和（或称为容斥原理）的思想。我们不直接求 [l, r] 的解，而是先求出在 [1, r] 区间内满足条件的整数个数，再减去在 [1, l-1] 区间内满足条件的整数个数，二者的差就是 [l, r] 区间内的解。
2. 核心函数：因此，问题被简化为实现一个函数 count(n, k, x)，用于计算在 [1, n] 区间内有多少整数 i 满足 i mod k = x。
3. 求解 count(n, k, x)：满足 i mod k = x 的数是一个公差为 k 的等差数列，首项是 x（如果 x 大于 0）或 k（如果 x 等于 0）我们可以通过整数除法来快速计算出在 [1, n] 范围内有多少个这样的数。例如，要计算 [1, n] 中有多少个数模 k 等于 x (x>0)，这些数是 x, x+k, x+2k, …。我们只需要找到小于等于 n 的最大项 x + m*k，然后计算 m 的可能取值个数（从 0 开始），这可以通过 (n - x) / k + 1 来计算。对于 x=0 的特殊情况，这些数是 k, 2k, 3k, …，其个数就是 n / k。
通过上述方法，代码先定义了 count 函数，然后在主循环中对于每个查询 l, r, k, x，通过调用 count(r, k, x) - count(l - 1, k, x) 来得到最终结果。
C++：
#include <iostream>
using namespace std;
long long count(long long n, long long k, long long x) {
if (n < 0) {
return 0;
}
if (x == 0) {
return n / k;
} else {
if (n < x) {
return 0;
}
return (n - x) / k + 1;
}
}
int main() {
int T;
cin >> T;
while (T-- > 0) {
long long l, r, k, x;
cin >> l >> r >> k >> x;
long long result = count(r, k, x) - count(l - 1, k, x);
cout << result << endl;
}
return 0;
}
Java：
import java.util.Scanner;
publicclass Main {
public static long count(long n, long k, long x) {
if (n < 0) {
return0;
}
if (x == 0) {
return n / k;
} else {
if (n < x) {
return0;
}
return (n - x) / k + 1;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
long l = sc.nextLong();
long r = sc.nextLong();
long k = sc.nextLong();
long x = sc.nextLong();
long result = count(r, k, x) - count(l - 1, k, x);
System.out.println(result);
}
sc.close();
}
}
Python：
def count(n, k, x):
if n < 0:
return 0
return n // k if x == 0 else ((n - x) // k + 1 if n >= x else 0)
T = int(input())
for _ in range(T):
l, r, k, x = map(int, input().split())
print(count(r, k, x) - count(l - 1, k, x))
第四题：K-小距离
给定一棵包含 n 个节点的无向带权树，每条边 (u,v) 的权重为正整数 wₙᵥ。树上共有 m 个标记为 “红点” 的节点。给定一个整数 K (1 ≤ K ≤ m)，对于每个节点 v，定义该节点到树中 K 个最近红点的距离和：F (v) = Σᵢ₌₁ᴷ dᵢ(v)，其中 d₁(v) ≤ d₂(v) ≤ … ≤ d_K (v) 是节点 v 到所有红点按距离从小到大排序的前 K 个距离。
请计算所有节点的 F (v)。
输入描述
第一行输入三个整数 n, m, K (2 ≤ m ≤ n ≤ 2×10⁵, 1 ≤ K ≤ min (100, m))，分别表示节点数、红点数和 K。
第二行输入 m 个互不相同的整数 r₁, r₂, …, r_m (1 ≤ rᵢ ≤ n)，表示红点节点编号。
接下来 n - 1 行，每行输入三个整数 uᵢ, vᵢ, wᵢ(1 ≤ uᵢ, vᵢ ≤ n, uᵢ ≠ vᵢ, 1 ≤ wᵢ ≤ 10⁶)，表示一条无向带权边。
保证输入构成一棵树。
输出描述
输出一行，包含 n 个整数 F (1), F (2), …, F (n)，用空格分隔。
样例输入
5 3 1
2 4 5
1 2 1
2 3 1
3 4 1
4 5 1
样例输出
1 0 1 0 0
参考题解
核心解决思路是**树形动态规划 (Tree DP
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
查看14道真题和解析