✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：魔法增强数组

1️⃣：分析二进制位级限制，确定每个元素的最大可能值

2️⃣：通过 OR 运算性质，使用全1掩码实现快速增幅

3️⃣：根据当前状态判断最小增幅器值

难度：中等

这道题目的关键在于理解 OR 运算的性质以及二进制位级的概念。通过数学分析可以发现，在给定位级限制下，使用全1掩码可以让任何元素达到该位级的最大值，从而获得最优解。

题目二：客户信用评估系统

1️⃣：解析 JSON 输入数据，分离特征和标签

2️⃣：实现高斯朴素贝叶斯算法，计算先验概率和条件概率参数

3️⃣：使用对数概率避免数值下溢，选择最大后验概率的类别

难度：中等

这道题目结合了数据处理和机器学习算法，需要理解朴素贝叶斯分类器的数学原理。通过条件独立假设和高斯分布建模，可以有效处理连续特征的分类问题。

题目三：时空传送门网络

1️⃣：建立状态空间模型，将城市和已使用次数组合为状态

2️⃣：使用带状态限制的最短路算法（SPFA）

3️⃣：处理负权边，通过双端队列优化算法效率

难度：中等偏难

这道题目需要将带约束的最短路问题转化为状态图上的最短路问题。关键是理解如何将"使用次数限制"编码到状态中，并正确处理负权边的情况。

题目四：古塔能量波动

1️⃣：将三元组计数问题转化为枚举中间元素的算法

2️⃣：使用线段树维护左右两侧的统计信息

3️⃣：通过离散化处理大数值范围，实现高效的区间查询和更新

难度：困难

这道题目是经典的逆序对变形问题，需要设计高效的数据结构来维护动态的统计信息。通过线段树的懒标记和区间操作，可以在 O(n log n) 时间内解决问题。

01. 魔法增强数组

问题描述

小基 同学在魔法学院学习魔法阵的构造技巧。现在她有一个由 个魔法水晶组成的魔法阵，每个水晶都有一个能量值 。

为了增强魔法阵的威力，小基 可以选择一个魔法增幅器，其增幅值为非负整数 。但是有一个重要限制：增幅器的魔法位级不能超过魔法阵中最强水晶的魔法位级。魔法位级的定义如下：

• 如果一个水晶的能量值为 ，其魔法位级为
• 如果一个水晶的能量值为正整数 ，其魔法位级为该值二进制表示的位数

一旦选定增幅器，小基 可以对魔法阵中的任意水晶进行增幅操作（可重复多次）：

• 选择一个位置 ，将水晶 的能量值变为 （按位或运算）

小基 希望在让魔法阵总能量尽可能大的前提下，使用的增幅操作次数尽可能少。

请帮助 小基 计算出魔法阵能达到的最大总能量，以及在达到最大总能量时所需的最小增幅器值 。

输入格式

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

对于每组测试数据：

• 第一行包含一个正整数 ，表示魔法水晶的数量。
• 第二行包含 个非负整数 ，表示每个魔法水晶的初始能量值。

输出格式

对于每组测试数据，输出一行两个整数，用空格分隔：

1. 魔法阵能达到的最大总能量
2. 在达到最大总能量时的最小增幅器值

样例输入

2
2
3 3
3
1 2 3

样例输出

6 0
9 3

数据范围

• 
• 
• 

样例	解释说明
样例1	魔法阵 中最大值为 ，其魔法位级为 。在位级限制内能达到的最大值为 。所有水晶已经是最大值，无需增幅，所以 ，总能量为 。
样例2	魔法阵 中最大值为 ，其魔法位级为 。在位级限制内能达到的最大值为 。使用增幅器 ，可以将所有水晶都变为 ，总能量为 。

题解

这道题目的关键在于理解位运算中 OR 操作的性质以及如何在位级限制下最大化数组总和。

首先分析题目本质：我们需要找到一个增幅器值 ，使得通过 OR 操作让数组总和最大。由于 OR 操作只能增加或保持位的值（1 OR 0 = 1，0 OR 0 = 0），因此要想让总和最大，最直接的想法就是让每个元素都尽可能大。

在给定位级限制下，任何数能达到的最大值就是该位级下的"全1数"。例如，如果位级为3，那么最大值就是 111₂ = 7₁₀ = 2³-1。

算法步骤如下：

