笔试时间：2024年08月01日 提前批

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

第一题

题目：小友的生产线

小友设计了一条新的生产线，在该条生产线上共有0-n种工序。每种工序之间可能存在上下游关系，如果一种工序没有下游工序，则为终点工序。如果一种工序其所有可能下游工序均可到达终点工序，则称该工序为合规工序。给你一个有向图，其中有n个节点，表示不同种工序，以及不同工序之间的关系，请计算该条生产线中，所有的合规工序，并按照升序排列。

注意：终点工序无下游工序，默认为合规工序。

输入描述

第一行输入正整数n，表示共有n个工序节点；

接下来n行，每行有j(1<=j<n)个数，表示工序节点i与其余j个工序节点上下游关系。

注意：若工序节点i为终点工序，则j=1，且数值为-1。

输出描述

输出一个数组，用来表示所有的合规工序，并按照升序排列。

补充说明：n == graph.length、1 <= n <= 104、0 <= n[i].length <= n、-1 <= n[i][j] <= n - 1、n[i] 按严格递增顺序排列，图中可能包含自环。

样例输入一

5

1 2 3 4

1 2

3 4

0 4

-1

样例输出一

4

说明：只有工序4是终点工序，即为合规工序

样例输入二

7

1 2

2 3

5

0

5

-1

-1

样例输出二

2 4 5 6

说明：工序5和6为终点工序，即为合规工序 工序2和4开始的所有下游工序最终都指向终点工序，按照升序排列最终结果为2，4，5，6。

参考题解

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

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

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

第二题

题目：小友策划游戏人物

小友是一个游戏策划，他计划设计一个新人物，该人物的攻击模式较为特殊：他的附加攻击力可以拆分为n份（n>=2），这n份的乘积作为最终伤害值。游戏总监认为该人物过于超模（过于强大），要求对其附加攻击力增加上限限制。现在给你最终伤害值的上限和该人物的附加攻击力，请判断该人物的实际最终伤害值是否会超出给出的最终伤害值上限。

输入描述

输入两个数值，第一个数值为最终伤害值上限，第二个数值为该人物的附加攻击力。

例如：2920 22

2920为最终伤害值的上限

22为该人物的附加攻击力

输出描述

输入true或者false

true表示超出上限

false表示未超出上限

补充说明

最终伤害值上限不会超过int最大值

样例输入一

1 2

样例输出一

false

说明

最终伤害上限1

附加攻击力2

2=1+1

1*1=1

所以未超过上限

样例输入二

161 14

样例输出二

true

说明

14=3+3+3+3+2

3*3*3*3*2=162>161

所以超过上限

参考题解

动态规划

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

#include <iostream>
#include <cmath>
using namespace std;

long long solve(long long n) {
    if (n <= 3) {
        return n - 1;
    }
    long long quotient = n / 3;
    long long remainder = n % 3;
    if (remainder == 0) {
        return pow(3, quotient);
    } else if (remainder == 1) {
        return pow(3, quotient - 1) * 4;
    } else {
        return pow(3, quotient) * 2;
    }
}

int main() {
    long long limit, power;
    cin >> limit >> power;
    long long ans = solve(power);
    if (ans > limit) {
        cout << "true" << endl;
    } else {
        cout << "false" << endl;
    }
    return 0;
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long limit = scanner.nextLong();
        long power = scanner.nextLong();
        long ans = solve(power);
        if (ans > limit) {
            System.out.println("true");
        }
        else{
            System.out.println("false");
        }
    }

    static long solve(long n) {
        if (n <= 3) {
            return n - 1;
        }
        long quotient = n / 3;
        long remainder = n % 3;
        if (remainder == 0) {
            return (long) Math.pow(3, quotient);
        } else if (remainder == 1) {
            return (long) Math.pow(3, quotient - 1) * 4;
        } else {
            return (long) Math.pow(3, quotient) * 2;
        }
    }
}

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

limit, power = map(int, input().split())
dp = [-1]*(power+1)
def dfs(i):
    if i==2:return 1
    if dp[i]!=-1:return dp[i]
    res = 0
    for j in range(1,i//2+1):
        res = max(res, dfs(i-j)*j, j*(i-j))
    dp[i] = res
    return res

ans = dfs(power)
if ans > limit:
    print("true")
else:
    print("false")

第三题

题目：最佳工作任务安排

小友所在的部门在进行一系列复杂的开发项目。为了优化开发流程，部门要求工程师在不同的任务之间切换。每个任务有不同的执行时间，有些任务因为各种原因无法进行（标记为-1）。工程师可以在规定的跳跃范围内从一个任务跳到另一个任务，但每次执行任务需要消耗相应的时间。你的目标是找到一个从任务列表开头到结尾的执行顺序，使得总执行时间最小。如果存在多个总执行时间相同的顺序，返回按索引值更小优先的顺序。如果无法到达最后一个任务，返回一个空数组。

规则：

1.输入一个整数数组 tasks 表示任务执行时间，长度为 n。

2.输入一个整数 maxStep 表示单次切换任务的最大切换长度。

3.你从任务列表的第一个任务开始（tasks[0] 不是 -1）。

4.从任务 i 切换到任务 j，消耗的时间为 tasks[j]。

5.如果你当前位于任务 i，你只能跳到任务 i + k（满足 i + k <= n），其中 k 在范围 [1, maxStep] 内。

6.返回一个整数数组，包含你访问的任务索引顺序，使得总执行时间最小。如果存在多个总执行时间相同的顺序，返回索引值更小的顺序。

排序说明：

如果存在多个总执行时间相同的顺序：

假设方案 p1 = [Pa1, Pa2, ..., Pax] 和方案 p2 = [Pb1, Pb2, ..., Pbx]。

如果在两个方案中第一个不同的索引 j 处，Pa[j] 小于 Pb[j]，则选择方案 p1。

如果所有索引都相同，但任务切换次数不同，则选择任务切换次数较少的一个方案。

提示：注意排序规则，如 1-2-3-4-5 和 1-4-5 , 假设两个方案所消耗的时间成本相同, 那么前面的方案更优。

输入描述

整数 N，代表任务 tasks 的长度

长度为 N 的数组 tasks 的各个元素

整数 M，代表每次切换任务的最大跳跃长度

输出描述

输出数组，代表总执行时间最短，并且索引值最小的执行方案。

补充说明：

1 <= tasks.length <= 1000

-1 <= tasks[i] <= 100

tasks[0] != -1

1 <= maxStep <= 100

样例输入一

5

1 2 4 -1 2

2

样例输出一

1 3 5

样例输入二

5

1 2 4 -1 2

1

样例输出二

[]

说明：

无法到达最后一个任务，输出字符串"[]"

参考题解

动态规划+路径回溯。

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

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

using namespace std;

int main() {
    // 读取输入
    int N, M;
    cin >> N;
    vector<int> task(N);
    for (int i = 0; i < N; ++i) {
        cin >> task[i];
    }
    cin >> M;

    // 初始化 dp 数组
    const int INF = INT_MAX; // 使用 INT_MAX 代替 inf
    vector<int> f(N, INF);
    f[0] = 0;
    vector<int> fm(N, -1);

    // 动态规划
    for (int i = 1; i < N; ++i) {
        if (task[i] == -1) continue;
        for (int k = 1; k <= M; ++k) {
            if (i - k < 0) break;
            if (f[i - k] + task[i] < f[i] && task[i - k] != -1) {
                f[i] = f[i - k] + task[i];
                fm[i] = i - k;
            }
        }
    }

    // 回溯找到路径
    vector<int> res;
    int index = N - 1;
    while (true) {
        if (index == 0) {
            res.push_back(1);
            break;
        }
        res.push_back(index + 1);
        index = fm[index];
    }

    // 反转并输出结果
    reverse(res.begin(), res.end());
    for (int r : res) {
        cout << r << " ";
    }

    return 0;
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int N = scanner.nextInt();
        int[] task = new int[N];
        for (int i = 0; i < N; i++) {
            task[i] = scanner.nextInt();
        }
        int M = scanner.nextInt();
        
        // 初始化 dp 数组
        final int INF = Intege