✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：光辉宝石收集

1️⃣：理解宝石融合操作本质，将问题转化为数组重新分配

2️⃣：贪心策略：正数全部集中到第一个位置，最大化前缀和

3️⃣：特殊情况处理：无正数时根据数组长度决定答案

难度：中等

这道题目的关键在于理解融合操作的本质是重新分配数组元素，通过贪心策略将所有正数集中到第一个位置，利用前缀最大值的单调性来最大化答案。时间复杂度 O(n)。

题目二：森林救援站分配

1️⃣：将每个探险者的可选救援站转化为连续区间

2️⃣：问题转化为经典的区间选点最大匹配问题

3️⃣：贪心策略：按右端点排序，优先选择最左边的可用位置

4️⃣：使用并查集优化查找下一个可用位置

难度：中等

这道题目巧妙地将二维坐标问题转化为一维区间调度问题。关键洞察是每个探险者的最近救援站集合形成连续区间，然后使用经典的贪心算法求解最大匹配。

题目三：魔法能量波动监测

1️⃣：将方差公式数学变换为便于维护的形式

2️⃣：使用两个树状数组分别维护区间和与区间平方和

3️⃣：单点修改时同时更新两个树状数组

4️⃣：区间查询时通过公式直接计算方差

难度：中等

这道题目结合了数学公式变换和数据结构应用。通过将方差公式转化为 Q/m - (S/m)² 的形式，避免了复杂的均值计算，使得树状数组可以高效维护所需信息。时间复杂度 O((n+q)log n)。

01. 光辉宝石收集

问题描述

小兰正在一个神秘的魔法世界中探险，她发现了 颗散落在地面的光辉宝石。每颗宝石都有一个能量值，第 颗宝石的能量值为 。

根据古老的魔法书记载，小兰可以使用特殊的魔法进行宝石融合：

• 选择两颗不同的宝石 和 （其中 且 ），将宝石 的所有能量转移到宝石 上，此时宝石 的能量值变为 ，而宝石 的能量值变为 。

小兰想要最大化她的魔法力量。根据魔法原理，她的总魔法力量等于所有位置上的前缀最大能量值之和，即：

请你帮助小兰计算在进行若干次宝石融合操作后，她能获得的最大魔法力量。

输入格式

每个测试文件包含多组测试数据。第一行输入一个整数 （），表示测试数据的组数。

对于每组测试数据：

第一行输入一个整数 （），表示宝石的数量。

第二行输入 个整数 （），表示每颗宝石的初始能量值。

保证所有测试数据中 的总和不超过 。

输出格式

对于每组测试数据，输出一个整数，表示小兰能获得的最大魔法力量。

样例输入

2
3
3 2 -1
1
-1

样例输出

15
-1

样例	解释说明
样例1	选择宝石1和宝石2进行融合（），操作后宝石能量变为 ，总魔法力量为
样例2	只有一颗宝石且能量为负，无法进行融合操作，最大魔法力量为

数据范围

• 
• 
• 
• 所有测试数据中 的总和不超过

题解

这道题的关键在于理解宝石融合操作的本质：每次操作都是将一颗宝石的能量转移到另一颗宝石上，并将原宝石的能量清零。经过多次操作后，所有宝石的能量都可以重新分配到不同位置上。

要最大化前缀最大值之和，最优策略是：

1. 当存在正能量宝石时：将所有正能量都集中到第一个位置。这样第一个位置的值 （所有正数之和）会成为所有前缀的最大值，答案就是 。

2. 当不存在正能量宝石时：

   • 如果 ，可以通过操作让某个位置变成 （将负数转移走），使得所有前缀最大值都为 ，答案为 。
   • 如果 ，无法进行操作，答案只能是原来的 。

这个策略的正确性在于：前缀最大值具有单调性，如果第一个位置是所有正数之和，那么它必然是后续所有前缀的最大值。

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

参考代码

• Python

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

# 读取测试数据组数
t = int(input())
while t > 0:
    t -= 1
    # 读取宝石数量
    n = int(input())
    # 读取宝石能量值
    gems = list(map(int, input().split()))
    
    # 计算所有正能量的总和
    pos_sum = sum(x for x in gems if x > 0)
    
    # 根据情况计算答案
    if pos_sum > 0:
        # 存在正能量，将其全部集中到第一个位置
        result = pos_sum * n
    else:
        # 不存在正能量
        if n == 1:
            # 只有一颗宝石，无法操作
            result = gems[0]
        else:
            # 多颗宝石，可以让某个位置变成0
            result = 0
    
    print(result)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        
        ll pos = 0; // 正数总和
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] > 0) {
                pos += a[i];
            }
        }
        
        ll ans;
        if (pos > 0) {
            // 存在正数，答案是正数总和乘以n
            ans = pos * n;
        } else {
            // 不存在正数
            if (n == 1) {
                ans = a[0]; // 只有一个元素，无法操作
            } else {
                ans = 0; // 可以通过操作让前缀最大值都为0
            }
        }
        
        cout << ans << "\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[] input = br.readLine().split(" ");
            int[] gems = new int[n];
            
            long posSum = 0; // 正数能量总和
            for (int i = 0; i < n; i++) {
                gems[i] = Integer.parseInt(input[i]);
                if (gems[i] > 0) {
                    posSum += gems[i];
                }
            }
            
            long result;
            if (posSum > 0) {
                // 存在正能量，集中到第一个位置
                result = posSum * n;
            } else {
                // 不存在正能量
                if (n == 1) {
                    // 只有一颗宝石，无法融合
                    result = gems[0];
                } else {
                    // 多颗宝石，可以操作让前缀最大值为0
                    result = 0;
                }
            }
            
            System.out.println(result);
        }
    }
}

