✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

淘天-2025.10.25

题目一：藏品整理系统

1️⃣：预处理每个数的约数列表，时间复杂度

2️⃣：维护计数数组 表示能被 整除的数量

3️⃣：查询操作 ，修改操作 ，其中 为约数个数

难度：中等

这道题目的关键在于换个角度思考：不是每次查询时遍历数组，而是预先维护每个除数对应的计数。通过空间换时间，将查询优化到常数时间，利用了"一个数的约数个数不多"这一数学性质。

题目二：神秘符文计数

1️⃣：将问题转化为组合计数问题

2️⃣：发现递推关系 ，答案为斐波那契数列

3️⃣：使用矩阵快速幂的倍增法在 时间内计算

难度：中等

这道题目巧妙地将一个看似复杂的组合问题转化为斐波那契数列求值。关键在于观察到递推规律，然后使用倍增法高效计算，体现了数学建模和算法优化的结合。

题目三：能量石收集

1️⃣：计算总能量 ，判断 是否超过

2️⃣：使用贪心策略从大到小选择能量石

3️⃣：将选中的编号反转后输出（升序）

难度：中等

这道题目的核心是贪心算法的应用。由于能量值恰好是连续的正整数，贪心策略能够保证找到解（如果存在）。理解为什么贪心是正确的，需要对问题的数学性质有深刻认识。

01. 藏品整理系统

问题描述

小兰是一位收藏家，她拥有 件藏品，每件藏品都有一个编号。为了方便管理，她给每件藏品标注了一个价值数字。最近，小兰需要频繁地查询和更新她的藏品信息。

具体来说，她需要处理 次操作，每次操作属于以下两种类型之一：

• 查询操作：给定一个整数 ，统计当前所有藏品中，有多少件藏品的价值可以被 整除。

• 修改操作：将第 件藏品的价值修改为 （藏品编号从 开始）。

请帮助小兰完成这个藏品管理系统。

输入格式

第一行包含两个整数 ，分别表示藏品数量和操作次数。

第二行包含 个整数 ，表示每件藏品的初始价值。

接下来 行，每行表示一次操作：

• 若为查询操作，输入两个整数 。

• 若为修改操作，输入三个整数 。

输出格式

对于每一次查询操作，输出一行整数，表示满足条件的藏品数量。

样例输入

5 6
2 3 4 5 6
1 2
1 3
2 3 9
1 3
2 5 12
1 6

样例输出

3
2
3
1

数据范围

样例	解释说明
样例1	初始藏品价值为 。第一次查询 ，有 三件藏品可被 整除。第二次查询 ，有 两件可被 整除。第三次将第 件藏品改为 ，此时数组变为 。第四次查询 ，有 三件可被 整除。第五次将第 件藏品改为 。最后查询 ，只有 可被 整除。

题解

这道题目的核心是如何高效地处理查询和修改操作。如果每次查询都遍历整个数组，时间复杂度会达到 ，对于题目给定的数据范围会超时。

关键观察：一个数 能被 整除，当且仅当 是 的约数。因此，我们可以换个角度思考：对于每个可能的除数 ，维护当前数组中有多少个数能被 整除。

解法思路：

1. 预处理约数：对于 到 的每个数，预先计算出它的所有约数。这个过程可以通过枚举倍数来实现，时间复杂度 。

2. 维护计数数组：使用一个数组 表示当前有多少个数能被 整除。

3. 初始化：读入初始数组后，对于每个数 ，遍历它的所有约数 ，将 加 。

4. 处理查询：查询操作只需要直接输出 ，时间复杂度 。

5. 处理修改：修改操作需要先将旧值 的所有约数对应的计数减 ，然后将新值 的所有约数对应的计数加 ，最后更新 。由于一个数的约数个数平均在 左右，所以每次修改的时间复杂度约为 。

时间复杂度分析：

• 预处理约数：，其中 。
• 初始化计数：，其中 是平均约数个数。
• 查询操作：。
• 修改操作：。
• 总时间复杂度：，对于给定的数据范围完全可以接受。

这个解法巧妙地利用了"一个数的约数个数不多"这一性质，通过空间换时间的策略，将查询优化到了常数时间。

参考代码

• Python

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

MAX = 200000

# 预处理每个数的约数
divs = [[] for _ in range(MAX + 1)]
for i in range(1, MAX + 1):
    for j in range(i, MAX + 1, i):
        divs[j].append(i)

n, q = map(int, input().split())
arr = [0] + list(map(int, input().split()))  # 下标从1开始

# cnt[k] 表示有多少个数能被k整除
cnt = [0] * (MAX + 1)

# 初始化计数数组
for i in range(1, n + 1):
    for d in divs[arr[i]]:
        cnt[d] += 1

# 处理操作
for _ in range(q):
    op = list(map(int, input().split()))
    if op[0] == 1:  # 查询操作
        k = op[1]
        print(cnt[k])
    else:  # 修改操作
        i, x = op[1], op[2]
        # 减去旧值的贡献
        for d in divs[arr[i]]:
            cnt[d] -= 1
        # 加上新值的贡献
        for d in divs[x]:
            cnt[d] += 1
        # 更新数组
        arr[i] = x

• Cpp

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

const int MX = 200000;
vector<int> divs[MX + 1];  // divs[i]存储i的所有约数
int arr[MX + 1];           // 存储藏品价值
int cnt[MX + 1];           // cnt[k]表示能被k整除的数量

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 预处理：对每个数i，将i加入到它的所有倍数的约数列表中
    for (int i = 1; i <= MX; i++) {
        for (int j = i; j <= MX; j += i) {
            divs[j].push_back(i);
        }
    }
    
    int n, q;
    cin >> n >> q;
    
    // 读入初始数组并初始化计数
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        for (int d : divs[arr[i]]) {
            cnt[d]++;
        }
    }
    
    // 处理q次操作
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {  // 查询操作
            int k;
            cin >> k;
            cout << cnt[k] << "\n";
        } else {  // 修改操作
            int idx, val;
            cin >> idx >> val;
            // 减去旧值的约数计数
            for (int d : divs[arr[idx]]) {
                cnt[d]--;
            }
            // 加上新值的约数计数
            for (int d : divs[val]) {
                cnt[d]++;
            }
            // 更新数组值
            arr[idx] = val;
        }
    }
    
    return 0;
}

• Java

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

public class Main {
    static final int MAX_VAL = 200000;
    static List<Integer>[] divList;  // 存储每个数的约数
    static int[] items;              // 藏品价值数组
    static int[] divCnt;             // 整除计数数组
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        
        // 预处理约数表
        divList = new ArrayList[MAX_VAL + 1];
        for (int i = 0; i <= MAX_VAL; i++) {
            divList[i] = new ArrayList<>();
        }
        for (int i = 1; i <= MAX_VAL; i++) {
            for (int j = i; j <= MAX_VAL; j += i) {
                divList[j].add(i);
            }
        }
        
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int q = Integer.parseInt(line[1]);
        
        items = new int[n + 1];
        divCnt = new int[MAX_VAL + 1];
        
        // 读入初始数据并统计
        line = br.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            items[i] = Integer.parseInt(line[i - 1]);
            for (int d : divList[items[i]]) {
                divCnt[d]++;
            }
        }
        
        // 处理操作
        for (int i = 0; i < q; i++) {
            line = br.readLine().split(" ");
            int opType = Integer.parseInt(line[0]);
            if (opType == 1) {  // 查询
                int k = Integer.parseInt(line[1]);
                pw.println(divCnt[k]);
            } else {  // 修改
                int pos = Integer.parseInt(line[1]);
                int newVal = Integer.parseInt(line[2]);
                // 减去旧值的贡献
                for (int d : divList[items[pos]]) {
                    divCnt[d]--;
                }
                // 加上新值的贡献
                for (int d : divList[newVal]) {
                    divCnt[d]++;
                }
                items[pos] = newVal;
            }
        }
        
        pw.flush();
        pw.close();
        br.close();
    }
}

02. 神秘符文计数

问题描述

在古老的魔法世界中，小基发现了一种特殊的符文系统。这个系统中只有两种基础符文：圆环符文和双环符文。

圆环符文蕴含 单位的魔力，而双环符文蕴含 单位的魔力。

现在小基想要研究一个有趣的问题：有多少种方式可以组合这些符文，使得：

• 组合中不能以圆环符文开头（即不能有前导的圆环符文）。

• 组合中只包含圆环符文和双环符文两种。

• 组合的总魔力值恰好为 单位。

由于小基需要处理多组询问，请你帮她计算每组询问的答案。

输入格式

第一行包含一个整数 ，表示测试数据的组数。

接下来 行，每行包含一个正整数 ，表示询问的目标魔力值。

输出格式

对于每组测试数据，输出一行整数，表示满足条件的符文组合方案数。

由于结果可能很大，请输出答案对 取模后的值。

样例输入

5
1
4
10
100
1000

样例输出

1
2
34
750033655
407824689

数据范围

样例	解释说明
样例1	当 时，只有一种方案：单独的圆环符文（虽然不能作为开头，但单个符文时它本身就是完整的组合）。
样例2	当 时，有两