✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

菜鸟

题目一：小兰的书籍分配计划

1️⃣：二分搜索最优分配数量，建立数学模型

2️⃣：利用等差数列求和公式计算最少需求，优化计算复杂度

难度：中等

这道题目的核心是在约束条件下的最优化问题。通过建立数学模型，将问题转化为单调函数的二分搜索，关键在于理解相邻差值约束下的最小需求计算。利用等差数列求和公式，可以在 O(log m) 时间内求解。

题目二：小毛的客户分类模型

1️⃣：解析二维数据集，提取特征和标签信息

2️⃣：实现基尼指数计算，评估特征分裂效果

3️⃣：遍历所有特征，选择最优分裂标准

难度：中等

这道题目结合了机器学习中决策树的核心概念。需要深入理解基尼不纯度的含义和计算方法，通过统计不同特征值下的类别分布，计算条件基尼指数，从而选择最佳特征进行数据分裂。

题目三：小基的魔法宝石消除

1️⃣：模拟消除规则，查找连续相同元素

2️⃣：实现重力下落机制，维护网格状态

3️⃣：循环执行消除和下落，直到无法继续

难度：中等偏难

这道题目是经典的消除类游戏模拟，需要准确实现多轮消除的同步性和重力下落机制。关键在于正确处理每轮的标记消除和列内元素的重新排列，考验对模拟过程的精确控制能力。

01. 小兰的书籍分配计划

问题描述

小兰是图书馆的管理员，她负责管理一个特殊的阅读室。这个阅读室有 个连续编号的座位（编号从 到 ），小兰的座位编号是 。今天图书馆收到了 本珍贵的古籍，小兰需要将这些古籍分配给阅读室里的读者。

为了维护阅读室的和谐氛围，小兰制定了一个公平分配原则：相邻座位的读者获得的古籍数量差不能超过 本。同时，每个读者至少要分到 本古籍。在满足这些条件的前提下，小兰希望自己能够获得尽可能多的古籍用于深入研究。

请帮助小兰计算，在满足分配原则的情况下，她最多能获得多少本古籍？

输入格式

第一行包含三个正整数 、、（，），分别表示座位数量、古籍总数和小兰的座位编号。

输出格式

输出一行，表示小兰能够获得的古籍数量的最大值。

样例输入

4 6 2

样例输出

2

数据范围

• 

• 

• 

• 

样例	解释说明
样例1	小兰坐在2号位置，4个座位分配6本书，可以按 的方式分配，小兰获得2本古籍

题解

这道题目的核心是理解分配约束条件下的最优化问题。

假设小兰获得 本古籍，那么由于相邻座位的古籍数量差不能超过1，我们可以推导出每个位置最少需要的古籍数量：

• 小兰左边第 个位置最少需要 本古籍
• 小兰右边第 个位置最少需要 本古籍

因此，总的最少古籍需求量为：

这个函数关于 单调递增，我们可以用二分搜索在 范围内找到最大的 使得 。

对于求和部分，当 时，前面的部分可以用等差数列求和公式计算，后面不足的部分每个位置分配1本。

时间复杂度为 ，每次计算need函数的复杂度为 。

参考代码

• Python

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

def calc_need(x, n, k):
    # 计算小兰得x本书时，总共至少需要多少本书
    left_cnt = k - 1  # 小兰左边的位置数
    right_cnt = n - k  # 小兰右边的位置数
    total = x  # 小兰的书数
    
    # 计算一侧需要的书数
    def side_sum(cnt):
        if x <= 1:
            return cnt  # 每个位置都只能分1本
        dec_len = min(cnt, x - 1)  # 递减部分的长度
        high = x - 1
        low = x - dec_len
        # 等差数列求和
        arith_sum = (high + low) * dec_len // 2
        return arith_sum + (cnt - dec_len)  # 剩余位置每个分1本
    
    total += side_sum(left_cnt) + side_sum(right_cnt)
    return total

