美团笔试 美团笔试题 0830
笔试时间：2025年8月30日
往年笔试合集：
第一题：小美的神秘运算2
小美有一个数字 n，小美打算按照以下规则对 n 进行操作：
如果 n 是偶数，让 n 除以 2；
否则，让 n 乘以 3 再加 1。
小美想知道，在操作 k 次后，n 会变成多少。
输入描述
输入一行两个整数 n,k，满足条件：
2 ≤ n ≤ 10¹⁸，0 ≤ k ≤ 10¹⁸
输出描述
输出 n 操作 k 次后的结果。
样例输入
100 10
样例输出
22
参考题解
对任意(n)按规则迭代，一旦到达(1)，后续进入长度为3的循环：1→4→2→1→…因此，当首次到达1后，剩余操作只取决于剩余步数对3取模。
C++：
#include <iostream>
using namespace std;
int main() {
int n, k;
// 读取输入n和k
cin >> n >> k;
// 核心变换循环：k>0且n≠1时执行
while (k > 0 && n != 1) {
if (n % 2 == 0) {
// 偶数：除以2（整数除法）
n /= 2;
} else {
// 奇数：变为3n+1
n = 3 * n + 1;
}
k--; // 每次变换后k减1
}
// 若仍有剩余k（n已为1），利用周期序列[1,4,2]计算
if (k > 0) {
int cycle[] = {1, 4, 2}; // 1的后续循环序列，周期3
int r = k % 3; // 取余数确定索引
n = cycle[r];
}
// 输出最终结果
cout << n << endl;
return 0;
}
Java：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入n和k
int n = scanner.nextInt();
int k = scanner.nextInt();
// 核心变换循环：k>0且n≠1时执行
while (k > 0 && n != 1) {
if (n % 2 == 0) {
// 偶数：除以2（整数除法）
n /= 2;
} else {
// 奇数：变为3n+1
n = 3 * n + 1;
}
k--; // 每次变换后k减1
}
// 若仍有剩余k（n已为1），利用周期序列[1,4,2]计算
if (k > 0) {
int[] cycle = {1, 4, 2}; // 1的后续循环序列，周期3
int r = k % 3; // 取余数确定索引
n = cycle[r];
}
// 输出最终结果
System.out.println(n);
scanner.close();
}
}
Python：
n, k = map(int, input().split()) while k > 0 and n != 1: if n % 2 == 0: n //= 2 else: n = 3*n + 1 k -= 1 if k > 0: r = k % 3 n = [1, 4, 2][r] print(n)
第二题：小美的有限小数
小美是一位数学爱好者，她想知道给定的有理数p/q在k进制下是否为一个有限小数。换句话说，她希望判断在基数为k的表示中，该分数的小数部分是否会在有限位后结束，而不是无限循环。例如，m½在十进制下表示为0.5，是有限小数；相比之下，1/3在十进制下表示为0.3（循环），不是有限小数。
输入描述
第一行输入一个整数T (1 ≤ T ≤ 10⁵)，表示测试数据的组数。
接下来T行，每行输入三个整数p,q,k (1 ≤ p,q ≤ 10¹⁸, 2 ≤ k ≤ 10¹⁸)，分别表示分子p、分母q和进制基数k。
输出描述
对于每一组测试数据，输出一行结果。若p/q在k进制下是有限小数，则输出yes；否则输出no。
样例输入
3
1 2 10
1 3 10
3 4 2
样例输出
yes
no
yes
参考题解
C++：
#include <bits/stdc++.h>
using namespace std;
long long gcdll(long long x, long long y) {
return std::gcd(x, y);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
while (T--) {
long long a, b, c;
cin >> a >> b >> c;
long long g = gcdll(a, b);
long long d = b / g;
if (c == 1) {
cout << (d == 1 ? "yes\n" : "no\n");
continue;
}
while (d > 1) {
long long t = gcdll(c, d);
if (t == 1) {
cout << "no\n";
goto next_case;
}
while (d % t == 0) d /= t;
}
cout << "yes\n";
next_case:
(void)0;
}
return 0;
}
Java：
import java.io.*;
import java.util.*;
public class Main {
static long gcd(long a, long b) {
while (b != 0) {
long t = a % b;
a = b;
b = t;
}
return Math.abs(a);
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null) return;
int T = Integer.parseInt(line.trim());
StringBuilder out = new StringBuilder();
for (int tc = 0; tc < T; tc++) {
StringTokenizer st;
while (true) {
line = br.readLine();
if (line == null) return; // unexpected EOF
line = line.trim();
if (!line.isEmpty()) break;
}
st = new StringTokenizer(line);
long a = Long.parseLong(st.nextToken());
long b = Long.parseLong(st.nextToken());
long c = Long.parseLong(st.nextToken());
long g = gcd(a, b);
long d = b / g;
if (c == 1) {
out.append(d == 1 ? "yes" : "no").append('\n');
continue;
}
boolean ok = true;
while (d > 1) {
long t = gcd(c, d);
if (t == 1) {
ok = false;
break;
}
while (d % t == 0) d /= t;
}
out.append(ok ? "yes" : "no").append('\n');
}
System.out.print(out.toString());
}
}
Python：
import sys, math
def work():
a, b, c = map(int, sys.stdin.readline().split())
g = math.gcd(a, b)
d = b // g
if1 == c:
print("yes"if1 == d else"no")
return
while d > 1:
t = math.gcd(c, d)
if1 == t:
print("no")
return
while d % t == 0:
d //= t
print("yes")
def main():
n = int(sys.stdin.readline())
i = 0
while i < n:
work()
i += 1
if __name__ == "__main__":
main()
第三题
给定一棵以节点1为根的有n个节点的树，每个节点i有一个正整数权值wᵢ，初始被涂成黑色或白色。你需要支持以下两种操作：
1. 翻转节点x的颜色（黑色变白色，白色变黑色）；
2. 查询从根节点1到节点x的路径上所有黑色节点的权值的最小公倍数（若路径上无黑色节点，则记为1）。
名词解释最小公倍数：最小公倍数是能够被给定整数集合中每个整数整除的最小正整数，记为lcm
输入描述
第一行输入两个整数n和q，1 ≤ n,q ≤ 2×10⁵，分别表示树的节点数量和操作数量。
第二行输入n个整数w₁,w₂,…,wₙ，1 ≤ wᵢ ≤ 100，分别表示节点1到节点n的权值。
第三行输入一个长度为n、仅由字符B和W构成的字符串c，其中cᵢ=B表示节点i初始化为黑色，cᵢ=W表示初始化为白色。
接下来n−1行，每行输入两个整数uᵢ和vᵢ（1 ≤ uᵢ,vᵢ ≤ n；uᵢ≠vᵢ），表示一条连接节点uᵢ和节点vᵢ的无向边。保证这n个节点构成一棵根为1的树。
接下来q行，每行输入两个整数t和x（t ∈ {1,2}, 1 ≤ x ≤ n），表示一次操作：
当t=1时，执行翻转操作；
当t=2时，执行查询操作。
输出描述
对于每次查询操作，输出一行结果。
样例输入
5 5
2 3 4 5 6
BWBWB
1 2
1 3
3 4
3 5
2 4
1 3
2 4
1 1
2 5
样例输出
4
2
6
说明：
在这个样例中，初始颜色为：
节点1→B；
节点2→W；
节点3→B；
节点4→W；
节点5→B。
1. 查询2 4：路径1−3−4上黑色节点为1,3，权值分别为2,4，lcm(2,4)=4
2. 翻转节点3后再次查询2 4：路径上仅剩节点1为黑色，lcm(2)=2
3. 再翻转节点1后第三次查询2 5：路径1−3−5上仅有节点5为黑色，lcm(6)=6
参考题解
C++：
#include <bits/stdc++.h>
using namespace std;
static const int MOD = 1000000007;
static const int MAXN = 200005;
static const int MAXW = 101;
static const int NUM_PRIMES = 25;
int n, q;
vector<int> adj[MAXN];
int w[MAXN];
bool is_black[MAXN];
// HLD arrays
int parent_[MAXN], depth_[MAXN], sz_[MAXN], heavy_[MAXN];
int dfn_[MAXN], top_[MAXN], rid_[MAXN], timer_ = 0;
// primes and factors up to 100
vector<int> primes;
int prime_idx[MAXW]; // map prime -> index [0..NUM_PRIMES)
vector<pair<int,int>> factors_[MAXW]; // factors for 1..100
// segment tree: each node stores an array<int,NUM_PRIMES> with max exponents
vector<array<int,NUM_PRIMES>> seg; // size 4*n
vector<array<int,NUM_PRIMES>> initial_; // size n+1
// ---------- utils ----------
long long modpow(long long a, long long e) {
long long r = 1 % MOD;
while (e) {
if (e & 1) r = (r * a) % MOD;
a = (a * a) % MOD;
e >>= 1;
}
return r;
}
array<int,NUM_PRIMES> merge_arr(const array<int,NUM_PRIMES>& A, const array<int,NUM_PRIMES>& B) {
array<int,NUM_PRIMES> C{};
for (int i = 0; i < NUM_PRIMES; ++i) C[i] = max(A[i], B[i]);
return C;
}
array<int,NUM_PRIMES> zero_arr() {
array<int,NUM_PRIMES> Z{};
for (int i = 0; i < NUM_PRIMES; ++i) Z[i] = 0;
return Z;
}
array<int,NUM_PRIMES> get_exponents(int x) {
array<int,NUM_PRIMES> res = zero_arr();
for (auto &pr : factors_[x]) {
int p = pr.first, e = pr.second;
int idx = prime_idx[p];
res[idx] = e;
}
return res;
}
// ---------- sieve & factor table ----------
void sieve_and_factors() {
vector<bool> siv(MAXW, true);
siv[0] = siv[1] = false;
memset(prime_idx, -1, sizeof(prime_idx));
for (int p = 2; p < MAXW; ++p) {
if (siv[p]) {
prime_idx[p] = (int)primes.size();
primes.push_back(p);
for (int i = p * p; i < MAXW; i += p) siv[i] = false;
}
}
// factors for 1..100
for (int i = 1; i < MAXW; ++i) {
int num = i;
for (int p : primes) {
if (1LL * p * p > num) break;
if (num % p == 0) {
int cnt = 0;
while (num % p == 0) { num /= p; ++cnt; }
factors_[i].push_back({p, cnt});
}
}
if (num > 1) factors_[i].push_back({num, 1});
}
}
// ---------- HLD ----------
int dfs1(int u, int p, int d) {
parent_[u] = p;
depth_[u] = d;
sz_[u] = 1;
heavy_[u] = 0;
int maxsz = 0;
for (int v : adj[u]) if (v != p) {
dfs1(v, u, d + 1);
sz_[u] += sz_[v];
if (sz_[v] > maxsz) {
maxsz = sz_[v];
heavy_[u] = v;
}
}
return sz_[u];
}
void dfs2(int u, int t) {
top_[u] = t;
dfn_[u] = ++timer_;
rid_[timer_] = u;
if (heavy_[u]) dfs2(heavy_[u], t);
for (int v : adj[u]) if (v != parent_[u] && v != heavy_[u]) {
dfs2(v, v);
}
}
// ---------- segment tree ----------
void seg_build(int p, int l, int r) {
if ((int)seg.size() == 0) return; // guard
if (l == r) {
seg[p] = initial_[l];
return;
}
int m = (l + r) >> 1;
seg_build(p<<1, l, m);
seg_build(p<<1|1, m+1, r);
seg[p] = merge_arr(seg[p<<1], seg[p<<1|1]);
}
void seg_update(int p, int l, int r, int pos, const array<int,NUM_PRIMES>& val) {
if (l == r) { seg[p] = val; return; }
int m = (l + r) >> 1;
if (pos <= m) seg_update(p<<1, l, m, pos, val);
else seg_update(p<<1|1, m+1, r, pos, val);
seg[p] = merge_arr(seg[p<<1], seg[p<<1|1]);
}
array<int,NUM_PRIMES> seg_query(int p, int l, int r, int ql, int qr) {
if (ql > qr) return zero_arr();
if (ql <= l && r <= qr) return seg[p];
int m = (l + r) >> 1;
array<int,NUM_PRIMES> L = zero_arr(), R = zero_arr();
if (ql <= m) L = seg_query(p<<1, l, m, ql, qr);
if (qr > m) R = seg_query(p<<1|1, m+1, r, ql, qr);
return m
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025 春招笔试合集 文章被收录于专栏
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
投递哔哩哔哩等公司10个岗位