✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线160+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

得物-第二套

题目一：魔法数字的奥秘

1️⃣：使用 Hensel 提升定理从模 10 的解逐步构造更高位数的解

2️⃣：预处理所有不超过 的魔法数字并排序

3️⃣：使用二分查找快速统计区间内的魔法数字个数

难度：中等

这道题目的关键在于理解魔法数字的数学性质，即满足 的数字。通过 Hensel 提升定理，我们可以从模 10 的四个根 开始，逐步构造出所有可能的魔法数字。由于魔法数字的总数极少（不超过 40 个），我们可以预处理后使用二分查找，实现高效的区间统计。

题目二：最优团队组建方案

1️⃣：将问题转化为图论中的连通分量计数问题

2️⃣：使用并查集维护员工之间的分组关系

3️⃣：在所有可能的阈值上进行二分查找找到最优解

难度：中等

这道题目结合了图论和二分查找的思想。核心在于理解随着阈值的增大，连通分量个数单调递减的性质。通过预处理所有员工对之间的协作相容性，然后使用并查集高效地计算给定阈值下的连通分量个数，最终通过二分查找找到满足条件的最大阈值。算法的时间复杂度为 ，对于题目的数据规模完全可以接受。

题目三：音乐厅演奏计划

1️⃣：设计三维动态规划状态

2️⃣：分情况讨论状态转移

3️⃣：使用滚动数组优化空间复杂度

难度：中等

这道题目考查动态规划的状态设计和转移。关键在于区分前一天是否练习的状态，以及正确处理打破原则的机会消耗。通过合理的状态定义，可以实现 O(nk) 的时间复杂度。

01. 魔法数字的奥秘

问题描述

K 小姐是一位热爱数学的魔法师，她发现了一类具有神奇性质的数字。这些数字被称为"魔法数字"。

一个正整数如果满足以下条件，就被称为魔法数字：将这个数自乘三次（即计算它的立方），得到的结果的末尾几位数字与原数字完全相同。

例如：数字 ，它的立方是 ，而 的末尾两位是 ，正好与原数字相同，所以 是一个魔法数字。

现在 K 小姐想知道，在给定的数字区间 中，一共有多少个魔法数字？

输入格式

输入包含两个正整数 和 ，用空格分隔。

其中 。

输出格式

输出一个整数，表示在区间 中（包含 和 ）魔法数字的个数。如果没有魔法数字，则输出 。

样例输入

1 200

10 100

样例输出

3

2

样例	解释说明
样例1	在区间 中，魔法数字有：（），（，末尾两位为 ），（，末尾三位为 ），共 个
样例2	在区间 中，魔法数字有： 和 （，末尾两位为 ），共 个

数据范围

题解

这道题的关键在于理解什么是魔法数字，以及如何高效地找到所有满足条件的数字。

首先分析魔法数字的性质：如果一个 位数 是魔法数字，那么 ，即 ，也就是 。

通过数学分析可以发现，对于任意位数 ，满足条件的数字只有有限个。我们可以从小的位数开始，逐步构造出所有可能的魔法数字。

具体做法是使用 Hensel 提升定理：

1. 首先找出所有满足 的数字，这些数字是
2. 对于每个已知的 位魔法数字，我们可以通过在其前面添加一位数字，构造出 位的魔法数字
3. 重复这个过程，直到构造出所有不超过 的魔法数字

由于魔法数字的数量很少（不超过 40 个），我们可以预处理出所有的魔法数字，然后对于每个查询，使用二分查找统计区间内的数量。

时间复杂度：预处理 ，查询 。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()

def precompute():
    # 预处理所有不超过 1e9 的魔法数字
    cur = [0, 1, 5, 6]  # x^3 ≡ x (mod 10) 的解
    ans = []
    mod = 10  # 当前模数
    
    for k in range(1, 11):  # 处理 1 到 10 位数
        nxt = []
        for x in cur:
            # 寻找唯一的 t 使得 y = x + t*mod 满足 y^3 ≡ y (mod 10*mod)
            for t in range(10):
                y = x + t * mod
                if (y * y * y) % (mod * 10) == y:
                    nxt.append(y)
                    break
        cur = nxt
        
        # 将恰好 k 位且 <= 1e9 的数字加入答案
        for x in cur:
            if mod // 10 <= x < mod and x <= 10**9 and x != 0:
                ans.append(x)
        mod *= 10
    
    return sorted(ans)

