笔试时间：2023年9月21日 秋招

备注：第三题题干不全暂无题解

第一题

题目：开电动汽车回家过年

新年即将来临，小明计划开新买的电动汽车回老家过年。已知小明的工作地在上海，老家在中部某城市A。上海到城市A的距离是L公里(1<=L≤100000)。小明的电动汽车的电池航程是P，电池最大电量也是P(假设电动汽车行使一公里需要消耗1度电。(1<=P<=100))。如果电动车在中途电量耗尽了，将无法继续强行，也就无法到达目的地了。已知小明出发前已经把电池充满了。途中依次经过N(1<=N<10000)个充电站。第i个充电站距离城市A有 Ai公里，最大可充电 Bi度。请问，小明能不能顺利地回老家过年?如果可以，请输出最少需要充电多少次;如果不可以，请输出-1。

解答要求：时间限制: C/C++ 1000ms, 其他语言: 2000ms内存限制: C/C++ 256MB,其他语言: 512MB。

输入描述

输入的第一行为数字N；

接下来的N行，每行包含2个数并用空格隔开: Ai Bi；

最后一行包括两个数LP，并用空格隔开。

输出描述

按照题目要求输出最少次数或者-1。

样例输入

4

4 4

5 5

11 6

15 8

25 10

样例输出

3

解释

小明出发时电池电量是10，距离城市A 25公里。

行驶10公里后，到达距离城市A 15公里的充电站，充点前电池电量为0，充电8度之后，再出发。

行驶4公里后，到达距离城市A11公里的充电站，充电前电池电量为4。充电6度之后，再出发。

行驶6公里后，到达距离城市A 5公里的充电站，充电前电池电量为4，充电1度之后，再出发。

之后，可以直接开到城市A，一共需要充电3次才能到达城市A。

参考题解

动态规划+记忆化搜索。

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

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

using namespace std;

int solve(int N, vector<pair<int, int>> &stations, int L, int P) {
    sort(stations.begin(), stations.end());
    stations.insert(stations.begin(), make_pair(0, 0));

    function<int(int, int)> dfs = [&](int i, int j) -> int {
        if (i == N) {
            int diff = L - stations[N].first;
            if (j >= diff) return 0;
            if (j + stations[N].second >= diff) return 1;
            return INT_MAX;
        }
        int diff = stations[i + 1].first - stations[i].first;
        int ans = INT_MAX;
        if (j >= diff) {
            ans = min(ans, dfs(i + 1, j - diff));  // 不充电
        }

        if (j + stations[i].second >= diff) {
            int curP = min(j + stations[i].second, P);  // 防止充爆
            ans = min(ans, dfs(i + 1, curP - diff) + 1);
        }
        return ans;
    };

    int ans = dfs(0, P);
    if (ans == INT_MAX) return -1;
    return ans;
}

int main() {
    int N, L, P;
    cin >> N;
    vector<pair<int, int>> stations(N);
    for (int i = 0; i < N; i++) {
        cin >> stations[i].first >> stations[i].second;
    }
    cin >> L >> P;

    int result = solve(N, stations, L, P);
    cout << result << endl;
    return 0;
}

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

from math import inf

def solve(N, stations, L, P):
    stations.sort(key=lambda x: x[0])
    stations = [[0, 0]] + stations

    def dfs(i, j):
        if i == N:
            diff = L - stations[-1][0]
            if j >= diff:
                return 0
            if j + stations[-1][1] >= diff:
                return 1
            return inf
        diff = stations[i + 1][0] - stations[i][0]
        ans = inf
        if j >= diff:
            ans = min(ans, dfs(i + 1, j - diff))  # 不充电

        if j + stations[i][1] >= diff:
            curP = min(j + stations[i][1], P)  # 防止充爆
            ans = min(ans, dfs(i + 1, curP - diff) + 1)
        return ans

    ans = dfs(0, P)
    if ans == inf:
        return -1
    return ans

if __name__ == "__main__":
    N = int(input())
    stations = []
    for _ in range(N):
        stations.append([int(c) for c in input().split()])

    L, P = map(int, input().split())

    result = solve(N, stations, L, P)
    print(result)

第二题

题目：查询节点路径

树的节点有三个属性:节点名称、节点ID，节点的父级节点ID。同一个父级节点下的所有子节点名称不会重复，但节点名称在全局可能重复。节点名称中不包含 / 字符，节点的id全局唯一，如果节点是树的根节点，则其父级节点1D的约定为-1，可以使用节点路径唯一标识一个节点在树中的位置。节点路径生成方式是:从树的根节点开始，找出到目标节点所经过的所有节点，然后将这些节点名称、用/字符分隔拼接而成。请实现树的节点查询功能:根据指定节点名称，返回查询出的所有节点路径。

解答要求：时间限制: C/C++1000ms,其他语言: 2000ms内存限制: C/C++ 256MB,其他语言:512MB

输入描述

标准IO输入。

第一行为要查询的节点名称。

第二行为节点名称序列，名称间使用逗号分隔。序列的序号即为节点id，序号从0开始。节点总数小于1024。

第三行为每个节点的父级节点的id。根节点的父级id约定为:-1

输出描述

输出一个整数，表示最少的操作次数。返回搜索到的所有节点的路径。

如果查询出多条路径，则按照路径的字典序从小到大排序后输出，逗号分隔。如果搜索结果为空，则输出 null。

样例输入

c

a,b,c,d,c

-1,0,1,0,3

样例输出

/a/b/c,/a/d/c

参考题解

dfs+回溯。总体来说就是先建树， 然后树上找路径。

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

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

using namespace std;

int main() {
    string target;
    cin >> target;
    cin.ignore(); // Consume newline character

    string names_str;
    getline(cin,