🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 140+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🌈 米哈游秋招笔试，来啦！！！

🧸 本次难度中等偏上，前两题难度较低，最后一题比较难写，细节较多

1️⃣ 自定义排序，stable sort 稳定排序的应用

2️⃣ 比较基础的树形DP，难度不大

3️⃣ 组合数学的问题，需要预处阶层和组合数，难度较大

🧸 01.古董拍卖会 评测链接🔗

问题描述

LYA 是一位著名的古董收藏家，她最近参加了一场盛大的古董拍卖会。拍卖会上共有 件古董，每件古董都有一个独特的价值。拍卖会采用了一种特殊的排序方式来展示这些古董：按照价值从高到低排序，但对于价值相同的古董，会保持它们原本的展示顺序不变。

拍卖会结束后，LYA 对两件特定的古董产生了兴趣。她想知道这两件古董在原本展示顺序中的距离。具体来说，她想知道排名为 的古董和排名为 的古董在原始展示顺序中的位置差。

输入格式

第一行包含三个正整数 、 和 ，分别表示古董的总数 ，以及 LYA 感兴趣的两件古董的排名 和 。

第二行包含 个正整数 ，表示每件古董的价值。

输出格式

输出一个整数，表示排名为 的古董和排名为 的古董在原始展示顺序中的位置差的绝对值。

样例输入1

5 3 5
4 2 3 1 5

样例输出1

2

样例输入2

6 2 5
3 3 3 3 3 3

样例输出2

3

样例解释

样例 解释说明

样例1	排序后的顺序是 [5, 4, 3, 2, 1]。排名第 3 的古董原本在位置 3，排名第 5 的古董原本在位置 5，它们之间的距离是
样例2	所有古董的价值都相同，因此排序后的顺序与原顺序相同。排名第 2 的古董在位置 2，排名第 5 的古董在位置 5，它们之间的距离是

数据范围

• 
• 
• 

题解

自定义排序

需要在对古董按价值排序的同时，保留原始顺序的信息。

参考代码

• Python

class Antique:
    def __init__(self, value, original_position):
        self.value = value
        self.original_position = original_position

    def __lt__(self, other):
        return self.value < other.value

def main():
    # 读取 total_antiques, rank_a, rank_b
    total_antiques, rank_a, rank_b = map(int, input().split())

    # 读取数组
    antiques = []
    values = list(map(int, input().split()))
    for i, value in enumerate(values):
        antiques.append(Antique(value, i))  # 保存值和原始位置

    # 进行稳定排序
    antiques.sort()

    # 获取排名为 rank_a 和 rank_b 的古董
    antique_a = antiques[rank_a - 1]
    antique_b = antiques[rank_b - 1]

    # 计算原始位置之差的绝对值
    distance = abs(antique_a.original_position - antique_b.original_position)

    # 输出结果
    print(distance)

if __name__ == "__main__":
    main()

• Java

import java.util.*;

public class Main {
    static class Antique implements Comparable<Antique> {
        int value;
        int original_position;

        Antique(int value, int original_position) {
            this.value = value;
            this.original_position = original_position;
        }

