✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题（建议用时：90分钟/套）
• 对照解析查漏补缺

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

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

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

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

题目一：行李分类整理限制

1️⃣：统计每种类型行李的出现频次

2️⃣：对每种类型，取 min(频次, k) 作为可以携带的数量

3️⃣：将所有类型可携带的数量相加得到答案

难度：简单

这道题目的核心是理解字符频率统计和应用简单的贪心策略。通过对每种行李类型(字符)进行计数，然后应用限制条件，可以在O(n)的时间复杂度内高效解决问题。题目很适合初学者理解哈希表或数组计数的应用。

题目二：曼哈顿距离探测器

1️⃣：将坐标进行45°旋转变换，p = x + y, q = x - y

2️⃣：将曼哈顿距离转化为切比雪夫距离 max(|p1-p2|, |q1-q2|)

3️⃣：分情况讨论，利用哈希表和二分查找高效统计点对数量

难度：中等偏难

这道题目结合了坐标变换、数学推导和高效的数据结构应用。关键技巧是将曼哈顿距离转化为更易于处理的形式，然后通过排序和二分查找避免暴力枚举，将时间复杂度从O(n²)优化到O(n log n)。这是一道考察算法优化和数学转化能力的好题目。

题目三：树上路径权值递增

1️⃣：使用BFS/DFS预处理每个节点的父节点和深度

2️⃣：通过最近公共祖先(LCA)构造任意两点间的简单路径

3️⃣：沿着路径为节点依次增加递增的权值

难度：中等

这道题目考察树的遍历和路径处理技巧。虽然题目中的操作可能很多，但由于固定为9次，直接模拟是可行的。关键是理解如何在树中找到两点间的唯一路径，以及如何处理LCA。总体时间复杂度为O(n+q*path_len)，其中q为操作次数，实际为O(n)。题目很好地结合了树的基本操作和路径处理算法。

题目四：图像智能降维处理

1️⃣：使用NumPy库进行矩阵的奇异值分解(SVD)

2️⃣：截取前k个奇异值及对应的奇异向量

3️⃣：重构低秩近似矩阵并保留指定精度

难度：中等

这道题目结合了线性代数理论和图像处理应用，考察对奇异值分解(SVD)的理解和实现。SVD是一种强大的矩阵分解方法，可用于数据压缩、去噪和特征提取。本题通过保留最重要的k个奇异值来实现图像矩阵的低秩近似，是矩阵降维的经典应用。算法复杂度主要由SVD分解决定，为O(min(mn², m²n))。

01. 行李分类整理限制

问题描述

小毛即将参加一场重要的商务旅行，他准备了 件不同种类的行李物品，每种行李用一个小写字母表示。根据航空公司的规定，每种类型的行李最多只能携带 件，超出部分需要额外付费或放弃携带。

小毛想知道在遵守航空公司规定的情况下，他最多能携带多少件行李物品。

输入格式

第一行包含两个整数 和 ，分别表示行李物品的总数和每种类型的行李最多可携带的数量。

第二行包含一个长度为 的字符串，表示 件行李物品的类型，输入保证仅由小写字母组成。

输出格式

输出一个整数，表示在遵守规定的情况下，小毛最多能携带的行李物品数量。

样例输入

3 1
aab

样例输出

2

数据范围

• 
• 
• 输入字符串仅包含小写字母

样例 解释说明

样例1	共有3件行李物品，类型分别为a、a、b。每种类型最多携带1件，所以小毛可以带走1件a类型和1件b类型的行李，共2件。

题解

这道题目的核心是统计每种行李物品的数量，然后根据限制条件计算最多能携带多少件。

首先，我们需要理解题目的要求：每种类型的行李最多只能携带 件。这里的"类型"是指小写字母表示的不同种类的行李。

解题思路非常直接：

1. 统计每个小写字母（即每种行李类型）出现的频次
2. 对于每种类型，我们最多能带 件，因此实际能带的是该类型的数量和 的较小值
3. 将所有类型能带的数量相加，即为答案

举个例子，假设输入为"aab"，k=1，那么：

• 'a'出现了2次，但最多只能带1件，所以能带1件'a'类型的行李
• 'b'出现了1次，不超过限制，所以能带1件'b'类型的行李
• 总共能带1+1=2件行李

时间复杂度分析：

• 统计频次需要遍历一次输入字符串，时间复杂度为O(n)
• 计算每种类型能带多少件需要遍历26个小写字母，时间复杂度为O(1)
• 总体时间复杂度为O(n)

对于给定的数据范围（n≤10^5），这个算法可以很轻松地解决问题。

参考代码

• Python

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

