【笔试刷题】美团-2026.03.14-研发岗-改编真题
✅ 春招备战指南 ✅
💡 学习建议：
- 先尝试独立解题
- 对照解析查漏补缺
🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。
🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力
🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的
春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗
美团-2026.03.14-研发岗
这套 3.14 美团暑期实习研发岗题的梯度比较顺。第一题是标准数学结论题，核心在于看出“因子数为奇数”等价于“完全平方数”；第二题把递推式改写成前缀和差，属于很典型的优化型动态规划；第三题则是整套题的分水岭，关键不在并查集本身，而在于能不能意识到“删边要逆序做”。
题目一：区间平方因子扫描
这题表面像数论枚举，但真正要抓的是结论。只要明白因子通常成对出现，只有完全平方数会把中间那个因子单独留下，题目就能直接化成区间平方数计数。
题目二：k阶和式递推查询
题意本身不难，难点在于不能按定义傻算前 k 项和。把 k 阶递推改写成前缀和差以后，每一项都能做到 O(1) 转移，整题就落成了线性预处理加离线回答查询。
题目三：断边图连通峰值
这题最容易卡在“删边之后连通块会分裂”这一点。正着做并查集完全不顺，反过来以后就清楚了：删边变加边，点权也只会单调增加，于是只要在逆序过程中维护连通块最大值即可。
01. 区间平方因子扫描
问题描述
小美很喜欢研究数字的因子。
如果正整数 p 可以整除正整数 x，那么称 p 是 x 的一个因子。例如 12 的因子有 1, 2, 3, 4, 6, 12。
现在给定一个区间 [l, r]，请你计算这个区间里有多少个数的因子数量是奇数。
输入格式
输入一行，包含两个整数 l 和 r。
输出格式
输出一个整数，表示区间 [l, r] 中因子数量为奇数的数的个数。
样例输入 1
1 1
样例输出 1
1
样例说明 1
区间中只有数字 1，它只有一个因子，因此答案是 1。
样例输入 2
4 5
样例输出 2
1
样例说明 2
4 的因子有 1, 2, 4，一共 3 个；5 的因子有 1, 5，一共 2 个。
所以区间中只有 4 满足条件，答案是 1。
数据范围
1 <= l <= r <= 10^9
题解
这题最重要的不是枚举因子，而是先看“为什么因子数量会是奇数”。
通常情况下，因子都会成对出现：
- 如果
d是x的因子，那么x / d也是x的因子。 - 这两个因子一般是不同的，所以会一对一对地贡献。
只有一种情况例外：这两个因子恰好相等。
也就是：
d = x / d
等价于：
d^2 = x
这说明，只有当 x 是完全平方数时，因子个数才会是奇数。
于是题目就被转化成一个非常直接的问题：
- 统计区间
[l, r]中完全平方数的个数。
设：
cnt(r)表示不超过r的完全平方数个数。
那么显然有：
cnt(r) = floor(sqrt(r))
因为 1^2, 2^2, 3^2, ..., floor(sqrt(r))^2 都不超过 r。
最终答案就是：
floor(sqrt(r)) - floor(sqrt(l - 1))
实现时需要注意一个小细节：直接调用浮点 sqrt 之后，可能因为精度问题出现偏差，所以最好在取整后再向上、向下各修正几次。
时间复杂度是 O(1)，空间复杂度是 O(1)。
参考代码
- Python
import math
import sys
input = lambda: sys.stdin.readline().strip()
def isqrt_floor(x: int) -> int:
# Python 直接使用整数平方根，避免浮点误差。
return math.isqrt(x)
def solve() -> None:
l, r = map(int, input().split())
# 区间内完全平方数个数 = 前缀个数做差。
ans = isqrt_floor(r) - isqrt_floor(l - 1)
print(ans)
if __name__ == "__main__":
solve()
- Cpp
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
static int64 isqrt_floor(int64 x) {
// 先用长双精度开方，再做微调，避免边界误差。
int64 y = sqrtl((long double)x);
while ((y + 1) * (y + 1) <= x) {
++y;
}
while (y * y > x) {
--y;
}
return y;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int64 l, r;
cin >> l >> r;
// 前缀平方数个数做差即可。
cout << isqrt_floor(r) - isqrt_floor(l - 1) << '\n';
return 0;
}
- Java
import java.io.BufferedInputStream;
import java.io.IOException;
public class Main {
private static class FastScanner {
private final BufferedInputStream in = new BufferedInputStream(System.in);
private final byte[] buf = new byte[1 << 16];
private int len = 0;
private int ptr = 0;
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buf);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buf[ptr++];
}
long nextLong() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
long sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
long val = 0;
while (c > ' ') {
val = val * 10 + c - '0';
c = read();
}
return val * sign;
}
}
private static long isqrtFloor(long x) {
long y = (long) Math.sqrt(x);
// 修正浮点误差，保证返回 floor(sqrt(x))。
while ((y + 1) * (y + 1) <= x) {
y++;
}
while (y * y > x) {
y--;
}
return y;
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner();
long l = fs.nextLong();
long r = fs.nextLong();
long ans = isqrtFloor(r) - isqrtFloor(l - 1);
System.out.println(ans);
}
}
02. k阶和式递推查询
问题描述
定义超级斐波那契数列如下：
- 前
k项都等于1。 - 当
n > k时，有：
S_n = S_{n-1} + S_{n-2} + ... + S_{n-k}
现给定整数 k 和查询次数 q，每次查询一个正整数 x，请你输出该序列第 x 项的值。
由于答案可能很大，请对 10^9 + 7 取模后输出。
输入格式
第一行输入两个整数 k 和 q。
接下来 q 行，每行输入一个正整数 x，表示一次询问。
输出格式
输出 q 行。
对于每次询问，输出对应的 S_x mod (10^9 + 7)。
样例输入
2 5
1
2
3
4
5
样例输出
1
1
2
3
5
数据范围
1 <= k <= 10^61 <= q <= 2 * 10^51 <= x <= 10^6
题解
这题如果直接照着定义递推，会很容易写成：
- 求
S_n时，把S_{n-1}到S_{n-k}全部加一遍。
这样单次转移是 O(k)，总复杂度会到 O(maxX * k)，肯定扛不住。
真正的关键，是把“前 k 项之和”改写成前缀和差。
设：
pre[i] = S_1 + S_2 + ... + S_i
那么对于 n > k：
S_n = S_{n-1} + S_{n-2} + ... + S_{n-k}
这一段正好就是：
S_n = pre[n - 1] - pre[n - k - 1]
这样一来，每求一个新位置，就不需要再循环加 k 次，而是只做一次减法。
整个流程如下：
- 先把所有询问读进来，并求出最大的查询值
maxX。 - 只预处理到
maxX，不用多算。 - 前
k项都直接赋值为1。 - 从第
k + 1项开始，用前缀和公式做O(1)转移。 - 按输入顺序输出每个查询结果。
注意两个边界：
- 当
i <= k时，答案固定是1。 - 取模减法时要防止负数，所以写成
(a - b + MOD) % MOD更稳。
时间复杂度是 O(maxX + q)，空间复杂度是 O(maxX)。
参考代码
- Python
import sys
MOD = 10**9 + 7
input = lambda: sys.stdin.readline().strip()
def solve():
k, q = map(int, input().split())
queries = [int(input()) for _ in range(q)]
max_x = max(queries)
# f[i] 表示第 i 项，pre[i] 表示前 i 项和。
f = [0] * (max_x + 1)
pre = [0] * (max_x + 1)
for i in range(1, max_x + 1):
if i <= k:
f[i] = 1
else:
left = pre[i - k - 1] if i - k - 1 >= 0 else 0
# 用前缀和差快速得到前 k 项之和。
f[i] = (pre[i - 1] - left) % MOD
pre[i] = (pre[i - 1] + f[i]) % MOD
print("\n".join(str(f[x]) for x in queries))
if __name__ == "__main__":
solve()
- Cpp
#include <bits/stdc++.h>
using namespace std;
static const long long MOD = 1000000007LL;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k, q;
cin >> k >> q;
vector<int> queries(q);
int max_x = 0;
for (int i = 0; i < q; ++i) {
cin >> queries[i];
max_x = max(max_x, queries[i]);
}
// f[i] 表示第 i 项，pre[i] 表示前 i 项和。
vector<long long> f(max_x + 1, 0), pre(max_x + 1, 0);
for (int i = 1; i <= max_x; ++i) {
if (i <= k) {
f[i] = 1;
} else {
long long left = (i - k - 1 >= 0 ? pre[i - k - 1] : 0);
// S_i = pre[i-1] - pre[i-k-1]
f[i] = (pre[i - 1] - left + MOD) % MOD;
}
pre[i] = (pre[i - 1] + f[i]) % MOD;
}
for (int x : queries) {
cout << f[x] << '\n';
}
return 0;
}
- Java
import java.io.BufferedInputStream;
import java.io.IOException;
public class Main {
static final long MOD = 1_000_000_007L;
static class FastScanner {
private final BufferedInputStream in = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int len = 0;
private int ptr = 0;
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value * sign;
}
}
public static void main(String[] args) throws Exception {
FastScanne剩余60%内容，订阅专栏后可继续查看/也可单篇购买
互联网刷题笔试宝典，这里涵盖了市面上大部分的笔试题合集，希望助大家春秋招一臂之力