def solve():
    n, m, k = map(int, input().split())
    
    # 二分搜索最大的x使得need(x) <= m
    l, r = 1, m
    while l < r:
        mid = (l + r + 1) // 2
        if calc_need(mid, n, k) <= m:
            l = mid
        else:
            r = mid - 1
    
    print(l)

if __name__ == "__main__":
    solve()

• Cpp

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

// 计算小兰得到x本书时总共需要的最少书数
long long calc_need(long long x, long long n, long long k) {
    long long left_cnt = k - 1;  // 左侧位置数
    long long right_cnt = n - k;  // 右侧位置数
    long long res = x;  // 小兰的书数
    
    // 计算单侧需求
    auto side_calc = [&](long long cnt) -> long long {
        if (x <= 1) return cnt;  // 每位置分1本
        long long dec_len = min(cnt, x - 1);  // 递减序列长度
        long long high = x - 1, low = x - dec_len;
        long long sum = (high + low) * dec_len / 2;  // 等差求和
        return sum + (cnt - dec_len);  // 剩余位置分1本
    };
    
    res += side_calc(left_cnt) + side_calc(right_cnt);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long n, m, k;
    cin >> n >> m >> k;
    
    long long l = 1, r = m;
    while (l < r) {
        long long mid = (l + r + 1) / 2;
        if (calc_need(mid, n, k) <= m) {
            l = mid;  // 可行，尝试更大值
        } else {
            r = mid - 1;  // 不可行，减小范围
        }
    }
    
    cout << l << "\n";
    return 0;
}

• Java

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

public class Main {
    // 计算小兰得到x本书时总共需要的最少书数
    static long calcNeed(long x, long n, long k) {
        long leftCnt = k - 1;  // 左侧位置数
        long rightCnt = n - k;  // 右侧位置数
        long result = x;  // 小兰的书数
        
        // 计算单侧需求的lambda函数等价实现
        result += sideCalc(x, leftCnt) + sideCalc(x, rightCnt);
        return result;
    }
    
    static long sideCalc(long x, long cnt) {
        if (x <= 1) return cnt;  // 每个位置分1本
        long decLen = Math.min(cnt, x - 1);  // 递减序列长度
        long high = x - 1, low = x - decLen;
        long sum = (high + low) * decLen / 2;  // 等差数列求和
        return sum + (cnt - decLen);  // 剩余位置分1本
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        long n = Long.parseLong(st.nextToken());
        long m = Long.parseLong(st.nextToken());
        long k = Long.parseLong(st.nextToken());
        
        long l = 1, r = m;
        while (l < r) {
            long mid = (l + r + 1) / 2;
            if (calcNeed(mid, n, k) <= m) {
                l = mid;  // 可行，尝试更大值
            } else {
                r = mid - 1;  // 不可行，减小范围
            }
        }
        
        System.out.println(l);
    }
}

02. 小毛的客户分类模型

问题描述

小毛是一家金融科技公司的数据科学家，他正在为公司的风控系统开发一个客户信用评估模型。为了提高模型的准确性，小毛需要从众多客户特征中选择最有价值的特征进行建模。

小毛决定使用决策树算法中的基尼指数作为特征选择的标准。基尼指数可以衡量数据集的不纯度，值越小表示数据越"纯净"，即分类效果越好。

给定一个客户数据集，其基尼指数的计算公式为：

其中 代表属于第 类的样本个数， 是整个数据集的样本数量。

如果数据集 根据特征 是否取某一值被分割为 两部分，那么在特征 条件下的基尼指数定义为：

小毛现在有一个客户数据集，他需要找出能使整个数据集基尼指数最小的特征，以此作为决策树的根节点分裂标准。

输入格式

输入一个二维列表，每个子列表的最后一个元素是该客户的信用标签（ 表示低风险， 表示高风险），其他元素是对应特征的值（均为 或 ）。

输出格式

输出使整个数据集基尼指数最小的特征对应的索引（从 开始计数）。

样例输入

[[0,0,0,0,0],[0,0,0,1,0],[0,1,0,1,1],[0,1,1,0,0],[0,0,0,0,0]]

样例输出

1

数据范围

• 样本数量

• 特征数量

