✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：艺术画框排列

1️⃣：分析画框的两种放置方式（横放和竖放）

2️⃣：根据高度限制选择占用宽度最小的放置方式

3️⃣：累加所有画框的宽度贡献得到最终答案

难度：简单

这道题目考查贪心算法的基本应用。对于每幅画框，在满足高度限制的前提下选择宽度最小的放置方式。关键在于理解两种放置方式的宽度和高度关系，然后做出最优选择。时间复杂度O(n)，实现简单直观。

题目二：客户行为模式分析

1️⃣：数据预处理，将训练和测试数据合并后进行标准化

2️⃣：使用DBSCAN算法进行密度聚类，识别客户群体和异常客户

3️⃣：根据质心坐标对聚类结果重新排序，输出JSON格式结果

难度：中等

这道题目结合了机器学习和数据处理技术。需要熟悉DBSCAN聚类算法的原理和sklearn库的使用。重点在于理解密度聚类的特点，掌握数据标准化和结果后处理的方法。适合有一定机器学习基础的选手。

题目三：幸运号码统计

1️⃣：使用容斥原理计算倍数个数，避免重复计数

2️⃣：枚举因子并统计不超过n的有效因子个数

3️⃣：处理因子与倍数之间的重叠，得到最终答案

难度：中等

这道题目考查数论知识和容斥原理的应用。需要理解倍数、因子的概念，掌握高效的因子枚举方法。关键难点在于避免重复计数，需要仔细分析各种情况的交集。时间复杂度为O(√x + √y)，对算法效率要求较高。

题目四：城市网络监控系统

1️⃣：使用重心分解技术对树进行预处理，构建分治树

2️⃣：维护每个重心的警戒节点计数和距离总和信息

3️⃣：利用容斥原理处理查询，实现O(log n)的单次操作复杂度

难度：困难

这道题目是树上动态查询的经典问题，需要掌握点分治（重心分解）这一高级数据结构。算法涉及重心寻找、分治树构建、容斥原理等多个知识点。实现复杂度较高，但时间效率优秀。适合有扎实算法基础的高级选手挑战。

01. 艺术画框排列

问题描述

小毛是一位艺术画廊的策展人，他收到了 幅珍贵的艺术画作。每幅画作都已经装裱在精美的矩形画框中，第 幅画的画框尺寸为长 ，宽 。

现在小毛需要在画廊的一面特殊展示墙上按顺序排列这些画作。这面墙有以下特点：

1. 墙面高度有限，最大高度为

2. 所有画框必须紧贴地面排列，不能悬空

3. 每幅画都可以选择横放或竖放（即可以旋转90度）

4. 画框之间不能重叠，必须紧密相邻排列

小毛希望计算出按照给定顺序排列所有画作时，最少需要占用多长的墙面宽度。

保证每幅画至少有一种放置方式能够满足高度限制。

输入格式

第一行包含两个正整数 （，），分别表示画作的数量和墙面的最大高度。

接下来 行，每行包含两个正整数 （），表示第 幅画的画框尺寸。

输出格式

输出一个整数，表示排列所有画作时需要占用的最小墙面宽度。

样例输入

3 4
1 2
2 5
4 2

样例输出

8

数据范围

• 

• 

• 

• 保证

样例	解释说明
样例1	第1幅画可以选择高度较小的方向放置（高度2），占用宽度1；第2幅画只能以高度2放置，占用宽度5；第3幅画选择高度较小的方向放置，占用宽度2。总宽度为1+5+2=8

题解

这道题目的核心思想很直观：对于每幅画，选择一个合适的放置方向使得占用的宽度最小，同时满足高度限制。

关键观察：对于一幅尺寸为 和 的画框，有两种放置方式：

1. 横放：高度为 ，宽度为

2. 竖放：高度为 ，宽度为

策略分析：

• 如果两种放置方式的高度都不超过墙面高度 ，那么应该选择占用宽度较小的那种方式，即竖放（宽度为 ）

• 如果只有一种放置方式满足高度限制，那么只能选择那种方式

具体算法：

1. 对于每幅画，计算两个尺寸的最大值和最小值

