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

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

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

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

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

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

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

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

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

🍥 本次米哈游难度不大哦，相比于去年秋招，没有那种ex的概率dp了，舒服！！！

1️⃣ 枚举每个可能

2️⃣ DFS暴力搜索

3️⃣ 经典问题 flood fill 洪水灌溉问题的拓展版，DFS/BFS/并查集都是可以做的

🎲 01.LYA的幸运数字

问题描述

LYA 是一位数字艺术家，她对数字 4 和 6 有特殊的偏爱。最近，她接到了一个特殊的艺术项目，需要在一个给定的数字范围内找出最"幸运"的数字。

在 LYA 的定义中，一个数字的"幸运度"取决于它包含的 4 和 6 的总数。例如，数字 46164 的幸运度为 4（两个 4 和两个 6）。

现在，LYA 需要在给定的范围 内找出幸运度最高的数字。如果有多个数字的幸运度相同且最高，她会选择其中最大的数字作为最终的幸运数字。

输入格式

输入包含一行，有两个正整数 和 （）。

输出格式

输出一行，包含一个整数，表示 LYA 找到的最幸运数字。

样例输入

40 50

样例输出

46

样例输入

12 13

样例输出

13

样例输入

100 200

样例输出

166

数据范围

题解

枚举，由于 和 比较小， 从后往前暴力枚举统计

时间复杂度 ， 表示数位的长度

tips 思考：如果 怎么做

参考代码

• Python

# 读取输入
n, m = map(int, input().split())

max_lucky = 0  # 最大幸运度
result = 0     # 最幸运的数字

# 从大到小遍历范围内的数字
for num in range(m, n-1, -1):
    lucky_count = 0
    temp = num
    
    # 统计数字中4和6的个数
    while temp > 0:
        digit = temp % 10
        if digit == 4 or digit == 6:
            lucky_count += 1
        temp //= 10
    
    # 更新最大幸运度和结果
    if lucky_count > max_lucky:
        max_lucky = lucky_count
        result = num

# 输出结果
print(result)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        
        int maxLucky = 0;  // 最大幸运度
        int result = 0;    // 最幸运的数字
        
        // 从大到小遍历范围内的数字
        for (int num = m; num >= n; num--) {
            int luckyCount = 0;
            int temp = num;
            
            // 统计数字中4和6的个数
            while (temp > 0) {
                int digit = temp % 10;
                if (digit == 4 || digit == 6) {
                    luckyCount++;
                }
                temp /= 10;
            }
            
            // 更新最大幸运度和结果
            if (luckyCount > maxLucky) {
                maxLucky = luckyCount;
                result = num;
            }
        }
        
        // 输出结果
        System.out.println(result);
        
        scanner.close();
    }
}

• Cpp

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    int max_lucky = 0;  // 最大幸运度
    int result = 0;     // 最幸运的数字
    
    // 从大到小遍历范围内的数字
    for (int num = m; num >= n; num--) {
        int lucky_count = 0;
        int temp = num;
        
        // 统计数字中4和6的个数
        while (temp > 0) {
            int digit = temp % 10;
            if (digit == 4 || digit == 6) {
                lucky_count++;
            }
            temp /= 10;
        }
        
        // 更新最大幸运度和结果
        if (lucky_count > max_lucky) {
            max_lucky = lucky_count;
            result = num;
        }
    }
    
    // 输出结果
    cout << result << endl;
    
    return 0;
}

🎀 02.LYA的魔法学院挑战

问题描述

LYA 正在参加魔法学院的毕业考试。考试共有 个关卡，每个关卡都有三位不同的魔法导师提供指导。学院里共有 位魔法导师。

在每个关卡中，LYA 可以选择接受其中一位导师的指导。每位导师的指导都能让 LYA 获得一定的魔法能量值。此外，如果 LYA 在整个考试过程中至少接受了某位导师三次指导，那么这位导师会额外赐予 LYA 一份魔法礼物，进一步提升她的魔法能量。

LYA 想知道，通过合理选择每个关卡的指导导师，她最多能获得多少魔法能量值。

输入格式

第一行包含两个整数 和 （），分别表示关卡数量和魔法导师数量。

第二行包含 个整数 （），表示每位魔法导师的额外礼物所能提供的魔法能量值。

接下来的 行描述每个关卡的情况：

