米哈游笔试 米哈游笔试题 0907
笔试时间：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:
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2024 BAT笔试合集 文章被收录于专栏
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解，包含python、C++、Java多种语言版本，持续更新中。
查看16道真题和解析