笔试时间：2025年9月4日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：运行时速

已知三类列车的运行时速区间如下(单位: 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