1. 计算位级限制：找到数组中的最大值，计算其二进制位数，这就是增幅器的位级上限。
2. 确定理论最大值：在该位级下，每个元素能达到的最大值为 full = 2^位级 - 1。
3. 计算最大总和：所有元素都变为 full 时，总和为 n × full。
4. 确定最小增幅器值：
   • 如果所有元素已经等于 full，则不需要任何操作，x = 0
   • 否则，使用 x = full 可以让任何元素通过一次 OR 操作变为 full

关键观察：对于任意数 a 和 full = 2^k - 1，都有 a OR full = full。这是因为 full 在所有 k 位上都是1，OR操作会让结果在所有位置都变成1。

时间复杂度为 O(n)，空间复杂度为 O(1)。

参考代码

Python

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

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    
    # 找到最大值并计算其位级
    max_val = max(a)
    if max_val == 0:
        bit_len = 1
    else:
        bit_len = max_val.bit_length()
    
    # 计算该位级下的最大值（全1掩码）
    full_mask = (1 << bit_len) - 1
    
    # 最大可能总和
    max_sum = n * full_mask
    
    # 检查是否所有元素都已经是最大值
    all_max = all(x == full_mask for x in a)
    
    # 确定最小增幅器值
    min_x = 0 if all_max else full_mask
    
    return max_sum, min_x

T = int(input())
for _ in range(T):
    max_sum, min_x = solve()
    print(max_sum, min_x)

Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        long long max_val = 0;
        
        // 读取数据并找最大值
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            max_val = max(max_val, a[i]);
        }
        
        // 计算位级长度
        int bit_len = (max_val == 0) ? 1 : 64 - __builtin_clzll(max_val);
        
        // 计算全1掩码
        long long mask = (1LL << bit_len) - 1;
        
        // 计算最大总和
        long long total = (long long)n * mask;
        
        // 检查是否所有元素都已经是最大值
        bool need_boost = false;
        for (int i = 0; i < n; i++) {
            if (a[i] != mask) {
                need_boost = true;
                break;
            }
        }
        
        // 输出结果
        long long min_x = need_boost ? mask : 0;
        cout << total << " " << min_x << "\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 T = Integer.parseInt(br.readLine());
        
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            String[] tokens = br.readLine().split(" ");
            long[] arr = new long[n];
            long maxValue = 0;
            
            // 读取数组并找最大值
            for (int i = 0; i < n; i++) {
                arr[i] = Long.parseLong(tokens[i]);
                maxValue = Math.max(maxValue, arr[i]);
            }
            
            // 计算位级长度
            int bitLength = (maxValue == 0) ? 1 : 64 - Long.numberOfLeadingZeros(maxValue);
            
            // 计算全1掩码
            long fullMask = (1L << bitLength) - 1;
            
            // 计算最大可能总和
            long maxSum = (long) n * fullMask;
            
            // 检查是否需要增幅
            boolean needAmplify = false;
            for (int i = 0; i < n; i++) {
                if (arr[i] != fullMask) {
                    needAmplify = true;
                    break;
                }
            }
            
            // 确定最小增幅器值
            long minX = needAmplify ? fullMask : 0;
            
            System.out.println(maxSum + " " + minX);
        }
    }
}

02. 客户信用评估系统

问题描述

小柯在银行工作，负责开发一套客户信用评估系统。该系统需要根据客户的历史数据来预测新客户的信用等级。

银行收集了大量客户的特征数据，每个客户都有若干个数值特征（如年龄、收入、负债比率等），以及对应的信用等级标签（0 表示信用良好，1 表示信用风险较高）。

小柯决定使用高斯朴素贝叶斯分类器来构建这个评估系统。请你帮助她实现这个分类器，要求只使用 numpy 和 pandas 库。

算法流程如下：

1. 数据处理

   • 从输入的 JSON 数据中提取训练集和测试集
   • 训练集每行最后一列为标签 ，其余为特征值

2. 参数估计

   • 计算每个类别的先验概率：
   • 在条件独立假设下，计算每个特征在每个类别下的均值 和方差
   • 使用总体方差计算（ddof=0），如果方差为 0，则设为

3. 预测计算

   • 使用对数后验概率避免数值下溢：
   • 选择对数后验概率最大的类别作为预测结果

输入格式

输入为一行 JSON 格式数据：

