笔试时间：2025年04月05日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：整数转变

开始有一个整数b ，你需要经过若干次操作，使n 的值不小于m 。 操作一：将n 更改为2 * n ，花费为 w2 ； 操作二：将 n 更改为3 * n ，花费为w3 。 请输出需要的最小花费。

输入描述

输入第一行一个整数T，代表接下来有 T 组测试数据。

接下来 T 行，每行有 4 个整数 n,m,w2,w31< T < 100001< n,m< 2^{31}-11< w_2,w_3 < 1000

输出描述

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

样例输入

4

1 6 2 3

4 32 3 4

2 1 1 2

1 2147483647 1 4

样例输出

5

8

0

31

参考题解

记忆化搜索。

C++：[此代码未进行大量数据的测试，仅供参考]

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

unordered_map<int, int> dp;
int m, w2, w3;

int dfs(int i) {
    if (i >= m) return 0;
    if (dp.count(i)) return dp[i];
    int cost2 = dfs(i * 2) + w2;
    int cost3 = dfs(i * 3) + w3;
    dp[i] = min(cost2, cost3);
    return dp[i];
}

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

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    static Map<Integer, Integer> dp;
    static int m, w2, w3;

    static int dfs(int i) {
        if (i >= m) return 0;
        if (dp.containsKey(i)) return dp.get(i);
        int cost2 = dfs(i * 2) + w2;
        int cost3 = dfs(i * 3) + w3;
        int res = Math.min(cost2, cost3);
        dp.put(i, res);
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            m = sc.nextInt();
            w2 = sc.nextInt();
            w3 = sc.nextInt();
            dp = new HashMap<>();
            System.out.println(dfs(n));
        }
        sc.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

T = int(input())
for _ in range(T):
    n, m, w2, w3 = map(int, input().split())

    dp = {}
    def dfs(i):
        if i >= m: return 0
        if i in dp: return dp[i]
        dp[i] = min(dfs(i * 2) + w2, dfs(i * 3) + w3)
        return dp[i]


    print(dfs(n))

第二题

题目：漂亮数

我们定义一个漂亮数是这样的数：1、该数为正整数2、设该数为x，存在一个质数p使得x mod p = 0 且 p * p >= x给你一个正整数n，你能否求出有多少漂亮数小于等于n？

输入描述

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

输出描述

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

样例输入

10

样例输出

8

参考题解

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

C++：[此代码未进行大量数据的测试，仅供参考]

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

int main() {
    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 (int p : primes) {
            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) {
            max_prime[x] = x;
            count++;
        } else {
            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;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] minPrime = new int[n + 1];
        List<Integer> primes = new ArrayList<>();

        // 欧拉筛法
        for (int i = 2; i <= n; i++) {
            if (minPrime[i] == 0) {
                minPrime[i] = i;
                primes.add(i);
            }
            for (int p : primes) {
                if (p > minPrime[i] || i * p > n) break;
                minPrime[i * p] = p;
            }
        }

        int count = 0;
        int[] maxPrime = new int[n + 1];

        for (int x = 2; x <= n; x++) {
            if (minPrime[x] == x) {
                maxPrime[x] = x;
                count++;
            } else {
                int p = minPrime[x];
                int m = x / p;
                maxPrime[x] = Math.max(p, maxPrime[m]);
                if ((long) maxPrime[x] * maxPrime[x] >= x) {
                    count++;
                }
            }
        }

        System.out.println(count);
        sc.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())

max_n = n
min_prime = [0] * (max_n + 1)  # 最小质因数数组
primes = []

# 欧拉筛法预处理最小质因数
for i in range(2, max_n + 1):
    if min_prime[i] == 0:
        min_prime[i] = i
        primes.append(i)
    for p in primes:
        if p > min_prime[i] or i * p > max_n:
            break
        min_prime[i * p] = p

count = 0
max_prime = [0] * (max_n + 1)  # 最大质因数数组

for x in range(2, max_n + 1):
    if min_prime[x] == x:  # x是质数
        max_prime[x] = x
        count += 1
    else:  # x是合数
        p = min_prime[x]
        m = x // p
        max_prime[x] = max(p, max_prime[m])
        if max_prime[x] * max_prime[x] >= x:
            count += 1

print(count)

第三题

题目：最长路径

游游很喜欢树，这一天他在研究树上的路径，他遇到了一个难题，现在邀请你帮助他解决该问题。在一棵树上，两个点并不一定能确定一条链，但是可以找到一条经过这两个点最长的一条链。你有一棵 n 个点的树，树上每条边都有一个权值，定义一条简单路径的长度为这条简单路径上的边权和，对于给定的两个点 x, y，你需要回答在树上经过这两个点的最长简单路径是多少。【树上的路径】从节点 u 到节点 v 的简单路径定义为从节点 u 出发，以节点 v 为终点，随意在树上走，不经过重复的点和边走出来的序列。可以证明，在树上，任意两个节点间有且仅有一条简单路径。

输入描述

第一行两个数 n, m (1< n, m < 10^5)。

接下来