02. 森林救援站分配

问题描述

在一片 的森林中，发生了紧急情况。森林中有 名探险者被困，他们分别位于坐标 处（）。

为了应对紧急情况，森林管理部门在对角线上设置了 个救援站，分别位于坐标 （）。每个救援站只能救援一名探险者，一旦有人到达救援站，该救援站就会关闭。

每名探险者可以在森林中移动，每次移动可以到达与当前位置四连通的相邻格子（即上下左右四个方向）。探险者会选择距离自己最近的救援站作为目标（按曼哈顿距离计算）。如果有多个救援站距离相等，探险者们会协调分配，以使最终获救的人数最大化。

请计算在最优分配策略下，最多有多少名探险者能够成功获救。

【名词解释】

• 四连通：当 时，位置 与 四连通，可以直接移动。

• 曼哈顿距离：两点 和 之间的曼哈顿距离为 。

输入格式

第一行输入两个整数 和 （），分别表示森林的边长和被困探险者的数量。

接下来 行，每行输入两个整数 和 （），表示第 名探险者的位置坐标。

输出格式

输出一个整数，表示最多能够获救的探险者数量。

样例输入

2 3
1 2
2 1
1 1

4 3
1 2
1 2
1 2

样例输出

2

2

样例	解释说明
样例1	森林中有2个救援站： 和 。3名探险者分别在 、、。由于救援站数量限制，最多只能救援2人
样例2	森林中有4个救援站：、、、。3名探险者都在 ，距离最近的救援站是 和 （距离都为1），所以最多救援2人

数据范围

题解

这道题可以转化为一个经典的区间调度问题。

首先分析每个探险者可以选择的救援站。对于位于 的探险者，到救援站 的曼哈顿距离是 。

设 ，，可以发现：

• 当 时，距离恒为
• 当 或 时，距离会增大

因此，每个探险者的最近救援站集合是一个连续区间 ，最近距离为 。

问题转化为：给定 个区间（每个探险者对应一个区间），有 个点（救援站），每个点容量为1，求最多能匹配多少个区间。

这是经典的区间选点问题，贪心策略如下：

1. 按右端点升序排序所有区间
2. 依次处理每个区间，尽量分配给区间内最左边的未被占用的救援站
3. 使用并查集优化查找下一个可用位置

算法的正确性可以通过交换论证来证明：如果某个区间选择了靠右的救援站，我们总可以将其换到靠左的位置而不影响后续区间的选择。

时间复杂度：，其中排序需要 ，并查集操作摊还复杂度接近线性。

参考代码

• Python

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

class DSU:
    def __init__(self, n):
        # parent[i] 表示 >= i 的最小可用救援站
        self.par = list(range(n + 2))  # 哨兵：parent[n+1] = n+1
    
    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]
    
    def occupy(self, x):
        # 标记位置x被占用，指向下一个可用位置
        self.par[x] = self.find(x + 1)

# 读入数据
n, m = map(int, input().split())
segs = []

for _ in range(m):
    x, y = map(int, input().split())
    l, r = min(x, y), max(x, y)
    segs.append((l, r))

# 按右端点排序
segs.sort(key=lambda seg: seg[1])

# 贪心分配
dsu = DSU(n)
ans = 0

for l, r in segs:
    pos = dsu.find(l)  # 找到 >= l 的最小可用位置
    if pos <= r:  # 如果在区间内
        ans += 1
        dsu.occupy(pos)  # 占用该位置

print(ans)

• Cpp

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

struct DSU {
    vector<int> par;
    
    DSU(int n) : par(n + 2) {
        // 初始化：parent[i] = i，parent[n+1] = n+1 作为哨兵
        iota(par.begin(), par.end(), 0);
    }
    
    int find(int x) {
        return par[x] == x ? x : par[x] = find(par[x]);
    }
    
    void occupy(int x) {
        // 将位置x标记为被占用，指向下一个可用位置
        par[x] = find(x + 1);
    }
};

struct Seg {
    int l, r;
};

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