2025.04.05 美团笔试题

题解链接：https://mp.weixin.qq.com/s/v5MeHD9ui8lPxRIoe0wD3Q

测评链接：https://oj.niumacode.com/training/59

1. 整数转变

开始有一个整数 b，你需要经过若干次操作，使 n 的值不小于 m 。

操作一：将 $n$ 更改为 $2 * n$ ，花费为 $w_2$
操作二：将 $n$ 更改为 $3 * n$ ，花费为 $w_3$

请输出需要的最小花费。

输入描述

输入第一行一个整数 $T$，代表接下来有 $T$ 组测试数据。接下来 $T$ 行，每行有 4 个整数 $n,m,w_2,w_3$
$1< T < 10000$
$1< n,m < 2^{31}-1$
$1< w_2,w_3 < 1000$

输出描述

对于每组测试数据，输出一行，一个整数代表最小花费

示例 1

输入：

4
1 6 2 3
4 32 3 4
2 1 1 2
1 2147483647 1 4

输出：

代码：动态规划（记忆化搜索 + 哈希表 memo）

记忆化搜索，这个题不可以使用迭代的动态规划来完成，会超时，记忆化搜索可以跳过非常多不必要考虑的状态（因为使用了 unordered_map 而非 vector，省去了逐个遍历的时间）。

#include <bits/stdc++.h>

using namespace std;

unordered_map<long long, long long> memo;

long long dfs(long long i, long long m, long long w2, long long w3) {
    if(i >= m)
        return 0;
    if(memo.find(i) != memo.end())
           return memo[i];
    return memo[i] = min(dfs(i * 2, m, w2, w3) + w2, dfs(i * 3, m, w2, w3) + w3);
}

int main() {
    int T;
    cin >> T;
    while(T--) {
        int n, m, w2, w3;
        cin >> n >> m >> w2 >> w3;
        memo.clear();
        cout << dfs(n, m, w2, w3) << endl;
    }
    return 0;
}

2. 漂亮数

我们定义一个漂亮数是这样的数：

该数为正整数
设该数为 x，存在一个质数 p 使得 x mod p = 0 且 p * p >= x

给你一个正整数 n，你能否求出有多少漂亮数小于等于 n？

输入描述

输入一行一个正整数 $n(1 < n < 5 * 10^6)$

输出描述

输出一行一个正整数，代表小于等于 n 的漂亮数的个数。

示例 1

输入：

输出：

解释：10 以内除了 1 和 8 都是漂亮数

代码：数论

筛质数
基于最小质因数，递推计算每个数的最大质因数。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    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 (size_t j = 0; j < primes.size(); ++j) {
            int p = primes[j];
            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) {  // x是质数
            max_prime[x] = x;
            count++;
        } else {  // x是合数
            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;
}

3. 最长路径

游游很喜欢树，这一天他在研究树上的路径，他遇到了一个难题，现在邀请你帮助他解决该问题。

在一棵树上，两个点并不一定能确定一条链，但是可以找到一条经过这两个点最长的一条链。

你有一棵 n 个点的树，树上每条边都有一个权值，定义一条简单路径的长度为这条简单路径上的边权和，对于给定的两个点 x, y，你需要回答在树上经过这两个点的最长简单路径是多少。

树上的路径：从节点 u 到节点 v 的简单路径定义为从节点 u 出发，以节点 v 为终点，随意在树上走，不经过重复的点和边走出来的序列。可以证明，在树上，任意两个节点间有且仅有一条简单路径。

输入描述

第一行两个数 $n, m (1< n, m < 10^5)$
接下来 $n - 1$ 行，每行 3 个数 $u_i, v_i, d_i (1 < u_i, v_i < n, 1 < d_i <10^9)$，表示树的第 $i$ 条边
接下来 $m$ 行，每行 2 个数 $x, y$，表示一次询问。

输出描述

共 m 行，每行一个整数 ans，表示你的答案

示例 1

输入：

输出：

代码：LCA（最近公共祖先）

路径由三部分组成：

起点 a 到 x：选一个能离 x 最远的点 a（不能往 y 方向走）
x 到 y：这是唯一的固定路径
y 到终点 b：选一个能离 y 最远的点 b（不能往 x 方向走）

总长度就是这三段距离的和。核心是找到 a 和 b 这两个“最远端点”。

为了快速计算，需要提前准备三个重要信息：

向下最长路径（子树方向）
- 用深度优先搜索（DFS）从根节点出发，记录每个节点 u 的两个值：
  - down1[u]：u 向下走到子树的最长路径（比如 u→ 子节点 v → … → 叶子）
  - down2[u]：次长路径（必须走不同子节点）
- 同时记录 down1_child[u] 表示哪个子节点贡献了最长路径
向上最长路径（父节点方向）
- 第二次 DFS 计算 up[u]，表示从u向上走（经过父节点）的最长路径。这里要考虑两种情况：
  - 如果父节点的最长路径经过 u → 只能用父节点的次长路径
  - 否则 → 可以用父节点的最长路径
- 比如父节点 p 的最长路径是 p→q，而 u 是 p 的子节点但不是 q，则 up[u] = up[p] + 边权
LCA（最近公共祖先）
- 用倍增法预处理每个节点的 $2^k$ 级祖先，快速计算 x 和 y 的距离：
  - dist(x,y) = 到根的距离x + 到根的距离y - 2 * 到根的距离(lca(x,y))：这能快速得到 x 到 y 的路径长度