{
  "train": [[特征1, 特征2, ..., 标签], [特征1, 特征2, ..., 标签], ...],
  "test": [[特征1, 特征2, ...], [特征1, 特征2, ...], ...]
}

其中：

• train 包含训练样本，每行包含 个特征值和 1 个标签
• test 包含待预测样本，每行包含 个特征值
• 所有数值均为浮点数或整数

输出格式

输出一行 JSON 数组，包含测试集中每个样本的预测标签（0 或 1）。

样例输入

{"train": [[1,1,0], [1,1,0.9,0], [4,4,1], [4,2,3.8,1]], "test": [[1,1], [4,4]]}

样例输出

[0,1]

数据范围

• 训练样本数
• 测试样本数
• 特征维度
• 特征值范围：

样例	解释说明
样例1	训练集有4个样本，前两个标签为0（特征值较小），后两个标签为1（特征值较大）。测试样本 [1,1] 与标签0的样本更相似，预测为0；[4,4] 与标签1的样本更相似，预测为1。

题解

高斯朴素贝叶斯是一种基于贝叶斯定理和特征条件独立假设的分类算法。它假设每个特征在给定类别下服从高斯分布。

算法的核心思想是利用贝叶斯定理：

由于分母对所有类别都相同，我们只需要比较分子部分。在条件独立假设下：

对于高斯分布， 的概率密度函数为：

为避免数值下溢，我们使用对数形式进行计算：

具体实现步骤：

1. 分离训练集的特征和标签
2. 计算每个类别的先验概率、特征均值和方差
3. 对测试样本计算对数后验概率
4. 选择概率最大的类别

时间复杂度：O(训练样本数 × 特征数 + 测试样本数 × 特征数 × 类别数)

参考代码

Python

import sys
import json
import numpy as np

def gaussian_nb_predict(train_data, test_data):
    """
    高斯朴素贝叶斯分类器
    """
    # 转换为numpy数组并分离特征和标签
    train_array = np.array(train_data, dtype=float)
    features = train_array[:, :-1]  # 所有列除了最后一列
    labels = train_array[:, -1].astype(int)  # 最后一列作为标签
    
    n_samples = len(labels)
    classes = np.unique(labels)  # 获取所有类别
    
    # 计算每个类别的先验概率
    class_priors = {}
    for cls in classes:
        class_priors[cls] = np.sum(labels == cls) / n_samples
    
    # 计算每个类别下每个特征的均值和方差
    class_means = {}
    class_vars = {}
    
    for cls in classes:
        # 获取该类别的所有样本
        cls_features = features[labels == cls]
        # 计算均值
        class_means[cls] = np.mean(cls_features, axis=0)
        # 计算方差（总体方差，ddof=0）
        class_vars[cls] = np.var(cls_features, axis=0, ddof=0)
        # 处理方差为0的情况
        class_vars[cls][class_vars[cls] == 0] = 1e-9
    
    # 对测试集进行预测
    predictions = []
    
    for test_sample in test_data:
        test_sample = np.array(test_sample, dtype=float)
        log_probs = {}
        
        # 为每个类别计算对数后验概率
        for cls in classes:
            mu = class_means[cls]
            var = class_vars[cls]
            
            # 对数先验概率
            log_prior = np.log(class_priors[cls])
            
            # 对数似然概率（高斯分布的对数形式）
            log_likelihood = -0.5 * np.sum(
                np.log(2 * np.pi * var) + (test_sample - mu) ** 2 / var
            )
            
            # 对数后验概率
            log_probs[cls] = log_prior + log_likelihood
        
        # 选择概率最大的类别
        predicted_class = max(log_probs, key=log_probs.get)
        predictions.append(int(predicted_class))
    
    return predictions

def main():
    # 读取JSON输入
    input_data = json.loads(sys.stdin.read())
    
    # 进行预测
    results = gaussian_nb_predict(input_data['train'], input_data['test'])
    
    # 输出JSON格式结果
    print(json.dumps(results, ensure_ascii=False))

if __name__ == '__main__':
    main()

03. 时空传送门网络

问题描述

小兰是一位时空魔法师，她需要在 个城市之间建立传送门网络。这些城市编号为 到 ，之间有 条双向传送通道，第 条通道连接城市 和 ，基础传送时间为 。

每个城市都配备了一个时空魔法装置，具有不同的时间调节能力：

