笔试时间：2024年09月07日 秋招

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

第一题

题目

给定两个正整数n,m，米小游想要求出n-m中的所有整数的哪个数字中4的数量加上 6 的数量最多。如果有多个这样的数字，请输出最大的。例如某一个数字是 44624，则它有3个4，1个6，所以4和6的数量之和为 4。

输入描述

输入仅包含一行共两个正整数n,m。

输出描述

输出一行一个整数表示答案。

样例输入一

40 50

样例输出一

46

样例输入二

12 13

样例输出二

13

说明

2 和 13 中 4 的个数和 6 的个数加起来都是 0，所以输出较大的数字 13。

参考题解

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

#include <iostream>

using namespace std;

// 计算一个数字中4和6的数量
int countFourAndSix(int num) {
    int count = 0;
    while (num > 0) {
        int digit = num % 10;
        if (digit == 4 || digit == 6) {
            count++;
        }
        num /= 10;
    }
    return count;
}

int main() {
    int n, m;
    cin >> n >> m;

    // 记录最大4和6的数量以及对应的数字
    int maxCount = -1;
    int result = n;

    // 遍历n到m范围内的所有数字
    for (int i = n; i <= m; i++) {
        int count = countFourAndSix(i);

        // 如果找到更多的4和6的数量，或者相同数量时取较大的数字
        if (count > maxCount || (count == maxCount && i > result)) {
            maxCount = count;
            result = i;
        }
    }

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

    return 0;
}

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

import java.util.Scanner;

public class Main {
    // 计算一个数字中4和6的数量
    public static int countFourAndSix(int num) {
        int count = 0;
        while (num > 0) {
            int digit = num % 10;
            if (digit == 4 || digit == 6) {
                count++;
            }
            num /= 10;
        }
        return count;
    }

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

        // 读取输入
        int n = in.nextInt();
        int m = in.nextInt();

        // 记录最大4和6的数量以及对应的数字
        int maxCount = -1;
        int result = n;

        // 遍历n到m范围内的所有数字
        for (int i = n; i <= m; i++) {
            int count = countFourAndSix(i);

            // 如果找到更多的4和6的数量，或者相同数量时取较大的数字
            if (count > maxCount || (count == maxCount && i > result)) {
                maxCount = count;
                result = i;
            }
        }

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

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

def count_four_and_six(num):
    # 计算一个数字中4和6的数量
    count = 0
    while num > 0:
        digit = num % 10
        if digit == 4 or digit == 6:
            count += 1
        num //= 10
    return count

if __name__ == "__main__":
    n, m = map(int, input().split())

    # 记录最大4和6的数量以及对应的数字
    max_count = -1
    result = n

    # 遍历n到m范围内的所有数字
    for i in range(n, m + 1):
        count = count_four_and_six(i)

        # 如果找到更多的4和6的数量，或者相同数量时取较大的数字
        if count > max_count or (count == max_count and i > result):
            max_count = count
            result = i