# 读取输入
n, k = map(int, input().split())
items = input()

# 统计每种行李的数量
freq = {}
for item in items:
    freq[item] = freq.get(item, 0) + 1

# 计算最多能带多少件行李
total = 0
for item_type, count in freq.items():
    # 每种类型最多带k件
    total += min(count, k)

# 输出结果
print(total)

• Cpp

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    
    // 统计每种行李的数量
    vector<int> cnt(26, 0);
    for (char c : s) {
        cnt[c - 'a']++;
    }
    
    // 计算最多能带多少件行李
    int ans = 0;
    for (int i = 0; i < 26; ++i) {
        ans += min(cnt[i], k);
    }
    
    cout << ans << "\n";
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        String s = br.readLine();
        
        // 统计每种行李的数量
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        
        // 计算最多能带多少件行李
        int result = 0;
        for (int i = 0; i < 26; i++) {
            result += Math.min(count[i], k);
        }
        
        System.out.println(result);
    }
}

02. 曼哈顿距离探测器

问题描述

小兰正在研发一种城市交通探测器，该探测器能够检测城市中任意两个位置之间的曼哈顿距离是否恰好为特定值。曼哈顿距离是在直角坐标系中，两点之间横坐标差的绝对值与纵坐标差的绝对值之和，形如： 和 之间的曼哈顿距离为 。

现在，小兰需要测试这个探测器的性能。她在城市地图上标记了 个点，并希望知道有多少对点之间的曼哈顿距离恰好为 。需要注意的是，点对 和点对 被视为同一个点对，不会重复计算。

输入格式

第一行包含两个正整数 和 ，分别表示标记点的数量和指定的曼哈顿距离值。

接下来的 行，每行包含两个整数 和 ，表示第 个标记点的坐标。

输出格式

输出一个整数，表示曼哈顿距离恰好为 的点对数量。

样例输入

4 1
0 1
1 0
1 1
0 0

样例输出

4

数据范围

• 
• 
• 

样例 解释说明

样例1	曼哈顿距离为1的点对有4对： (0,1)和(1,1)的距离为1 (0,1)和(0,0)的距离为1 (1,0)和(1,1)的距离为1 (1,0)和(0,0)的距离为1

题解

这道题乍看起来似乎需要暴力枚举所有点对并计算它们的曼哈顿距离，但这样的方法时间复杂度为 ，对于 最大为 的数据规模来说是不可接受的。我们需要一个更高效的解法。

关键的数学变换是将曼哈顿距离转化为切比雪夫距离。具体做法是将原坐标 进行45°旋转变换，得到新坐标 ：

• 
• 

在这种变换下，原本的曼哈顿距离 变为了切比雪夫距离 。

利用这个性质，我们要找曼哈顿距离恰好为 的点对，可以分为两种情况：

1. 且
2. 且

对于每种情况，我们可以按 值或 值分组，然后对每组中的点进行排序，通过双指针高效地找出满足条件的点对。

算法步骤：

1. 将所有点按变换后的 和 坐标分组存储
2. 对于情况1，遍历所有 值，查找距离恰好为 的另一组点，通过双指针找出满足 的点对
3. 对于情况2，遍历所有 值，查找距离恰好为 的另一组点，通过双指针找出满足 的点对
4. 将两种情况的计数相加得到最终答案

时间复杂度分析：

• 坐标变换和分组需要 时间
• 排序需要 时间
• 双指针查找需要 时间
• 总体时间复杂度为 ，空间复杂度为

对于给定的数据范围，这个算法可以高效地解决问题。

参考代码

• Python

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

# 读取输入
n, k = map(int, input().split())
points = []
for _ in range(n):
    x, y = map(int, input().split())
    # 坐标变换：p = x+y, q = x-y
    p, q = x + y, x - y
    points.append((p, q))

# 按p和q分组
p_groups = defaultdict(list)
q_groups = defaultdict(list)
for p, q in points:
    p_groups[p].append(q)
    q_groups[q].append(p)

# 对每个组内的值排序
for p in p_groups:
    p_groups[p].sort()
for q in q_groups:
    q_groups[q].sort()

ans = 0
# 情况1：|p1-p2| = k 且 |q1-q2| ≤ k
for p in p_groups:
    if p + k in p_groups:
        for q in p_groups[p]:
            # 二分查找满足条件的q值范围
            left = 0
            right = len(p_groups[p + k])
            # 找到q-k的位置
            low = 0
            high = right - 1
            while low <= high:
                mid = (low + high) // 2
                if p_groups[p + k][mid] < q - k:
                    low = mid + 1
                else:
                    high = mid - 1
            left = low
            
            # 找到q+k的位置
            low = 0
            high = right - 1
            while low <= high:
                mid = (low + high) // 2
                if p_groups[p + k][mid] <= q + k:
                    low = mid + 1
                else:
                    high = mid - 1
            right = low
            
            ans += (right - left)

