程序员基德

今天 14:03 中国科学技术大学 C++ 发布于浙江

关注

【笔试刷题】美团-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。

样例输入 2

4 5

样例输出 2

样例说明 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()

#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)。

样例输入

样例输出

数据范围

1 <= k <= 10^6
1 <= q <= 2 * 10^5
1 <= 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()

#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%内容，订阅专栏后可继续查看/也可单篇购买

互联网刷题笔试宝典文章被收录于专栏

互联网刷题笔试宝典，这里涵盖了市面上大部分的笔试题合集，希望助大家春秋招一臂之力