        @Override
        public int compareTo(Antique other) {
            return Integer.compare(this.value, other.value);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取 total_antiques, rank_a, rank_b
        int total_antiques = scanner.nextInt();
        int rank_a = scanner.nextInt();
        int rank_b = scanner.nextInt();

        // 读取数组
        List<Antique> antiques = new ArrayList<>();
        for (int i = 0; i < total_antiques; i++) {
            int value = scanner.nextInt();
            antiques.add(new Antique(value, i));  // 保存值和原始位置
        }

        // 进行稳定排序
        Collections.sort(antiques);

        // 获取排名为 rank_a 和 rank_b 的古董
        Antique antique_a = antiques.get(rank_a - 1);
        Antique antique_b = antiques.get(rank_b - 1);

        // 计算原始位置之差的绝对值
        int distance = Math.abs(antique_a.original_position - antique_b.original_position);

        // 输出结果
        System.out.println(distance);

        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Antique {
    int value;
    int original_position;

    Antique(int v, int p) : value(v), original_position(p) {}

    bool operator<(const Antique& other) const {
        return value < other.value;
    }
};

int main() {
    int total_antiques, rank_a, rank_b;
    cin >> total_antiques >> rank_a >> rank_b;

    vector<Antique> antiques;
    antiques.reserve(total_antiques);

    // 读取数组
    for (int i = 0; i < total_antiques; i++) {
        int value;
        cin >> value;
        antiques.emplace_back(value, i);  // 保存值和原始位置
    }

    // 进行稳定排序
    stable_sort(antiques.begin(), antiques.end());

    // 获取排名为 rank_a 和 rank_b 的古董
    const Antique& antique_a = antiques[rank_a - 1];
    const Antique& antique_b = antiques[rank_b - 1];

    // 计算原始位置之差的绝对值
    int distance = abs(antique_a.original_position - antique_b.original_position);

    // 输出结果
    cout << distance << endl;

    return 0;
}

🎀 02.LYA的冒险游戏 评测链接🔗

问题描述

LYA 正在玩一款名为《奇幻冒险》的游戏。游戏中有 个关卡，这些关卡形成了一棵以 1 号关卡为根的树形结构。每个关卡都有一个前置关卡（除了 1 号关卡），玩家必须先通过前置关卡才能进入当前关卡。

每个关卡都有两个属性值：探索值 和挑战值 。关卡的趣味度定义为这两个值的和。LYA 想知道她通过一些关卡（可以是任意数量）能获得的最大趣味度总和是多少。

请你帮助 LYA 计算出这个最大趣味度总和。

输入格式

第一行输入一个整数 ，表示关卡的数量。

第二行输入 个整数 ，其中 表示第 个关卡的前置关卡编号。

第三行输入 个整数 ，表示每个关卡的探索值。

第四行输入 个整数 ，表示每个关卡的挑战值。

输出格式

输出一个整数，表示 LYA 能获得的最大趣味度总和。

好的，我会为您添加这个新的样例并提供解释。以下是更新后的样例部分：

样例输入1

5
1 1 2 2
1 -2 3 -4 5
-1 2 -3 4 -5

样例输出1

0

样例输入2

4
1 1 2
1 -1 1 1
2 2 0 -2

样例输出2

3

样例解释

样例 解释说明

样例1	在这个例子中，最优的选择是不选择任何关卡。因为选择任何关卡或关卡组合都会导致负的趣味度总和，所以最大的趣味度总和是0。
样例2	在这个例子中，最优的选择是选择关卡1、2和3。关卡1的趣味度是1+2=3，关卡2的趣味度是-1+2=1，关卡3的趣味度是1+0=1。总的趣味度为3+1+1=5。虽然关卡4的探索值为正，但其挑战值为负，总趣味度为负，所以不选择关卡4。因此，最大的趣味度总和是5。

数据范围

• 
• 
• 

题解

树形DP

这道题目本质上是一个树形动态规划问题。需要在一棵树上选择一些节点，使得这些节点的权值和最大。每个节点的权值就是该关卡的趣味度（探索值加挑战值）。

**关键点：**必须从根节点开始选择，并且只有选择了父节点，才能选择子节点。这就形成了一个自顶向下的依赖关系。

解题思路如下：

1. DFS遍历这棵树。在DFS的过程中，自底向上地计算每个节点的最大贡献值。

2. 对于每个节点，有两个选择：

   • 选择这个节点：那么就可以加上这个节点的趣味度，并且可以选择它的子节点。
   • 不选择这个节点：那么就不能选择它的任何子节点。

3. 目标是最大化总和，所以对于每个节点，选择这两种情况中较大的那个。

4. 最后，根节点的最大贡献值就是要求的答案。

时间复杂度分析：只需要遍历一次树，所以时间复杂度是 ，其中 是节点的数量。这对于给定的数据范围（）是可以接受的。

参考代码

• Python

# 读取输入
n = int(input())
f = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# 构建树结构
tree = [[] for _ in range(n + 1)]
for i in range(1, n):
    tree[f[i-1]].append(i+1)

# DFS函数，计算每个节点的最大贡献值
def dfs(node):
    value = a[node-1] + b[node-1]  # 当前节点的趣味度
    for child in tree[node]:
        child_value = dfs(child)
        if child_value > 0:
            value += child_value
    return value

# 从根节点开始DFS
result = dfs(1)

# 输出结果，如果为负则输出0
print(max(result, 0))

• Java

import java.util.*;

public class Main {
    static List<List<Integer>> tree;
    static int[] a, b;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        tree = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            tree.add(new ArrayList<>());
        }
        
        for (int i = 2; i <= n; i++) {
            int f = scanner.nextInt();
            tree.get(f).add(i);
        }
        
        a = new int[n + 1];
        b = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            b[i] = scanner.nextInt();
        }
        
        // 从根节点开始DFS
        long result = dfs(1);
        
        // 输出结果，如果为负则输出0
        System.out.println(Mat