25届-9.07miha游改编题
💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历
👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸
✨ 合集传送们 -> 🧷学长刷题笔记
🍒 本专栏已收集
140+套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞
🍠 米哈游秋招笔试，来啦！！！
🍥 本次米哈游难度不大哦，相比于去年秋招，没有那种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
解题思路如下：
-
对于每个关卡，都有三种选择。需要尝试所有可能的选择组合。
-
使用DFS遍历所有可能的选择路径。在每个关卡，都尝试选择三个导师中的一个。
-
在DFS过程中，需要记录以下信息：
- 当前累积的魔法能量值
- 每位导师被选择的次数
-
当遍历完所有关卡后，检查是否有导师被选择了3次或以上。如果有，加上这些导师的额外礼物能量值。
-
更新最大魔法能量值。
-
回溯，尝试其他可能的选择路径。
时间复杂度分析：
- 每个关卡有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开始
int energy_gain = levels[pos]剩余60%内容，订阅专栏后可继续查看/也可单篇购买
这里收集了超全的刷题笔记，欢迎大家的订阅，会持续跟新的
点点互动二面9人在聊
投递米哈游等公司10个岗位