# 预处理所有魔法数字
magic_nums = precompute()

def solve():
    a, b = map(int, input().split())
    
    # 使用二分查找统计区间内的魔法数字数量
    left = 0
    right = len(magic_nums) - 1
    
    # 找到第一个 >= a 的位置
    start_pos = len(magic_nums)
    lo, hi = 0, len(magic_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if magic_nums[mid] >= a:
            start_pos = mid
            hi = mid - 1
        else:
            lo = mid + 1
    
    # 找到最后一个 <= b 的位置
    end_pos = -1
    lo, hi = 0, len(magic_nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if magic_nums[mid] <= b:
            end_pos = mid
            lo = mid + 1
        else:
            hi = mid - 1
    
    # 计算区间内的数量
    if start_pos <= end_pos:
        print(end_pos - start_pos + 1)
    else:
        print(0)

solve()

Cpp

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

// 预处理所有不超过 1e9 的魔法数字
vector<ll> precompute() {
    vector<ll> cur = {0, 1, 5, 6};  // x^3 ≡ x (mod 10) 的解
    vector<ll> ans;
    ll mod = 10;  // 当前模数
    
    for (int k = 1; k <= 10; ++k) {  // 处理 1 到 10 位数
        vector<ll> nxt;
        for (ll x : cur) {
            // 寻找唯一的 t 使得 y = x + t*mod 满足 y^3 ≡ y (mod 10*mod)
            for (int t = 0; t < 10; ++t) {
                ll y = x + (ll)t * mod;
                if (((__int128)y * y * y) % (mod * 10) == y) {
                    nxt.push_back(y);
                    break;
                }
            }
        }
        cur.swap(nxt);
        
        // 将恰好 k 位且 <= 1e9 的数字加入答案
        for (ll x : cur) {
            if (x >= mod / 10 && x < mod && x <= 1000000000LL && x != 0) {
                ans.push_back(x);
            }
        }
        mod *= 10;
    }
    
    sort(ans.begin(), ans.end());
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 预处理所有魔法数字
    static const vector<ll> magic = precompute();
    
    ll a, b;
    cin >> a >> b;
    
    // 使用 STL 的二分查找函数
    auto left = lower_bound(magic.begin(), magic.end(), a);
    auto right = upper_bound(magic.begin(), magic.end(), b);
    
    cout << (right - left) << "\n";
    
    return 0;
}

Java

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

public class Main {
    // 预处理所有不超过 1e9 的魔法数字
    private static List<Long> precompute() {
        List<Long> cur = new ArrayList<>(Arrays.asList(0L, 1L, 5L, 6L));
        List<Long> ans = new ArrayList<>();
        long mod = 10;  // 当前模数
        
        for (int k = 1; k <= 10; k++) {  // 处理 1 到 10 位数
            List<Long> nxt = new ArrayList<>();
            for (long x : cur) {
                // 寻找唯一的 t 使得 y = x + t*mod 满足 y^3 ≡ y (mod 10*mod)
                for (int t = 0; t < 10; t++) {
                    long y = x + (long)t * mod;
                    if ((y * y * y) % (mod * 10) == y) {
                        nxt.add(y);
                        break;
                    }
                }
            }
            cur = nxt;
            
            // 将恰好 k 位且 <= 1e9 的数字加入答案
            for (long x : cur) {
                if (x >= mod / 10 && x < mod && x <= 1000000000L && x != 0) {
                    ans.add(x);
                }
            }
            mod *= 10;
        }
        
        Collections.sort(ans);
        return ans;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 预处理所有魔法数字
        List<Long> magic = precompute();
        
        String[] input = br.readLine().split(" ");
        long a = Long.parseLong(input[0]);
        long b = Long.parseLong(input[1]);
        
        // 使用二分查找统计区间内的魔法数字数量
        int left = Collections.binarySearch(magic, a);
        if (left < 0) left = -left - 1;
        
        int right = Collections.binarySearch(magic, b);
        if (right < 0) right = -right - 2;
        else right++;
        
        if (left <= right && right < magic.size()) {
            System.out.println(right - left);
        } else {
            System.out.println(0);
        }
    }
}

02. 最优团队组建方案

问题描述

小基 是一家科技公司的项目经理，她需要为即将到来的团队建设活动组建若干个项目小组。

公司共有 名员工，每名员工都有两个重要的评估指标：技能等级 和协作指数 。为了确保团队协作的效果，小基 制定了一个"协作相容性"的标准。

两名员工之间的协作相容性定义为：他们技能等级差值的绝对值与协作指数差值的绝对值之和，即 。

现在 小基 需要设定一个相容性阈值 ，如果两名员工的协作相容性不超过 ，那么这两名员工必须被分配到同一个项目小组中（当然，即使协作相容性超过 的员工也可以在同一组，但不超过 的必须在同一组）。

小基 希望最终能够组建至少 个非空的项目小组。请问相容性阈值 最大可以设置为多少？

输入格式

第一行包含两个正整数 和 ，分别表示员工总数和需要组建的最少小组数。

第二行包含 个正整数 ，表示每名员工的技能等级。

第三行包含 个正整数 ，表示每名员工的协作指数。

输出格式

输出一个整数，表示相容性阈值 的最大可能值。

样例输入

3 2
1 9 3
2 7 8

4 3
1 2 3 4
1 3 2 4

样例输出

7

2

样例	解释说明
样例1	员工1和员工2的相容性为 ，员工2和员工3的相容性为 ，员工1和员工3的相容性为 。当阈值为 时，员工2和员工3必须在同一组，员工1单独一组，共2组满足要求
样例2	当阈值为 时，只有相容性不超过 的员工会被强制分到同一组，这样可以保证至少有 个小组

数据范围

• 
• 
• 保证任意两名员工的技能等级或协作指数至少有一项不同
• 由于 ，所以答案一定不为无穷大

题解

这道题本质上是一个图论问题。我们可以将每个员工看作图中的一个节点，当两个员工的协作相容性不超过阈值 时，就在他们之间连一条边。这样，连通的员工就必须在同一个项目小组中。

问题转化为：给定阈值 ，计算图中的连通分量个数。我们需要找到最大的 ，使得连通分量个数至少为 。

观察到随着阈值 的增大，图中的边会越来越多，连通分量的个数是单调递减的。因此我们可以使用二分查找来解决这个问题。

具体算法：

1. 预处理所有员工对之间的协作相容性：计算所有 对员工之间的协作相容性，并存储所有不同的数值。

2. 二分查找答案：在所有可能的协作相容性值上进行二分查找。对于每个候选值 ，使用并查集来计算当阈值为 时图中的连通分量个数。

3. 并查集统计连通分量：对于给定的阈值 ，将所有协作相容性不超过 的员工对用并查集连接起来，最后统计有多少个不同的连通分量。

4. 判断可行性：如果连通分量个数大于等于 ，说明当前的 值可行，尝试更大的值；否则说明 值过大，需要尝试更小的值。

时间复杂度分析：

• 预处理所有员工对的协作相容性：
• 二分查找的次数：
• 每次二分查找中使用并查集的时间复杂度：，其中 是反阿克曼函数
• 总时间复杂度：

对于 的数据规模，这个算法可以很好地解决问题。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()

class DSU:
    def __init__(self, n):
        # 初始化并查集，每个节点的父节点是自己
        self.parent = list(range(n))
        self.size = [1] * n
    
    def find(self, x):
        # 路径压缩：查找根节点并压缩路径
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # 按大小合并：将小树合并到大树上
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
    
    def count_groups(self):
        # 统计连通分量的个数
        return len(set(self.find(i) for i in range(len(self.parent))))

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    # 计算所有员工对之间的协作相容性
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            dist = abs(a[i] - a[j]) + abs(b[i] - b[j])