2. 如果最大值不超过 ，说明两种放置方式都可行，选择宽度较小的竖放方式，贡献

3. 否则只能选择横放方式，贡献

4. 将所有画作的宽度贡献相加得到答案

时间复杂度 ，对于每幅画只需要进行常数次比较操作。空间复杂度 。

需要注意使用64位整数避免溢出，因为最坏情况下答案可能达到 。

参考代码

• Python

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

def solve():
    """求解艺术画框排列问题"""
    n, m = map(int, input().split())
    
    total_width = 0  # 总宽度
    
    for _ in range(n):
        x, y = map(int, input().split())
        
        # 计算两个尺寸的最大值和最小值
        max_size = max(x, y)
        min_size = min(x, y)
        
        # 如果最大尺寸不超过高度限制，选择宽度较小的放置方式
        if max_size <= m:
            width = min_size  # 竖放，宽度为较小值
        else:
            width = max_size  # 只能横放，宽度为较大值
        
        total_width += width
    
    print(total_width)

if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    long long m;
    cin >> n >> m;
    
    long long ans = 0;  // 总宽度
    
    for (int i = 0; i < n; i++) {
        long long x, y;
        cin >> x >> y;
        
        // 计算最大值和最小值
        long long max_val = max(x, y);
        long long min_val = min(x, y);
        
        // 选择最优放置方式
        if (max_val <= m) {
            ans += min_val;  // 竖放
        } else {
            ans += max_val;  // 横放
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        
        String[] firstLine = reader.readLine().split(" ");
        int frameNum = Integer.parseInt(firstLine[0]);
        long maxHeight = Long.parseLong(firstLine[1]);
        
        long totalWidth = 0;  // 记录总宽度
        
        for (int i = 0; i < frameNum; i++) {
            String[] sizeLine = reader.readLine().split(" ");
            long sizeA = Long.parseLong(sizeLine[0]);
            long sizeB = Long.parseLong(sizeLine[1]);
            
            // 计算尺寸的最大值和最小值
            long biggerSize = Math.max(sizeA, sizeB);
            long smallerSize = Math.min(sizeA, sizeB);
            
            // 根据高度限制选择放置方式
            if (biggerSize <= maxHeight) {
                totalWidth += smallerSize;  // 可以竖放
            } else {
                totalWidth += biggerSize;   // 只能横放
            }
        }
        
        System.out.println(totalWidth);
    }
}

02. 客户行为模式分析

问题描述

小兰是一位资深的数据分析师，她需要为一家电商公司进行客户行为模式分析。公司收集了大量的客户特征数据，希望通过无监督学习方法识别出不同的客户群体，并检测出异常行为的客户。

小兰决定使用基于密度的聚类算法来完成这项任务。她需要：

1. 对历史客户数据和新客户数据进行统一的特征标准化处理

2. 使用密度聚类算法识别客户群体，将相似行为的客户归为同一群体

3. 检测出行为异常的离群客户

4. 为了便于业务部门理解，需要对识别出的客户群体进行重新编号排序

5. 最终输出新客户的群体分类结果

输入格式

输入为一行 JSON 格式的数据，包含以下字段：

• train：二维列表，表示历史客户的特征数据，每个子列表代表一个客户的多维特征

• test：二维列表，表示新客户的特征数据，特征维度与历史数据相同

所有特征值均为数值类型（整数或浮点数）。

输出格式

输出一行 JSON 数组，表示新客户的群体分类结果。

• 正常群体用非负整数表示（如 0, 1, 2, ...）

• 异常客户用 -1 表示

• 输出格式需符合 JSON 规范，逗号后须有空格

样例输入

{"train":[[0,0],[0,1,0],[5,5],[5.1,5],[10,0]],"test":[[0.05,0.05],[5.05,5.05],[9,0]]}

样例输出

[0, 1, -1]

数据范围

• 历史客户数据和新客户数据的特征维度相同

• 所有特征值为有效的数值

• 聚类参数固定：eps=0.3, min_samples=3