# 情况2：|q1-q2| = k 且 |p1-p2| < k
for q in q_groups:
    if q + k in q_groups:
        for p in q_groups[q]:
            # 二分查找满足条件的p值范围
            left = 0
            right = len(q_groups[q + k])
            # 找到p-(k-1)的位置
            low = 0
            high = right - 1
            while low <= high:
                mid = (low + high) // 2
                if q_groups[q + k][mid] < p - (k - 1):
                    low = mid + 1
                else:
                    high = mid - 1
            left = low
            
            # 找到p+(k-1)的位置
            low = 0
            high = right - 1
            while low <= high:
                mid = (low + high) // 2
                if q_groups[q + k][mid] <= p + (k - 1):
                    low = mid + 1
                else:
                    high = mid - 1
            right = low
            
            ans += (right - left)

print(ans)

• Cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    ll k;
    cin >> n >> k;
    
    // 读取点并转换坐标
    vector<pair<ll, ll>> pts(n);
    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        pts[i] = {x + y, x - y}; // p, q
    }
    
    // 按p和q分组
    unordered_map<ll, vector<ll>> p_map, q_map;
    for (auto &pt : pts) {
        p_map[pt.first].push_back(pt.second);
        q_map[pt.second].push_back(pt.first);
    }
    
    // 对每组排序
    for (auto &kv : p_map) sort(kv.second.begin(), kv.second.end());
    for (auto &kv : q_map) sort(kv.second.begin(), kv.second.end());
    
    ll ans = 0;
    
    // 情况1：|p1-p2| = k, |q1-q2| ≤ k
    for (auto &kv : p_map) {
        ll p = kv.first;
        auto it = p_map.find(p + k);
        if (it == p_map.end()) continue;
        
        auto &v1 = kv.second;
        auto &v2 = it->second;
        
        for (ll q : v1) {
            // 找到q-k和q+k的位置
            auto lo = lower_bound(v2.begin(), v2.end(), q - k);
            auto hi = upper_bound(v2.begin(), v2.end(), q + k);
            ans += (hi - lo);
        }
    }
    
    // 情况2：|q1-q2| = k, |p1-p2| < k
    for (auto &kv : q_map) {
        ll q = kv.first;
        auto it = q_map.find(q + k);
        if (it == q_map.end()) continue;
        
        auto &v1 = kv.second;
        auto &v2 = it->second;
        
        for (ll p : v1) {
            // 找到p-(k-1)和p+(k-1)的位置
            auto lo = lower_bound(v2.begin(), v2.end(), p - (k - 1));
            auto hi = upper_bound(v2.begin(), v2.end(), p + (k - 1));
            ans += (hi - lo);
        }
    }
    
    cout << ans << "\n";
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        long k = Long.parseLong(st.nextToken());
        
        // 读取点并转换坐标
        List<long[]> points = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long y = Long.parseLong(st.nextToken());
            points.add(new long[]{x + y, x - y}); // p, q
        }
        
        // 按p和q分组
        Map<Long, List<Long>> pMap = new HashMap<>();
        Map<Long, List<Long>> qMap = new HashMap<>();
        
        for (long[] point : points) {
            long p = point[0];
            long q = point[1];
            
            if (!pMap.containsKey(p)) {
                pMap.put(p, new ArrayList<>());
            }
            pMap.get(p).add(q);
            
            if (!qMap.containsKey(q)) {
                qMap.put(q, new ArrayList<>());
            }
            qMap.get(q).add(p);
        }
        
        // 对每组排序
        for (List<Long> list : pMap.values()) {
            Collections.sort(list);
        }
        
        for (List<Long> list : qMap.values()) {
            Collections.sort(list);
        }
        
        long ans = 0;
        
        // 情况1：|p1-p2| = k, |q1-q2| ≤ k
        for (Map.Entry<Long, List<Long>> entry : pMap.entrySet()) {
            long p = entry.getKey();
            List<Long> qList = entry.getValue();
            
            if (pMap.containsKey(p + k)) {
                List<Long> qList2 = pMap.get(p + k);
                
                for (long q : qList) {
                    // 二分查找满足条件的范围
                    int left = binarySearchLower(qList2, q - k);
                    int right = binarySearchUpper(qList2, q + k);
                    ans += (right - left);
                }
            }
        }
        
        // 情况2：|q1-q2| = k, |p1-p2| < k
        for (Map.Entry<Long, List<Long>>