笔试时间：2024年10月12日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

给定一个长度为 n 的数组，你需要对这个数组进行稳定地排序（从大到小排序）。稳定的排序指的是对于相同元素而言，排序前位置在前面的元素在排序后的位置仍然在前面。排序之后每一个元素有一个确定的排名，现在要求你输出排名为 a 的元素和排名为 b 的元素在排序之前的距离是多少。

输入描述

第一行包含三个正整数 n, a, b，分别表示数组的长度 n 和两个需要计算距离的元素排名 a 和 b（1 ≤ a, b ≤ n ≤ 10^5）。

第二行包含 n 个正整数 num_i，表示数组中的每一个数字（1 ≤ num_i ≤ 10^5）。

输出描述

输出一行整数表示答案。

样例输入

5 3 5

4 2 3 1 5

样例输出

2

解释：在排序后，排名为 3 和 5 的元素在原数组中的位置分别为 3 和 5，距离为 |3 - 5| = 2。

参考题解

定义一个内部静态类 Element记录原始索引，然后对其进行排序即可。对于Java 的 Arrays.sort() 对象数组是稳定排序，所以对于值相同的元素，排序后的位置与原始顺序一致。排序完成后，排名为 a 的元素在 elements[a - 1]，排名为 b 的元素在 elements[b - 1]。

C++：[此代码未进行大量数据的测试，仅供参考]

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

using namespace std;

struct Element {
    int value;
    int originalIndex;

    Element(int value, int originalIndex) : value(value), originalIndex(originalIndex) {}

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

int main() {
    int n, a, b;
    cin >> n >> a >> b;

    vector<Element> elements;
    for (int i = 0; i < n; i++) {
        int value;
        cin >> value;
        elements.emplace_back(value, i);
    }

    // 进行稳定排序
    sort(elements.begin(), elements.end());

    // 获取排名为 a 和 b 的元素
    Element elemA = elements[a - 1];
    Element elemB = elements[b - 1];

    // 计算原始下标之差的绝对值
    int distance = abs(elemA.originalIndex - elemB.originalIndex);

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

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    static class Element implements Comparable<Element> {
        int value;
        int originalIndex;

        public Element(int value, int originalIndex) {
            this.value = value;
            this.originalIndex = originalIndex;
        }

        public int compareTo(Element other) {
            return this.value - other.value;
        }
    }

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

        // 读取 n, a, b
        int n = scanner.nextInt();
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        // 读取数组
        Element[] elements = new Element[n];
        for (int i = 0; i < n; i++) {
            int value = scanner.nextInt();
            elements[i] = new Element(value, i); // 保存值和原始下标
        }

        // 进行稳定排序
        java.util.Arrays.sort(elements);

        // 获取排名为 a 和 b 的元素
        Element elemA = elements[a - 1];
        Element elemB = elements[b - 1];

        // 计算原始下标之差的绝对值
        int distance = Math.abs(elemA.originalIndex - elemB.originalIndex);

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

Python：[此代码未进行大量数据的测试，仅供参考]

class Element:
    def __init__(self, value, original_index):
        self.value = value
        self.original_index = original_index

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


def main():
    # 读取 n, a, b
    n, a, b = map(int, input().split())

    # 读取数组
    elements = []
    for i in range(n):
        value = int(input())
        elements.append(Element(value, i))

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

    # 获取排名为 a 和 b 的元素
    elem_a = elements[a - 1]
    elem_b = elements[b - 1]

    # 计算原始下标之差的绝对值
    distance = abs(elem_a.original_index - elem_b.original_index)

    # 输出结果
    print(distance)


if __name__ == "__main__":
    main()

第二题

题目

米小游正在玩《绝区零》。在《绝区零》中有一些关卡，这些关卡形成了一棵以 1 为根的有根树。具体来说，对于第 i 个关卡，必须通过它的前置关卡 f_i，后才能通过第 i 个关卡，其中第 1 个关卡没有前置关卡。每个关卡都有一个解密值 a_i 和一个操作值 b_i。一个关卡的趣味程度就是解密值与操作值之和。米小游想知道她通过若干个关卡可以获得的趣味程度之和的最大值是多少。

输入描述

第一行输入一个整数 n（1 ≤ n ≤ 10^5），表示关卡数量。

第二行输入 n-1 个整数 f_i（1 ≤ f_i ≤ i），表示第 i 个关卡的前置关卡。

第三行输入 n 个整数 a_i（-10^9 ≤ a_i ≤ 10^9），表示第 i 个关卡的解密值。

第四行输入 n 个整数 b_i（-10^9 ≤ b_i ≤ 10^9），表示第 i 个关卡的操作值。

输出描述

输出一个整数，表示答案，即通过若干个关卡可以获得的趣味程度之和的最大值。

样例输入

5

1 1 2 2

1 -2 3 -4 5

-1 2 -3 4 -5

样例输出

0

参考题解

由于必须先通过前置关卡才能通过当前关卡，因此关卡之间形成了一棵以 1 为根的树。我们需要在这棵树上选择一些节点（关卡），使得这些节点的有趣程度之和最大。对于每个节点，我们有两个选择：选择当前节点，并可以选择其子节点（如果对总和有益）。不选择当前节点，则不能选择其任何子节点（因为无法通过前置关卡）。因此，使用深度优先搜索，从下到上计算每个节点的最大有趣程度和。如果子节点的有趣程度和为正数，累加到当前节点的总和中。如果为负数，说明选择子节点会降低总和，因此不累加。最终，从根节点开始，得到整棵树的最大有趣程度和。

C++：[此代码未进行大量数据的测试，仅供参考]

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

using namespace std;

// 定义节点类
struct Node {
    int index; // 节点编号
    long long value; // 节点的有趣程度（a_i + b_i）
    vector<int> children; // 子节点列表

    Node() : value(0) {}
};

vector<Node> nodes;

// 深度优先搜索函数，返回以当前节点为根的子树的最大有趣程度和
long long dfs(int u) {
    long long sum = nodes[u].value; // 当前节点的有趣程度
    for (int v : nodes[u].children) {
        long long childSum = dfs(v); // 计算子节点的有趣程度和
        if (childSum > 0) {
            sum += childSum; // 只有当子节点的有趣程度和为正数时才累加
        }
    }
    return sum > 0 ? sum : 0;
}

int main() {
    int n;
    cin >> n; // 读取关卡数量
    nodes.r