✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

百度第一套-2025.09.23

题目一：小兰的古董收集

1️⃣：使用后缀预处理，从数组末尾向前扫描并维护已出现元素集合

2️⃣：对每个位置计算从该位置到末尾的不同元素个数

3️⃣：利用预处理结果O(1)回答每个询问

难度：中等

这道题目的关键在于理解后缀统计的思想。通过从后往前预处理，我们可以避免重复计算，将原本每次询问O(n)的时间复杂度优化到O(1)。使用哈希集合记录已出现的元素是解决此类问题的经典技巧。

题目二：小基的资源调度系统

1️⃣：计算每台服务器的实际单任务计费时长 min(a_i, x)

2️⃣：使用贪心策略，按计费时长排序进行任务分配

3️⃣：分别计算最小值（优先分配给时长短的服务器）和最大值（优先分配给时长长的服务器）

难度：中等

这道题目结合了贪心算法和资源分配优化。关键在于理解如何通过排序和贪心分配来达到极值。先保证每台服务器的下界需求，再对剩余任务进行贪心分配，是解决此类约束优化问题的标准方法。

01. 小兰的古董收集

问题描述

小兰是一位著名的古董收藏家，她最近收购了一批珍贵的古董艺术品。每件古董都有一个独特的编号用于标识其类型，用正整数 表示。小兰将这 件古董按照收购顺序从左到右排成一排，并从 到 依次编号，对应的古董类型编号记为 。

为了更好地管理这些古董，小兰聘请了一位专业的古董鉴定师小毛。小毛希望了解从任意位置开始到最后一件古董为止，总共包含了多少种不同类型的古董。

小毛给出了 个询问位置 （）。对于每个位置 ，他想知道从第 件古董到第 件古董（包含两端）这个范围内，一共有多少种不同类型的古董。

输入格式

第一行包含两个正整数 和 ，分别表示古董的总数和询问的次数。

第二行包含 个正整数 ，表示这 件古董的类型编号。

接下来 行，每行包含一个正整数 （），表示第 次询问的起始位置。

输出格式

输出 行，每行一个正整数，第 行的整数表示从第 件古董到第 件古董这个范围内，一共有多少种不同类型的古董。

样例输入

7 4
2 4 2 6 8 4 10
2
4
5
7

样例输出

5
4
3
1

数据范围

题解

这道题目要求我们快速回答多个询问：从某个位置到数组末尾有多少种不同的元素。如果每次询问都重新统计，时间复杂度会很高。

关键思路是使用后缀预处理的方法。我们可以从数组的末尾开始向前扫描，维护一个后缀数组 suf，其中 suf[i] 表示从位置 到数组末尾有多少种不同的元素。

具体算法：

1. 创建一个哈希集合来记录已经出现过的元素类型
2. 从数组末尾开始向前扫描每个位置
3. 对于位置 ，如果 之前没有出现过，说明它为后缀贡献了一种新类型
4. 更新 suf[i] = suf[i+1] + (a_i是否为新类型 ? 1 : 0)

这样预处理后，每个询问只需要 时间就能回答。

时间复杂度：预处理 ，回答所有询问 ，总复杂度 。 空间复杂度：。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

# 读取输入
n, m = map(int, input().split())
arr = list(map(int, input().split()))

# 后缀预处理，从后往前扫描
suf = [0] * (n + 2)  # suf[i] 表示从位置i到末尾的不同元素个数，多分配一位防止越界
seen = set()  # 记录已经出现的元素

for i in range(n - 1, -1, -1):  # 从 n-1 到 0 倒序遍历
    pos = i + 1  # 转换为1-based索引
    if arr[i] not in seen:  # 如果是新出现的元素
        seen.add(arr[i])  # 加入集合
        suf[pos] = suf[pos + 1] + 1  # 不同元素数量+1
    else:
        suf[pos] = suf[pos + 1]  # 不是新元素，数量不变

# 处理查询
for _ in range(m):
    b = int(input())
    print(suf[b])  # 直接输出预处理的结果

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n + 1);  // 1-indexed数组
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<int> suf(n + 2, 0);  // 后缀数组，suf[i]表示从i到n的不同元素个数
    unordered_set<int> vis;  // 记录已访问的元素
    
    // 从后往前预处理
    for (int i = n; i >= 1; i--) {
        if (vis.find(a[i]) == vis.end()) {  // 如果元素未出现过
            vis.insert(a[i]);  // 加入访问集合
            suf[i] = suf[i + 1] + 1;  // 不同元素数量+1
        } else {
            suf[i] = suf[i + 1];  // 已出现过，数量不变
        }
    }
    
    // 回答查询
    for (int i = 0; i < m; i++) {
        int b;
        cin >> b;
        cout << suf[b] << "\n";  // 输出预处理结果
    }
    
    return 0;
}

• Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int m = Integer.parseInt(firstLine[1]);
        
        int[] arr = new int[n + 1];  // 1-indexed数组
        String[] arrStr = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(arrStr[i - 1]);
        }
        
        int[] sufCnt = new int[n + 2];  // 后缀计数数组
        HashSet<Integer> visited = new HashSet<>();  // 记录已访问元素的集合
        
        // 从数组末尾向前预处理
        for (int i = n; i >= 1; i--) {
            if (!visited.contains(arr[i])) {  // 如果是新出现的元素
                visited.add(arr[i]);  // 添加到访问集合
                sufCnt[i] = sufCnt[i + 1] + 1;  // 不同元素数量递增
            } else {
                sufCnt[i] = sufCnt[i + 1];  // 重复元素，数量保持不变
            }
        }
        
        // 处理所有查询
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int b = Integer.parseInt(br.readLine());
            sb.append(sufCnt[b]).append("\n");  // 输出预处理的结果
        }
        
        System.out.print(sb);
        br.close();