• 特征值和标签均为 或

样例	解释说明
样例1	第2列特征（索引为1）能够最好地区分高风险和低风险客户，使得分裂后的基尼指数最小

题解

这道题目要求我们找到最优的分裂特征，本质上是一个特征选择问题。

解题思路如下：

1. 对于每个特征列，将数据按该特征的取值（0或1）分成两个子集
2. 计算每个子集的基尼指数
3. 按照权重计算条件基尼指数
4. 选择使条件基尼指数最小的特征

具体实现时，我们需要：

• 统计每个特征值对应的各类别样本数量
• 使用基尼指数公式计算不纯度
• 比较所有特征的条件基尼指数，选择最小值对应的特征索引

算法的时间复杂度为 ，其中 是样本数， 是特征数。对于给定的数据规模，这个复杂度是完全可以接受的。

参考代码

• Python

import sys
import ast

def calc_gini(cnt0, cnt1):
    """计算基尼指数"""
    total = cnt0 + cnt1
    if total == 0:
        return 0.0
    p0, p1 = cnt0 / total, cnt1 / total
    return 1.0 - p0 * p0 - p1 * p1

def solve():
    # 读取输入数据
    data = ast.literal_eval(sys.stdin.read().strip())
    m = len(data)  # 样本数
    d = len(data[0]) - 1  # 特征数
    labels = [row[-1] for row in data]  # 提取标签
    
    best_idx = -1
    best_gini = float('inf')
    
    # 遍历每个特征
    for feat_idx in range(d):
        # 统计特征值为0和1时各类别的数量
        cnt_00 = cnt_01 = cnt_10 = cnt_11 = 0
        # cnt_xy: 特征值为x，标签为y的样本数
        
        for i in range(m):
            feat_val = data[i][feat_idx]
            label_val = labels[i]
            if feat_val == 0:
                if label_val == 0:
                    cnt_00 += 1
                else:
                    cnt_01 += 1
            else:
                if label_val == 0:
                    cnt_10 += 1
                else:
                    cnt_11 += 1
        
        # 计算两个子集的大小
        subset1_size = cnt_00 + cnt_01  # 特征值为0的子集
        subset2_size = cnt_10 + cnt_11  # 特征值为1的子集
        
        # 计算条件基尼指数
        gini_cond = (subset1_size / m) * calc_gini(cnt_00, cnt_01) + \
                   (subset2_size / m) * calc_gini(cnt_10, cnt_11)
        
        if gini_cond < best_gini:
            best_gini = gini_cond
            best_idx = feat_idx
    
    print(best_idx)

if __name__ == "__main__":
    solve()

• Cpp

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

// 计算基尼指数
double calc_gini(int cnt0, int cnt1) {
    int total = cnt0 + cnt1;
    if (total == 0) return 0.0;
    double p0 = (double)cnt0 / total;
    double p1 = (double)cnt1 / total;
    return 1.0 - p0 * p0 - p1 * p1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string line;
    getline(cin, line);
    
    // 解析输入数据
    vector<vector<int>> data;
    // 简化解析，假设输入格式正确
    stringstream ss(line);
    char ch;
    ss >> ch; // 跳过 '['
    
    while (ss >> ch && ch != ']') {
        if (ch == '[') {
            vector<int> row;
            int val;
            while (ss >> val) {
                row.push_back(val);
                ss >> ch; // 读取 ',' 或 ']'
                if (ch == ']') break;
            }
            data.push_back(row);
        }
    }
    
    int m = data.size();  // 样本数
    int d = data[0].size() - 1;  // 特征数
    
    int best_idx = -1;
    double best_gini = 1e9;
    
    // 遍历每个特征
    for (int feat_idx = 0; feat_idx < d; feat_idx++) {
        int cnt_00 = 0, cnt_01 = 0, cnt_10 = 0, cnt_11 = 0;
        // cnt_xy: 特征值为x，标签为y的样本数
        
        for (int i = 0; i < m; i++) {
            int feat_val = data[i][feat_idx];
            int label_val = data[i][d];  // 最后一列是标签
            
            if