美团笔试 美团笔试题 0405
笔试时间：2025年04月05日
历史笔试传送门：
第一题
题目：整数转变
开始有一个整数b ，你需要经过若干次操作，使n 的值不小于m 。 操作一：将n 更改为2 * n ，花费为 w2 ； 操作二：将 n 更改为3 * n ，花费为w3 。 请输出需要的最小花费。
输入描述
输入第一行一个整数T，代表接下来有 T 组测试数据。
接下来 T 行，每行有 4 个整数 n,m,w2,w31< T < 100001< n,m< 2^{31}-11< w_2,w_3 < 1000
输出描述
对于每组测试数据，输出一行，一个整数代表最小花费。
样例输入
4
1 6 2 3
4 32 3 4
2 1 1 2
1 2147483647 1 4
样例输出
5
8
0
31
参考题解
记忆化搜索。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
unordered_map<int, int> dp;
int m, w2, w3;
int dfs(int i) {
if (i >= m) return 0;
if (dp.count(i)) return dp[i];
int cost2 = dfs(i * 2) + w2;
int cost3 = dfs(i * 3) + w3;
dp[i] = min(cost2, cost3);
return dp[i];
}
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n >> m >> w2 >> w3;
dp.clear();
cout << dfs(n) << endl;
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
static Map<Integer, Integer> dp;
static int m, w2, w3;
static int dfs(int i) {
if (i >= m) return 0;
if (dp.containsKey(i)) return dp.get(i);
int cost2 = dfs(i * 2) + w2;
int cost3 = dfs(i * 3) + w3;
int res = Math.min(cost2, cost3);
dp.put(i, res);
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int n = sc.nextInt();
m = sc.nextInt();
w2 = sc.nextInt();
w3 = sc.nextInt();
dp = new HashMap<>();
System.out.println(dfs(n));
}
sc.close();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
T = int(input())
for _ in range(T):
n, m, w2, w3 = map(int, input().split())
dp = {}
def dfs(i):
if i >= m: return 0
if i in dp: return dp[i]
dp[i] = min(dfs(i * 2) + w2, dfs(i * 3) + w3)
return dp[i]
print(dfs(n))
第二题
题目：漂亮数
我们定义一个漂亮数是这样的数：1、该数为正整数2、设该数为x，存在一个质数p使得x mod p = 0 且 p * p >= x给你一个正整数n，你能否求出有多少漂亮数小于等于n？
输入描述
输入一行一个正整数n(1< n< 5 * 10^6)。
输出描述
输出一行一个正整数，代表小于等于n的漂亮数的个数。
样例输入
10
样例输出
8
参考题解
筛质数基于最小质因数，递推计算每个数的最大质因数。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> min_prime(n + 1, 0); // 最小质因数
vector<int> primes;
// 欧拉筛法
for (int i = 2; i <= n; ++i) {
if (min_prime[i] == 0) {
min_prime[i] = i;
primes.push_back(i);
}
for (int p : primes) {
if (p > min_prime[i] || i * p > n) break;
min_prime[i * p] = p;
}
}
int count = 0;
vector<int> max_prime(n + 1, 0); // 最大质因数
for (int x = 2; x <= n; ++x) {
if (min_prime[x] == x) {
max_prime[x] = x;
count++;
} else {
int p = min_prime[x];
int m = x / p;
max_prime[x] = max(p, max_prime[m]);
if (1LL * max_prime[x] * max_prime[x] >= x) {
count++;
}
}
}
cout << count << endl;
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] minPrime = new int[n + 1];
List<Integer> primes = new ArrayList<>();
// 欧拉筛法
for (int i = 2; i <= n; i++) {
if (minPrime[i] == 0) {
minPrime[i] = i;
primes.add(i);
}
for (int p : primes) {
if (p > minPrime[i] || i * p > n) break;
minPrime[i * p] = p;
}
}
int count = 0;
int[] maxPrime = new int[n + 1];
for (int x = 2; x <= n; x++) {
if (minPrime[x] == x) {
maxPrime[x] = x;
count++;
} else {
int p = minPrime[x];
int m = x / p;
maxPrime[x] = Math.max(p, maxPrime[m]);
if ((long) maxPrime[x] * maxPrime[x] >= x) {
count++;
}
}
}
System.out.println(count);
sc.close();
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
n = int(input()) max_n = n min_prime = [0] * (max_n + 1) # 最小质因数数组 primes = [] # 欧拉筛法预处理最小质因数 for i in range(2, max_n + 1): if min_prime[i] == 0: min_prime[i] = i primes.append(i) for p in primes: if p > min_prime[i] or i * p > max_n: break min_prime[i * p] = p count = 0 max_prime = [0] * (max_n + 1) # 最大质因数数组 for x in range(2, max_n + 1): if min_prime[x] == x: # x是质数 max_prime[x] = x count += 1 else: # x是合数 p = min_prime[x] m = x // p max_prime[x] = max(p, max_prime[m]) if max_prime[x] * max_prime[x] >= x: count += 1 print(count)
第三题
题目：最长路径
游游很喜欢树，这一天他在研究树上的路径，他遇到了一个难题，现在邀请你帮助他解决该问题。在一棵树上，两个点并不一定能确定一条链，但是可以找到一条经过这两个点最长的一条链。你有一棵 n 个点的树，树上每条边都有一个权值，定义一条简单路径的长度为这条简单路径上的边权和，对于给定的两个点 x, y，你需要回答在树上经过这两个点的最长简单路径是多少。【树上的路径】从节点 u 到节点 v 的简单路径定义为从节点 u 出发，以节点 v 为终点，随意在树上走，不经过重复的点和边走出来的序列。可以证明，在树上，任意两个节点间有且仅有一条简单路径。
输入描述
第一行两个数 n, m (1< n, m < 10^5)。
接下来
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
投递美团等公司9个岗位 >
字节跳动三面491人在聊