- 对于每个查询 $(x,y)$，分情况处理：
  1. x 和 y 是同一个点：最长路径要么是向下走两条分支（down1 + down2），要么是向上走再向下（up + down1）
  2. x 和 y 不同
    - 分三步计算：
      1. 确定路径方向：
        
        找到 x 到 y 路径上的邻居节点 nx（如果 y 在 x 的子树里，nx 是 x 的子节点；否则是 x 的父节点）
        
        同理找到 y 的邻居 ny
      2. 计算 max_dist_x（不经过 nx 的最远距离）：
        
        如果 nx 是父节点 → 只能向下走，取 down1[x]
        
        如果 nx 是子节点 → 比较向上（up[x]）和向其他子节点的路径（down1 或 down2）
      3. 同样计算 max_dist_y，最终总长度是这三部分的和

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAX_N = 200005;
const int MAX_LOG_N = 20;

unordered_map<int, vector<pair<int, int>>> adj;
int parent[MAX_LOG_N][MAX_N];
int dist_to_parent_pow2[MAX_LOG_N][MAX_N];
int depth[MAX_N];
int dist_from_root[MAX_N];
int actual_parent[MAX_N];
int edge_weight_to_parent[MAX_N];
int down1[MAX_N], down2[MAX_N], down1_child[MAX_N], up[MAX_N];
vector<int> results;

void add_edge(int u, int v, int d) {
    adj[u].emplace_back(v, d);
    adj[v].emplace_back(u, d);
}

void dfs1(int u, int p, int d, int current_dist) {
    depth[u] = d;
    dist_from_root[u] = current_dist;
    parent[0][u] = p;
    actual_parent[u] = p;

    int max1 = 0, max2 = 0, child1 = 0;

    for (auto& [v, weight] : adj[u]) {
        if (v != p) {
            edge_weight_to_parent[v] = weight;
            dist_to_parent_pow2[0][v] = weight;
            
            dfs1(v, u, d + 1, current_dist + weight);
            
            int current_down_path = down1[v] + weight;
            if (current_down_path >= max1) {
                max2 = max1;
                max1 = current_down_path;
                child1 = v;
            } else if (current_down_path > max2) {
                max2 = current_down_path;
            }
        }
    }

    down1[u] = max1;
    down2[u] = max2;
    down1_child[u] = child1;
}

void dfs2(int u, int p) {
    int p_node = actual_parent[u];
    
    if (p_node != 0) {
        int weight_up = edge_weight_to_parent[u];
        int down_from_parent_not_via_u;
        
        if (down1_child[p_node] == u) {
            down_from_parent_not_via_u = down2[p_node];
        } else {
            down_from_parent_not_via_u = down1[p_node];
        }
        
        up[u] = weight_up + max(up[p_node], down_from_parent_not_via_u);
    }

    for (auto& [v, weight] : adj[u]) {
        if (v != p) {
            dfs2(v, u);
        }
    }
}

int get_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    
    for (int k = MAX_LOG_N - 1; k >= 0; --k) {
        if (depth[u] - (1 << k) >= depth[v]) {
            u = parent[k][u];
        }
    }
    
    if (u == v) return u;
    
    for (int k = MAX_LOG_N - 1; k >= 0; --k) {
        if (parent[k][u] != parent[k][v]) {
            u = parent[k][u];
            v = parent[k][v];
        }
    }
    
    return parent[0][u];
}

int get_dist(int u, int v) {
    int l = get_lca(u, v);
    return dist_from_root[u] + dist_from_root[v] - 2 * dist_from_root[l];
}

int get_ancestor(int u, int k) {
    int node = u;
    for (int i = 0; i < MAX_LOG_N; ++i) {
        if ((k >> i) & 1) {
            node = parent[i][node];
            if (node == 0) break;
        }
    }
    return node;
}

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n - 1; ++i) {
        int u, v, d;
        cin >> u >> v >> d;
        add_edge(u, v, d);
    }

    int MAX_LOG_N = (n - 1) == 0 ? 1 : 32 - __builtin_clz(n - 1);
    
    dfs1(1, 0, 0, 0);

    for (int k = 1; k < MAX_LOG_N; ++k) {
        for (int i = 1; i <= n; ++i) {
            parent[k][i] = parent[k-1][parent[k-1][i]];
            if (parent[k-1][i] != 0) {
                dist_to_parent_pow2[k][i] = dist_to_parent_pow2[k-1][i] + dist_to_parent_pow2[k-1][parent[k-1][i]];
            }
        }
    }

    dfs2(1, 0);

    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;

        if (x == y) {
            int ans = max(down1[x] + down2[x], up[x] + down1[x]);
            results.push_back(ans);
            continue;
        }

        int l = get_lca(x, y);
        int dist_xy = get_dist(x, y);

        int nx = 0;
        if (l == x) {
            int target_depth = depth[x] + 1;
            int steps_up = depth[y] - target_depth;
            nx = get_ancestor(y, steps_up);
        } else {
            nx = actual_parent[x];
        }

        int ny = 0;
        if (l == y) {
            int target_depth = depth[y] + 1;
            int steps_up = depth[x] - target_depth;
            ny = get_ancestor(x, steps_up);
        } else {
            ny = actual_parent[y];
        }

        int max_dist_x;
        if (nx == actual_parent[x]) {
            max_dist_x = down1[x];
        } else {
            if (nx == down1_child[x]) {
                max_dist_x = max(up[x], down2[x]);
            } else {
                max_dist_x = max(up[x], down1[x]);
            }
        }

        int max_dist_y;
        if (ny == actual_parent[y]) {
            max_dist_y = down1[y];
        } else {
            if (ny == down1_child[y]) {
                max_dist_y = max(up[y], down2[y]);
            } else {
                max_dist_y = max(up[y], down1[y]);
            }
        }

        int ans = max_dist_x + dist_xy + max_dist_y;
        results.push_back(ans);
    }

    for (int res : results) {
        cout << res << "\n";
    }
}

int main() {
    solve();
    return 0;
}

本文由 Yikun Wu 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。