样例	解释说明
样例1	第1个新客户[0.05,0.05]被归入群体0；第2个新客户[5.05,5.05]被归入群体1；第3个新客户[9,0]被识别为异常客户（-1）

题解

这道题目本质上是一个密度聚类问题的工程实现。需要按照固定的流程处理数据并输出结果。

算法步骤详解：

1. 数据预处理：将历史数据和新数据按行拼接，形成完整的数据集，然后进行统一的标准化处理。这样可以确保数据在同一个尺度上进行聚类。

2. 密度聚类：使用DBSCAN算法，参数固定为eps=0.3, min_samples=3。该算法能够自动识别簇的数量，并将密度较低的点标记为离群点。

3. 结果重映射：DBSCAN产生的簇标签是随机的，为了输出的一致性，需要根据各簇在标准化特征空间中的质心位置进行重新排序和编号。

4. 提取结果：只输出新客户数据对应的聚类标签。

关键技术点：

• 使用StandardScaler对所有数据进行统一标准化，避免不同特征量纲差异的影响
• DBSCAN聚类算法天然支持离群点检测，标记为-1
• 通过计算质心第一维坐标进行排序，确保输出结果的确定性
• 严格按照JSON格式输出结果

时间复杂度主要由DBSCAN算法决定，为O(n log n)，其中n是样本总数。

参考代码

• Python

import json
import sys
import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import DBSCAN

def analyze_customer_behavior():
    """客户行为模式分析主函数"""
    # 读取JSON输入数据
    input_data = json.loads(sys.stdin.read().strip())
    
    # 解析历史客户数据和新客户数据
    hist_data = np.array(input_data["train"], dtype=float)
    new_data = np.array(input_data["test"], dtype=float)
    
    # 合并所有数据进行统一处理
    combined_data = np.vstack([hist_data, new_data])
    
    # 特征标准化处理
    scaler = StandardScaler()
    normalized_data = scaler.fit_transform(combined_data)
    
    # 使用DBSCAN进行密度聚类
    clusterer = DBSCAN(eps=0.3, min_samples=3, 
                      metric="euclidean", algorithm="auto")
    cluster_labels = clusterer.fit_predict(normalized_data)
    
    # 提取新客户对应的聚类标签
    hist_count = len(hist_data)
    new_labels = cluster_labels[hist_count:]
    
    # 重新映射聚类标签
    unique_clusters = set(cluster_labels)
    normal_clusters = [c for c in unique_clusters if c != -1]
    
    # 计算各簇质心的第一维坐标用于排序
    cluster_centers = {}
    for cluster_id in normal_clusters:
        cluster_points = normalized_data[cluster_labels == cluster_id]
        center_coord = cluster_points.mean(axis=0)[0]
        cluster_centers[cluster_id] = center_coord
    
    # 按质心第一维坐标排序
    sorted_clusters = sorted(normal_clusters, key=lambda c: cluster_centers[c])
    
    # 建立新旧标签映射关系
    label_mapping = {old_label: new_idx for new_idx, old_label in enumerate(sorted_clusters)}
    label_mapping[-1] = -1  # 异常点标签保持不变
    
    # 应用映射到新客户标签
    final_labels = [label_mapping[label] for label in new_labels]
    
    # 输出JSON格式结果
    print(json.dumps(final_labels, separators=(', ', ': ')))

if __name__ == "__main__":
    analyze_customer_behavior()

03. 幸运号码统计

问题描述

小基是一位数字命理学爱好者，她相信某些数字具有特殊的能量。给定两个神秘数字 和 ，她定义一个正整数为"幸运号码"，当且仅当这个数字满足以下条件中的至少一个：

1. 它是 的倍数（能被 整除）

2. 它是 的倍数（能被 整除）

3. 它是 的因子（能整除 ）

4. 它是 的因子（能整除 ）

现在小基想要知道，在 到 的所有正整数中，有多少个数字是幸运号码。

输入格式

输入一行包含三个正整数 （），分别表示查询范围的上限、第一个神秘数字和第二个神秘数字。

输出格式

输出一个整数，表示 到 范围内幸运号码的总数。

样例输入

10 3 5

样例输出

6