• 时间加速装置（调节值为负数）：可以选择是否启动。启动后能够减少传送时间，减少的时间等于调节值的绝对值。
• 时间减速装置（调节值为非负数）：会被动触发，强制增加传送时间，增加的时间等于调节值。

小兰在一次旅程中最多只能启动 次时间加速装置，超过次数后就无法再使用任何加速装置。

当 小兰从城市 传送到城市 时，实际传送时间计算如下：

小兰可以重复经过任何城市和通道。请帮助她计算从城市 到城市 的最短实际传送时间。如果无法到达，请输出 NO。

输入格式

第一行包含三个正整数 ，分别表示城市数量、传送通道数量和最大加速装置使用次数。

第二行包含 个整数 ，表示每个城市的时间调节装置的调节值。

接下来 行，每行包含三个正整数 ，表示一条连接城市 和 的双向传送通道，基础传送时间为 。

输出格式

如果无法从城市 到达城市 ，输出 NO。

否则输出一个整数，表示从城市 到城市 的最短实际传送时间。

样例输入

5 5 2
0 0 0 -10 0 
1 2 1
2 3 1
3 5 1
1 4 6 
4 5 1

样例输出

-13

数据范围

• 
• 
• 
• 
• 
• 

样例	解释说明
样例1	最优路径为 。每步实际时间分别为：，总时间为 。在城市5使用了2次加速装置。

题解

这是一个带有状态限制的最短路问题。关键思路是将"城市"和"已使用加速装置次数"组合成一个新的状态空间。

我们可以将问题建模为在状态图 上的最短路问题，其中：

• 表示当前所在的城市（）
• 表示已经使用的加速装置次数（）

状态转移规则：

1. 从状态 通过边 转移：
   • 如果城市 的装置为减速装置（）：只能转移到状态 ，代价为
   • 如果城市 的装置为加速装置（）：
     • 不启动：转移到状态 ，代价为
     • 启动（当 时）：转移到状态 ，代价为

算法实现：

1. 使用带权重的图论算法（如Dijkstra或SPFA）在状态图上求最短路
2. 起始状态为 ，目标是
3. 由于可能存在负权边，推荐使用SPFA算法

由于存在负权边，可以使用双端队列优化的SPFA：

• 如果当前边的权重非负，将新状态加入队尾
• 如果当前边的权重为负，将新状态加入队头

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

参考代码

Python

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

def solve():
    n, m, k = map(int, input().split())
    a = [0] + list(map(int, input().split()))  # 1-indexed
    
    # 构建邻接表
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # 距离数组：dist[u][j] 表示到达城市u且使用了j次加速装置的最短时间
    INF = float('inf')
    dist = [[INF] * (k + 1) for _ in range(n + 1)]
    in_queue = [[False] * (k + 1) for _ in range(n + 1)]
    
    # 双端队列SPFA
    dq = deque()
    dist[1][0] = 0
    dq.append((1, 0))
    in_queue[1][0] = True
    
    while dq:
        u, used = dq.popleft()
        in_queue[u][used] = False
        
        current_dist = dist[u][used]
        
        for v, w in graph[u]:
            # 情况1：减速装置或不使用加速装置
            if a[u] >= 0:  # 减速装置
                cost = w + a[u]
            else:  # 加速装置，选择不使用
                cost = w
            
            if current_dist + cost < dist[v][used]:
                dist[v][used] = current_dist + cost
                if not in_queue[v][used]:
                    if cost >= 0:
                        dq.append((v, used))
                    else:
                        dq.appendleft((v, used))
                    in_queue[v][used] = True
            
            # 情况2：使用加速装置（如果可用）
            if a[u] < 0 and used < k:
                cost = w + a[u]  # 使用加速装置
                if current_dist + cost < dist[v][used + 1]:
                    dist[v][used + 1] = current_dist + cost
                    if not in_queue[v][used + 1]:
                        if cost >= 0:
                            dq.append((v, used + 1))
                        else:
                            dq.appendleft((v, used + 1))
                        in_queue[v][used + 1] = True
    
    # 找到到达城市n的最短时间
    ans = min(dist[n][j] for j in range(k + 1))
    
    if ans == INF:
        print("NO")
    else:
        print(ans)

solve()

Cpp

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

const ll INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, k;
    cin >> n >> m >>