米哈游笔试 米哈游笔试题 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%内容,订阅专栏后可继续查看/也可单篇购买
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。