数据范围

• 

样例	解释说明
样例1	在1到10中，幸运号码有：1(是3和5的因子)、3(是3的倍数和因子)、5(是5的倍数和因子)、6(是3的倍数)、9(是3的倍数)、10(是5的倍数)，共6个

题解

这道题目需要统计满足特定条件的数字个数。关键是要避免重复计数，因为一个数字可能同时满足多个条件。

分析思路：

1. 倍数统计：使用容斥原理计算 和 的倍数个数

   • 的倍数个数：
   • 的倍数个数：
   • 同时是 和 的倍数个数：
   • 总的倍数个数：

2. 因子统计：枚举 和 的所有因子

   • 对于一个数 ，其因子个数约为
   • 需要统计不超过 的因子个数

3. 去重处理：因子中可能包含已经在倍数中计算过的数字，需要去除重复

具体算法：

1. 计算 和 的最小公倍数
2. 使用容斥原理计算倍数个数
3. 枚举 和 的所有因子，统计不超过 的因子
4. 检查因子是否已经作为倍数被计算过，避免重复计数

优化：因子枚举只需要到 ，对于每个 ，如果 能整除某个数，那么 也是因子。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

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

def get_divisors(num):
    """获取num的所有因子"""
    divisors = set()
    for i in range(1, int(math.sqrt(num)) + 1):
        if num % i == 0:
            divisors.add(i)
            if i != num // i:
                divisors.add(num // i)
    return divisors

def gcd(a, b):
    """计算最大公约数"""
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    """计算最小公倍数"""
    return a * b // gcd(a, b)

def solve():
    """求解幸运号码统计问题"""
    n, x, y = map(int, input().split())
    
    # 计算x和y的倍数个数（使用容斥原理）
    lcm_val = lcm(x, y)
    multiple_count = n // x + n // y - n // lcm_val
    
    # 获取x和y的所有因子
    x_divisors = get_divisors(x)
    y_divisors = get_divisors(y)
    
    # 合并因子集合，并筛选出不超过n的因子
    all_divisors = set()
    for div in x_divisors:
        if div <= n:
            all_divisors.add(div)
    for div in y_divisors:
        if div <= n:
            all_divisors.add(div)
    
    # 统计已经作为倍数计算过的因子个数
    dup_count = 0
    for div in all_divisors:
        if div % x == 0 or div % y == 0:
            dup_count += 1
    
    # 最终答案 = 倍数个数 + 因子个数 - 重复个数
    result = multiple_count + len(all_divisors) - dup_count
    
    print(result)

if __name__ == "__main__":
    solve()

• Cpp

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

// 获取num的所有因子
vector<ll> get_factors(ll num) {
    vector<ll> factors;
    for (ll i = 1; i * i <= num; i++) {
        if (num % i == 0) {
            factors.push_back(i);
            if (i * i != num) {
                factors.push_back(num / i);
            }
        }
    }
    return factors;
}

// 计算最大公约数
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 计算最小公倍数
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n, x, y;
    cin >> n >> x >> y;
    
    // 计算倍数个数
    ll lcm_val = lcm(x, y);
    ll multiples = n / x + n / y - n / lcm_val;
    
    // 获取所有因子
    unordered_set<ll> factor_set;
    vector<ll> x_factors = get_factors(x);
    vector<ll> y_factors = get_factors(y);
    
    for (ll f : x_factors) {
        if (f <= n) factor_set.insert(f);
    }
    for (ll f : y_factors) {
        if (f <= n) factor_set.insert(f);
    }
    
    // 计算重复的因子个数
    ll overlap = 0;
    for (ll f : factor_set) {
        if (f % x == 0 || f % y == 0) {
            overlap++;
        }
    }
    
    ll answer = multiples + (ll)factor_set.size() - overlap;
    cout << answer << "\n";
    
    return 0;
}

• Java

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

public class Main {
    // 获取数字的所有因子
    private static Set<Long> getFactors(long num) {
        Set<Long> factors = new HashSet<>();
        for (long i = 1; i * i <= num; i++) {
            if (num % i == 0) {
                factors.add(i);
                if