✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：小兰的音乐播放列表

1️⃣：枚举所有可能的质因子，筛选满足条件的歌曲

2️⃣：对每个质因子使用贪心策略选择不相邻位置

3️⃣：取所有质因子情况下的最大值

难度：中等

这道题目的关键在于理解最大公约数的性质和不相邻选择的贪心策略。由于节拍值范围较小，可以枚举所有质因子，然后对每个质因子贪心选择不相邻的位置，时间复杂度为 ，是一个高效的解法。

题目二：小毛的收藏品评估系统

1️⃣：预处理统计每个数值的出现频次

2️⃣：对每个查询分别统计因子和倍数

3️⃣：使用整除枚举避免重复计算

难度：中等

这道题目结合了数论中的整除关系和高效查询技巧。通过预处理频次和分别枚举因子、倍数的方法，可以在合理的时间复杂度内处理大量查询，体现了算法设计中时空权衡的思想。

题目三：图书馆座位分配优化

1️⃣：使用动态规划定义状态 dp[j][i] 表示前 i 个座位分成 j 个区域的最大效率值

2️⃣：利用值域限制优化转移，只在区间最小值变化时更新答案

3️⃣：时间复杂度优化到 O(kn×100)，充分利用 a_i ≤ 100 的条件

难度：中等

这道题目是经典的区间动态规划问题，关键在于理解如何将连续分段问题转化为 DP 状态。通过巧妙利用值域较小的特点进行剪枝优化，将朴素的 O(kn²) 算法优化到实用的复杂度。解题的核心思想是只有当区间最小值发生变化时才需要更新答案，这大大减少了不必要的计算。

01. 小兰的音乐播放列表

问题描述

小兰是一位音乐爱好者，她有一个包含 首歌曲的播放列表。每首歌曲都有一个特定的节拍值 ，用来表示这首歌的音乐风格特征。

为了创建一个和谐的音乐体验，小兰想要从播放列表中选择一些歌曲，使得这些歌曲的节拍值具有共同的音乐特征（即它们的最大公约数大于 ）。同时，为了避免相似风格的歌曲过于集中，她规定选中的歌曲在原播放列表中的位置不能相邻。

请你帮助小兰计算，在满足上述条件的情况下，她最多可以选择多少首歌曲。

输入格式

第一行输入一个整数 （），表示播放列表中歌曲的数量。

第二行输入 个整数 （），表示每首歌曲的节拍值。

输出格式

输出一个整数，表示小兰最多可以选择的歌曲数量。

样例输入

5
1 2 3 2 6

样例输出

2

数据范围

样例	解释说明
样例1	可以选择位置 和位置 的歌曲，节拍值分别为 和 ，它们的最大公约数为 ，且位置不相邻，所以答案为

题解

这道题目的关键在于理解两个约束条件：选中的歌曲节拍值的最大公约数要大于1，以及选中的歌曲位置不能相邻。

首先分析一下数据范围。由于每首歌曲的节拍值不超过100，所以可能的质因子只有25个（2、3、5、7、...、97）。如果选中的一组歌曲的最大公约数大于1，那么这个最大公约数一定包含某个质因子，也就是说，所有选中歌曲的节拍值都能被这个质因子整除。

基于这个观察，可以采用枚举的策略：对每个可能的质因子 ，我们考虑只选择那些节拍值能被 整除的歌曲，然后在这些候选位置中选择尽可能多的不相邻位置。

对于不相邻选择的问题，可以用贪心策略：从左到右扫描，如果当前位置的歌曲可选（即节拍值能被 整除），就选择它，然后跳过下一个位置。这样可以保证选择的数量最多。

具体算法步骤：

1. 预处理出所有不超过100的质数
2. 对每个质数 ，计算最多能选择多少首节拍值能被 整除的不相邻歌曲
3. 返回所有质数中的最大值

时间复杂度为 ，约为 ，对于 的数据范围是足够的。

参考代码

• Python

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

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    # 预处理质数
    prms = []
    for p in range(2, 101):
        is_prm = True
        for d in range(2, int(p**0.5) + 1):
            if p % d == 0:
                is_prm = False
                break
        if is_prm:
            prms.append(p)
    
    max_cnt = 0
    # 枚举每个质数
    for p in prms:
        cnt = 0
        i = 0
        # 贪心选择不相邻的位置
        while i < n:
            if a[i] % p == 0:
                cnt += 1
                i += 2  # 跳过下一个位置
            else:
                i += 1
        max_cnt = max(max_cnt, cnt)
    
    print(max_cnt)

solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> vals(n);
    for (int i = 0; i < n; i++) {
        cin >> vals[i];
    }
    
    // 预处理质数
    vector<int> prms;
    for (int p = 2; p <= 100; p++) {
        bool ok = true;
        for (int d = 2; d * d <= p; d++) {
            if (p % d == 0) {
                ok = false;
                break;
            }
        }
        if (ok) prms.push_back(p);
    }
    
    int res = 0;
    // 枚举每个质数
    for (int p : prms) {
        int cnt = 0;
        for (int i = 0; i < n; ) {
            if (vals[i] % p == 0) {
                cnt++;
                i += 2;  // 选中后跳过下一个位置
            } else {
                i++;
            }
        }
        res = max(res, cnt);
    }
    
    cout << res << "\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));
        
        int n = Integer.parseInt(br.readLine());
        String[] tokens = br.readLine().split(" ");
        int[] beatVals = new int[n];
        for (int i = 0; i < n; i++) {
            beatVals[i] = Integer.parseInt(tokens[i]);
        }
        
        // 预处理质数
        List<Integer> primeList = new ArrayList<>();
        for (int p = 2; p <= 100; p++) {
            boolean isPrime = true;
            for (int d = 2; d * d <= p; d++) {
                if (p % d == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) primeList.add(p);
        }
        
        int maxCount = 0;
        // 枚举每个质数
        for (int prime : primeList) {
            int count = 0;
            for (int i = 0; i < n; ) {
                if (beatVals[i] % prime == 0) {
                    count++;
                    i += 2;  // 选中后跳过下一个位置
                } else {
                    i++;
                }
            }
            maxCount = Math.max(maxCount, count);
        }
        
        System.out.println(maxCount);
    }
}

02. 小毛的收藏品评估系统

问题描述

小毛是一位古董收藏家，他建立了一个收藏品评估系统。在这个系统中，每件收藏品都有一个唯一的价值评分。

系统中定义两件收藏品为"兼容品"，当且仅当其中一件收藏品的价值评分能够被另一件的价值评分整除（即两个评分之间存在整除关系）。

现在小毛的数据库中存储了 件收藏品的价值评分。接下来会进行 次查询，每次查询给出一个新收藏品的价值评分 ，请你帮助小毛统计数据库中有多少件收藏品与这个新收藏品是"兼容品"。

输入格式

第一行输入两个整数 （），分别表示数据库中收藏品的数量和查询次数。

第二行输入 个整数 （），表示数据库中每件收藏品的价值评分。

接下来 行，每行输入一个整数 （），表示一个新收藏品的价值评分。

输出格式

对于每次查询，输出一个整数，表示数据库中与查询的收藏品为"兼容品"的收藏品数量。

样例输入

5 3
1 2 2 5 6
4
2
1

样例输出

3
4
5

数据范围

样例	解释说明
样例1查询	数据库中的（因为）、（因为）、（因为）与兼容，共件
样例2查询	数据库中的（因为）、（因为）、（因为）、（因为）与兼容，共件
样例3查询	数据库中所有收藏品都与兼容（因为能整除所有正整数），共件

题解

这道题目要求快速查询与给定数字存在整除关系的数字个数。两个数字存在整除关系，意味着一个是另一个的因子或倍数。

对于查询数字 ，我们需要统计数据库中满足以下条件的数字个数：

1. 数据库中的数字是 的因子
2. 数据库中的数字是 的倍数

需要注意的是，如果数据库中的数字恰好等于 ，它既是 的因子又是 的倍数，所以要避免重复计算。

算法思路：

1. 预处理阶段：统计数据库中每个数值的出现次数，用数组 cnt[v] 记录数值 在数据库中出现的次数。

2. 查询阶段：对于每个查询 ，分别统计：

   • 因子部分：遍历 的所有因子 ，累加 cnt[d]
   • 倍数部分：遍历 的所有倍数（在给定范围内），累加对应的计数
   • 减去重复计算的 cnt[x]

对于因子枚举，只需要枚举到 ，每找到一个因子 ，同时也找到了对应的因子 。

对于倍数枚举，从 开始，每次增加 ，直到超出数据范围。

时