程序员基德

08-25 19:11 中国科学技术大学 C++ 发布于浙江

关注

【秋招笔试】2025.08.24小红书秋招笔试第一套改编题

✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

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

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

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

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

难度：中等

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

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

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

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

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

难度：中等

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

题目三：小基的单词游戏挑战

1️⃣：分析约束条件，将问题转化为字母频次的优化问题

2️⃣：从后往前贪心确定每个字母的保留次数

3️⃣：按字典序构造最终结果字符串

难度：中等偏难

这道题目需要深入理解贪心算法的本质和字典序的特性。通过从高位字母向低位字母的贪心策略，既保证了约束条件的满足，又实现了删除字符数的最小化和字典序的最优化，是一个精巧的贪心问题。

01. 小兰的音乐播放列表

问题描述

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

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

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

输入格式

第一行输入一个整数 $n$ （ $1 \leq n \leq 10^5$ ），表示播放列表中歌曲的数量。

第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1 \leq a_i \leq 100$ ），表示每首歌曲的节拍值。

输出格式

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

样例输入

5
1 2 3 2 6

样例输出

数据范围

$1 \leq n \leq 10^5$
$1 \leq a_i \leq 100$

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

题解

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

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

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

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

具体算法步骤：

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

时间复杂度为 $O(n \times \text{质数个数})$ ，约为 $O(25n)$ ，对于 $n \leq 10^5$ 的数据范围是足够的。

参考代码

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()

#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);
    }
}