• 第一行包含三个整数 （），表示三位导师指导所能获得的魔法能量值。
• 第二行包含三个整数 （），表示这三位导师的编号。保证这三个数字互不相同。

输出格式

输出一个整数，表示 LYA 最多能获得的魔法能量值总和。

样例输入

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

数据范围

题解

DFS

解题思路如下：

1. 对于每个关卡，都有三种选择。需要尝试所有可能的选择组合。

2. 使用DFS遍历所有可能的选择路径。在每个关卡，都尝试选择三个导师中的一个。

3. 在DFS过程中，需要记录以下信息：

   • 当前累积的魔法能量值
   • 每位导师被选择的次数

4. 当遍历完所有关卡后，检查是否有导师被选择了3次或以上。如果有，加上这些导师的额外礼物能量值。

5. 更新最大魔法能量值。

6. 回溯，尝试其他可能的选择路径。

时间复杂度分析：

• 每个关卡有3种选择，共有n个关卡
• 总的搜索空间是
• 由于 ，，这个规模的搜索空间是可以在短时间内完成的

参考代码

• Python

def dfs(pos, energy, choices):
    global max_energy, n, m, rewards, levels
    
    # 基本情况：已经处理完所有关卡
    if pos == n:
        # 计算额外奖励
        bonus = sum(rewards[i] for i in range(m) if choices[i] >= 3)
        max_energy = max(max_energy, energy + bonus)
        return
    
    # 尝试选择当前关卡的三个导师之一
    for i in range(3):
        mentor = levels[pos][1][i] - 1  # 导师编号从0开始
        energy_gain = levels[pos][0][i]
        
        # 选择这个导师
        choices[mentor] += 1
        dfs(pos + 1, energy + energy_gain, choices)
        # 回溯
        choices[mentor] -= 1

# 读取输入
n, m = map(int, input().split())
rewards = list(map(int, input().split()))
levels = []
for _ in range(n):
    energy = list(map(int, input().split()))
    mentors = list(map(int, input().split()))
    levels.append((energy, mentors))

max_energy = 0
dfs(0, 0, [0] * m)

# 输出结果
print(max_energy)

• Java

import java.util.Scanner;

public class Main {
    static int n, m;
    static int[] rewards;
    static int[][][] levels;
    static int maxEnergy = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        n = scanner.nextInt();
        m = scanner.nextInt();
        
        rewards = new int[m];
        for (int i = 0; i < m; i++) {
            rewards[i] = scanner.nextInt();
        }
        
        levels = new int[n][2][3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                levels[i][0][j] = scanner.nextInt();
            }
            for (int j = 0; j < 3; j++) {
                levels[i][1][j] = scanner.nextInt() - 1;  // 导师编号从0开始
            }
        }
        
        // 开始DFS
        dfs(0, 0, new int[m]);
        
        // 输出结果
        System.out.println(maxEnergy);
    }
    
    static void dfs(int pos, int energy, int[] choices) {
        // 基本情况：已经处理完所有关卡
        if (pos == n) {
            // 计算额外奖励
            int bonus = 0;
            for (int i = 0; i < m; i++) {
                if (choices[i] >= 3) {
                    bonus += rewards[i];
                }
            }
            maxEnergy = Math.max(maxEnergy, energy + bonus);
            return;
        }
        
        // 尝试选择当前关卡的三个导师之一
        for (int i = 0; i < 3; i++) {
            int mentor = levels[pos][1][i];
            int energyGain = levels[pos][0][i];
            
            // 选择这个导师
            choices[mentor]++;
            dfs(pos + 1, energy + energyGain, choices);
            // 回溯
            choices[mentor]--;
        }
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> rewards;
vector<vector<pair<int, int>>> levels;
int max_energy = 0;

void dfs(int pos, int energy, vector<int>& choices) {
    // 基本情况：已经处理完所有关卡
    if (pos == n) {
        // 计算额外奖励
        int bonus = 0;
        for (int i = 0; i < m; i++) {
            if (choices[i] >= 3) {
                bonus += rewards[i];
            }
        }
        max_energy = max(max_energy, energy + bonus);
        return;
    }
    
    // 尝试选择当前关卡的三个导师之一
    for (int i = 0; i < 3; i++) {
        int mentor = levels[pos][i].second - 1;  // 导师编号从0开始