    # 输出结果
    print(result)

第二题

题目

米小游正在挑战往事乐土，往事乐土中有n个关卡，m位英桀，挑战完每个关卡后可以在三位不同英桀给出的奖励中选择一个，每个奖励的能力值为ai，来源为第bi位英桀。若米小游至少获得了三个来源为同一位英桀的奖励，她可以获得来自这位英桀的额外奖励，能力值为ci。米小游想知道，她挑战完这n个关卡最多可以获得多少能力值？

输入描述

第一行输入两个整数n,m，表示关卡数量，英桀数量.

第二行输入 m 个整数ci，表示每位英桀的额外奖励。

接下来对于每一个关卡: 第一行输入三个整数，表示奖励的能力值, 第二行输入三个整数 ，表示奖励的来源，保证三个数字互不相同。

输出描述

输出一个整数表示答案。

样例输入

4 13

0 1111 525 1031 55 0 0 722 0 430 1221 29 711

9 5 3

3 2 4

2 3 7

2 11 5

4 0 6

10 2 13

10 5 196

1 12 8

样例输出

1314

说明

在第1个关卡中，选择第2位英桀的奖励，获得5点能力值; 在第2个关卡中，选择第2位英桀的奖励，获得2点能力值; 在第3个关卡中，选择第2位英桀的奖励，获得0点能力值; 此时米小游获得了3个第2位英桀的奖励，额外获得了1111点能力值， 在第4个关卡中，选择第8位英桀的奖励，获得196点能力值， 最后的能力值为:5+2+0+1111+196=1314。

参考题解

回溯。

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

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

using namespace std;

int n, m; // 关卡数量、英桀数量
vector<int> c; // 每个英桀的额外奖励
vector<vector<int>> rewards; // 每个关卡的三个奖励的能力值
vector<vector<int>> sources; // 每个关卡的三个奖励对应的英桀来源
vector<int> chosen; // 记录每个英桀被选择的次数
int maxResult = 0; // 记录最大的能力值

// 回溯法函数，用于探索所有可能的奖励选择路径
void dfs(int level, int currentSum) {
    if (level == n) {
        // 已经完成了所有关卡，计算最终的能力值
        int extraBonus = 0;
        for (int i = 0; i < m; i++) {
            if (chosen[i] >= 3) {
                extraBonus += c[i]; // 加上额外奖励
            }
        }
        maxResult = max(maxResult, currentSum + extraBonus); // 更新最大值
        return;
    }

    // 尝试选择每个关卡的三个奖励之一
    for (int i = 0; i < 3; i++) {
        int rewardValue = rewards[level][i];
        int rewardSource = sources[level][i] - 1; // 英桀编号从 1 开始，转换为 0 开始
        chosen[rewardSource]++;
        dfs(level + 1, currentSum + rewardValue); // 继续处理下一个关卡
        chosen[rewardSource]--; // 回溯撤销选择
    }
}

int main() {
    cin >> n >> m;

    // 输入每位英桀的额外奖励
    c.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> c[i];
    }

    // 初始化关卡的奖励和来源
    rewards.resize(n, vector<int>(3));
    sources.resize(n, vector<int>(3));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> rewards[i][j]; // 奖励的能力值
        }
        for (int j = 0; j < 3; j++) {
            cin >> sources[i][j]; // 奖励的来源英桀
        }
    }

    // 初始化被选择次数的数组
    chosen.resize(m, 0);

    // 使用回溯算法搜索所有可能的选择组合
    dfs(0, 0);

    // 输出最大结果
    cout << maxResult << endl;

    return 0;
}

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

import java.util.Scanner;

public class Main {
    static int n, m; // 关卡数量、英桀数量
    static int[] c; // 每个英桀的额外奖励
    static int[][] rewards; // 每个关卡的三个奖励的能力值
    static int[][] sources; // 每个关卡的三个奖励对应的英桀来源
    static int[] chosen; // 记录每个英桀被选择的次数
    static int maxResult = 0; // 记录最大的能力值

    // 回溯法函数，用于探索所有可能的奖励选择路径
    public static void dfs(int level, int currentSum) {
        if (level == n) {
            // 已经完成了所有关卡，计算最终的能力值
            int extraBonus = 0;
            for (int i = 0; i < m; i++) {
                if (chosen[i] >= 3) {
                    extraBonus += c[i]; // 加上额外奖励
                }
            }
            maxResult = Math.max(maxResult, currentSum + extraBonus); // 更新最大值
            return;
        }

        // 尝试选择每个关卡的三个奖励之一
        for (int i = 0; i < 3; i++) {
            int rewardValue = rewards[level][i];
            int rewardSource = sources[level][i] - 1; // 英桀编号从 1 开始，转换为 0 开始
            chosen[rewardSource]++;
            dfs(level + 1, currentSum + rewardValue); // 继续处理下一个关卡
            chosen[rewardSource]--; // 回溯撤销选择
        }
    }

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

        // 输入关卡数量和英桀数量
        n = in.nextInt();
        m = in.nextInt();

        // 输入每位英桀的额外奖励
        c = new int[m];
        for (int i = 0; i < m; i++) {
            c[i] = in.nextInt();
        }

        // 初始化关卡的奖励和来源
        rewards = new int[n][3];
        sources = new int[n][3];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                rewards[i][j] = in.nextInt(); // 奖励的能力值
            }
            for (int j = 0; j < 3; j++) {
                sources[i][j] = in.nextInt(); // 奖励的来源英桀
            }
        }

        // 初始化被选择次数的数组
        chosen = new int[m];

        // 使用回溯算法搜索所有可能的选择组合
        dfs(0, 0);

        // 输出最大结果
        System.out.println(maxResult);

        in.close();
    }
}

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

def dfs(level, current_sum):
    global max_result
    if level == n: