今天 00:00 香港大学推荐算法发布于上海

关注

美团笔试美团笔试题 20260314

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

笔试时间：2026年3月14日

第1题 - 小美的因子数量

题目

小美很喜欢因子数量为奇数的数。现在小芳给了小美一个区间 $[l, r]$ ，请你帮小美算出区间内有多少个因子数量为奇数的数。

【名词解释】因子：对于正整数 $n$ ，如果存在正整数 $k$ 使得 $n$ 能被 $k$ 整除，则称 $k$ 是 $n$ 的因子。例如， $6$ 的因子有 $1, 2, 3, 6$ 。

输入描述

第一行输入两个整数 $l, r$ （ $1 \leq l \leq r \leq 10^{18}$ ），表示询问的区间。

输出描述

输出一个整数，表示区间内因子数量为奇数的数的个数。

样例输入1

1 1

样例输出1

样例说明1

在这个样例中，区间内唯一可以取到的数字为 $1$ ，其因子数量只有自身，为奇数。

样例输入2

4 5

样例输出2

样例说明2

在这个样例中，区间内只有 $4$ 的因子数量为奇数。

参考题解

解题思路：

核心思路是从"因子"到"完全平方数"的转换：

因子成对原理：对于任意正整数，它的因子通常成对存在。假设是的一个因子，那么也是的因子，且。
奇偶性分析：非完全平方数：对于任意一对因子，永远满足，因此因子总数必定是偶数。完全平方数：存在特殊的一对，这两个相等的数值只被统计为一个因子，因此总因子数为奇数。
结论：一个正整数的因子数量为奇数，当且仅当该数是完全平方数。
区间计数：区间内完全平方数的个数为。利用前缀和思想，区间内完全平方数个数为。

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    long long l, r;
    cin >> l >> r;
    long long ans = (long long)sqrtl(r) - (long long)sqrtl(l - 1);
    cout << ans << endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long l = sc.nextLong();
        long r = sc.nextLong();
        long ans = (long) Math.sqrt((double) r) - (long) Math.sqrt((double) (l - 1));
        System.out.println(ans);
    }
}

Python

def solve():
    l, r = map(int, input().split())
    ans = int(r ** 0.5) - int((l - 1) ** 0.5)
    print(ans)

if __name__ == '__main__':
    solve()

第2题 - 超级斐波那契数列

题目

定义超级斐波那契数列如下：给定整数 $k$ ，该序列的前 $k$ 项均为 $1$ ；对于 $n > k$ ，第 $n$ 项为前 $k$ 项之和，即：

$S(n) = S(n-1) + S(n-2) + \cdots + S(n-k)$

现给定整数 $k$ 和查询次数 $q$ ，每次查询一个正整数 $x$ ，请输出该序列的第 $x$ 项对 $10^9 + 7$ 取模后的值。

输入描述

第一行输入两个整数 $k, q$ （ $1 \leq k \leq 10^5$ ， $1 \leq q \leq 10^5$ ）；此后 $q$ 行，每行输入一个正整数 $x$ （ $1 \leq x \leq 10^6$ ）。

输出描述

输出 $q$ 行，每行输出一个整数，表示对应查询的答案对 $10^9 + 7$ 取模后的值。

样例输入

样例输出

样例说明

在这组测试数据中：当 $k=2$ 时， $S(1)=1$ ； $S(2)=1$ ； $S(3)=S(1)+S(2)=2$ ； $S(4)=S(2)+S(3)=3$ ； $S(5)=S(3)+S(4)=5$ 。

参考题解

解题思路：

如果按照原始定义每次进行 $k$ 项求和，时间复杂度会达到 $O(k \times \max(x))$ ，对于大数据量会直接超时。通过推导递推关系进行优化：

对于 $n > k$ ： $S(n) = S(n-1) + S(n-2) + \cdots + S(n-k)$

对于 $n-1 > k$ ： $S(n-1) = S(n-2) + S(n-3) + \cdots + S(n-k-1)$

两式相减得到 $O(1)$ 的状态转移方程：

$S(n) = 2 \times S(n-1) - S(n-k-1)$

特别地， $S(k+1) = k$ （前 $k$ 个 $1$ 的和）。

利用该递推式预处理整个序列后，对每个查询 $O(1)$ 回答。

时间复杂度： $O(\max(x) + q)$
空间复杂度： $O(\max(x))$

C++

#include <bits/stdc++.h>
using namespace std;

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]);
    }

    const long long MOD = 1e9 + 7;
    vector<long long> S(max_x + 1, 0);

    for(int i = 1; i <= min(k, max_x); i++){
        S[i] = 1;
    }

    if(max_x > k){
        S[k + 1] = k % MOD;
        for(int i = k + 2; i <= max_x; i++){
            S[i] = (2 * S[i - 1] % MOD - S[i - k - 1] % MOD + MOD) % MOD;
        }
    }

    for(int i = 0; i < q; i++){
        cout << S[queries[i]] << "\n";
    }

    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int k = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        int[] queries = new int[q];
        int maxX = 0;
        for (int i = 0; i < q; i++) {
            queries[i] = Integer.parseInt(br.readLine().trim());
            maxX = Math.max(maxX, queries[i]);
        }

        final long MOD = 1_000_000_007L;
        long[] S = new long[maxX + 1];

        for (int i = 1; i <= Math.min(k, maxX); i++) {
            S[i] = 1;
        }

        if (maxX > k) {
            S[k + 1] = k % MOD;
            for (int i = k + 2; i <= maxX; i++) {
                S[i] = (2 * S[i - 1] % MOD - S[i - k - 1] % MOD + MOD) % MOD;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            sb.append(S[queries[i]]).append("\n");
        }
        System.out.print(sb);
    }
}

Python

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    k = int(input_data[0])
    q = int(input_data[1])
    queries = [int(x) for x in input_data[2:]]

    max_x = max(queries) if queries else 0
    if max_x == 0:
        return

    MOD = 10 ** 9 + 7
    S = [0] * (max_x + 1)

    for i in range(1, min(k + 1, max_x + 1)):
        S[i] = 1

    if max_x > k:
        S[k + 1] = k % MOD
        for i in range(k + 2, max_x + 1):
            S[i] = (2 * S[i - 1] - S[i - k - 1]) % MOD

    out = [str(S[x]) for x in queries]
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    solve()

第3题 - 最大节点权值

题目

给你一个由 $n$ 个编号为 $1 \sim n$ 的节点以及 $m$ 条编号为 $1 \sim m$ 的边组成的无向图，我们定义一个节点的权值为它的当前度（即已执行完之前所有操作后的状态）加上它的节点编号。

小美会进行 $q$ 次如下操作：

操作一： 断开编号为 $x$ 的边，保证每条边至多被删除一次，即在进行操作一时，该边当前一定存在于图中。
操作二： 向你询问编号为 $x$ 的节点所在的连通块中所有节点中最大的权值，你需要将此权值告诉他。

【名词解释】

度：与一个顶点相连接的边的条数称为该顶点的度。
连通块：也称连通分量，满足：是原图的一个子图；连通块内的任意两个顶点之间都存在路径相连，且路径上的点也在连通块内；是极大的，即不能再通过添加原图中的其他顶点而依旧保持连通性；单独的点也构成一个连通块。连通块的大小即为连通块中顶点的数量。

输入描述

第一行输入三个正整数 $n, m, q$ （ $1 \leq n, m, q \leq 2 \times 10^5$ ），表示节点个数，边个数，操作次数。

此后 $m$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i$ （ $1 \leq u_i, v_i \leq n$ ），表示图上第 $i$ 条边连接节点 $u_i$ 和 $v_i$ 。

此后 $q$ 行，第 $i$ 行先输入一个整数 $op_i$ （ $op_i \in \{1, 2\}$ ），表示操作编号。随后在同一行：

若 $op_i = 1$ ，输入一个整数 $x$ （ $1 \leq x \leq m$ ），表示断掉的边的编号；
若 $op_i = 2$ ，输入一个整数 $x$ （ $1 \leq x \leq n$ ），表示询问的节点编号。

保证图没有重边和自环，操作一合法。

输出描述

输出若干行，每一行对操作二进行回答。

样例输入

样例输出

7
5
6

参考题解

解题思路：

这是一道图论与数据结构结合的连通性问题，使用并查集（DSU）、Kruskal 重构树思想和线段树来高效解决。

核心思路：

正向处理删边操作非常困难（连通块分裂），而逆向处理（时光倒流）将"删边"变为"加边"，可以用并查集轻松维护连通性。

分两步走：

第一遍离线扫描（建重构树）：收集所有最后仍未被删除的边，随后将操作逆序，依次加上被删除的边。使用并查集记录每一次合并，将合并操作抽象为建立一棵类似 Kruskal 重构树的森林结构：每次合并两个连通块时，创建一个新虚拟节点作为它们的父节点。对这棵森林进行 DFS 求出 DFS 序（时间戳），使得任意时刻的一个连通块对应 DFS 序上一段连续区间。
第二遍倒序处理（线段树维护区间最大值）：按 DFS 序在叶子节点建立维护最大值的线段树。重新"时光倒流"执行操作：遇到操作一（加边）：该边两个端点度数加 1，在线段树对应叶子位置单点修改，同时用并查集维护连通性。遇到操作二（查询）：找到该节点所在连通块当前的重构树节点，获取其子树对应的 DFS 区间，在线段树中进行区间最大值查询。

C++

#include <bits/stdc++.h>
using namespace std;

int parent_dsu[200001];
int root_arr[200001];

int find_dsu(int x) {
    while (parent_dsu[x] != x) {
        parent_dsu[x] = parent_dsu[parent_dsu[x]];
        x = parent_dsu[x];
    }
    return x;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<pair<int,int>> edges(M + 1);
    for (int i = 1; i <= M; i++) {
        cin >> edges[i].first >> edges[i].second;
    }

    vector<pair<int,int>> ops(Q);
    for (int i = 0; i < Q; i++) {
        cin >> ops[i].first >> ops[i].second;
    }

    vector<bool> deleted(M + 1, false);
    vector<int> deg(N + 1, 0);

    // 统计初始度数
    for (int i = 1; i <= M; i++) {
        deg[edges[i].first]++;
        deg[edges[i].second]++;
    }

    // 减去被删边的度数
    for (int i = 0; i < Q; i++) {
        if (ops[i].first == 1) {
            deleted[ops[i].second] = true;
            deg[edges[ops[i].second].first]--;
            deg[edges[ops[i].second].second]--;
        }
    }

    // 构建加边序列（时光倒流）
    vector<int> seq;
    for (int i = 1; i <= M; i++) {
        if (!deleted[i]) seq.push_back(i);
    }
    for (int i = Q - 1; i >= 0; i--) {
        if (ops[i].first == 1) seq.push_back(ops[i].second);
    }

    // ---- 第一遍：构建 Kruskal 重构树 ----
    int max_krt = N + (int)seq.size() + 1;
    vector<int> krt_left(max_krt, 0), krt_right(max_krt, 0), krt_parent(max_krt, 0);
    vector<int> add_edge_krt_node(seq.size(), 0);

    for (int i = 1; i <= N; i++) { parent_dsu[i] = i; root_arr[i] = i; }
    int krt_nodes = N;

    for (int idx = 0; idx < (int)seq.size(); idx++) {
        int ei = seq[idx];
        int u = edges[ei].first, v = edges[ei].second;
        int ru = find_dsu(u), rv = find_dsu(v);
        if (ru != rv) {
            krt_nodes++;
            krt_left[krt_nodes] = root_arr[ru];
            krt_right[krt_nodes] = root_arr[rv];
            krt_parent[root_arr[ru]] = krt_nodes;
            krt_parent[root_arr[rv]] = krt_nodes;
            parent_dsu[ru] = rv;
            root_arr[rv] = krt_nodes;
        }
        add_edge_krt_node[idx] = krt_nodes;
    }

    // DFS 计算时间戳
    vector<int> in_time(krt_nodes + 1, 0), out_time(krt_nodes + 1, 0);
    vector<int> leaf_arr(N, 0);
    int timer = 0;

    stack<pair<int,int>> stk;
    for (int i = 1; i <= krt_nodes; i++) {
        if (krt_parent[i] == 0) stk.push({i, 0});
    }
    while (!stk.empty()) {
        auto [curr, state] = stk.top(); stk.pop();
        if (state == 0) {
            if (krt_left[curr] == 0 && krt_right[curr] == 0) {
                in_time[curr] = timer;
                out_time[curr] = timer;
                leaf_arr[timer] = curr;
                timer++;
            } else {
                stk.push({curr, 1});
                if (krt_right[curr]) stk.push({krt_right[curr], 0});
                if (krt_left[curr]) stk.push({krt_left[curr], 0});
            }
        } else {
            in_time[curr] = in_time[krt_left[curr]];
            out_time[curr] = out_time[krt_right[curr]];
        }
    }

    // ---- 线段树 ----
    vector<int> tree(2 * N, 0);
    for (int i = 0; i < N; i++) {
        int node = leaf_arr[i];
        tree[N + i] = deg[node] + node;
    }
    for (int i = N - 1; i > 0; i--) {
        tree[i] = max(tree[2 * i], tree[2 * i + 1]);
    }

    auto update = [&](int pos) {
        int idx = in_time[pos] + N;
        tree[idx] = deg[pos] + pos;
        idx /= 2;
        while (idx > 0) {
            tree[idx] = max(tree[2 * idx], tree[2 * idx + 1]);
            idx /= 2;
        }
    };

    auto query = [&](int l, int r) -> int {
        int res = -1;

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

2025 春招笔试合集文章被收录于专栏

2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南