✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

携程

题目一：字符串相似度判定

1️⃣：对每个字符串去重，只保留每个字母第一次出现的位置

2️⃣：比较两个去重后的字符串是否相同

难度：简单

这道题目的关键在于理解"去重"操作，即只保留每个字母第一次出现的位置。通过使用一个布尔数组来记录每个字母是否已出现，我们可以在O(n)的时间复杂度内完成去重操作，然后比较两个处理后的字符串是否相同。

题目二：人才资源优化配置

1️⃣：将任务按能力值要求从小到大排序

2️⃣：计算前缀最大收益，找出每个能力阈值下的最佳任务

3️⃣：对每个员工二分查找能完成的最优任务

难度：中等

这道题目考察了贪心策略和二分查找，关键是理解每个员工应该被分配到他能完成的、收益最高的任务上。通过排序和前缀最大值的预处理，我们可以快速找到每个员工的最优分配，实现O((n+m)log n)的算法。

题目三：数列分解问题

1️⃣：推导连续非负整数序列之和的数学公式

2️⃣：验证计算出的起始值是否为非负整数

难度：中等

这道题目主要考察数学推导和大整数处理。通过等差数列求和公式，我们可以得出一个数 n 能否被分解为 m 个连续非负整数的判定条件：(n-m*(m-1)/2) 必须是非负的且能被 m 整除。实现时需要注意处理大整数溢出问题。

题目四：双三角覆盖最小圆

1️⃣：枚举所有点对，计算以点对为直径的圆

2️⃣：枚举所有三点组合，计算外接圆

3️⃣：验证每个候选圆是否覆盖所有点，取半径最小值

难度：困难

这道题目考察计算几何中的最小覆盖圆问题。通过枚举所有可能的点对和三点组合，我们可以得到所有可能的候选圆，然后选取能覆盖所有点的最小圆。需要熟练掌握外接圆的计算公式，并处理浮点数精度问题。

01. 字符串相似度判定

问题描述

小基最近在做一个文本分析系统，她发现很多时候需要判断两个字符串是否相似。她定义的相似规则如下：首先将每个字符串中的每个字母去重（若一个字母多次出现，只保留第一次出现的位置），然后比较两个去重后的字符串是否完全一致。如果一致，则认为这两个原始字符串相似。

现在小基有多组字符串对需要判断，请你帮她写一个程序来自动判断每组字符串对是否相似。

输入格式

每个测试文件包含多组测试数据。

第一行输入一个整数 ，代表数据组数。

对于每组测试数据： 输入两行，每行一个字符串，分别代表 和 。输入保证仅由小写字母组成，且长度不超过 。

数据保证单个测试文件的所有字符串长度之和不超过 。

输出格式

对于每组数据，若两个字符串相似，输出"YES"，否则输出"NO"。

样例输入

2
aba
abba
ac
ca

样例输出

YES
NO

数据范围

样例 解释说明

样例1	第一组："aba"去重后得到"ab"，"abba"去重后也是"ab"，所以相似，输出"YES"。 第二组："ac"去重后是"ac"，"ca"去重后是"ca"，不相同，输出"NO"。

• 
• 字符串长度不超过
• 所有字符串长度之和不超过

题解

这道题考察的是字符串处理和去重操作。整体思路非常清晰：

1. 对每个输入的字符串进行去重处理，保留每个字母第一次出现的位置
2. 比较两个去重后的字符串是否相同

去重操作可以使用一个布尔数组（或集合、哈希表等）来记录每个字母是否已经出现过。由于题目限定只有小写字母，我们可以用一个长度为26的布尔数组就足够了。

具体做法：

1. 遍历原字符串的每个字符
2. 对于当前字符，检查它是否已经在结果串中出现过
3. 如果没有出现过，将其添加到结果串中，并标记为已出现
4. 对两个输入字符串分别进行上述处理，得到两个去重后的字符串
5. 比较这两个去重后的字符串是否相同

这个算法的时间复杂度是 O(n)，其中 n 是字符串的总长度。空间复杂度是 O(1)，因为我们只使用了固定大小的额外空间。

参考代码

• Python

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

def solve():
    # 读取测试用例数量
    t = int(input())
    
    for _ in range(t):
        # 读取两个字符串
        s1 = input()
        s2 = input()
        
        # 去重函数，保留每个字符第一次出现的位置
        def rmdup(s):
            seen = [False] * 26  # 记录字符是否出现过
            res = ""  # 结果字符串
            
            for c in s:
                idx = ord(c) - ord('a')  # 转换为索引
                if not seen[idx]:  # 如果字符未出现过
                    seen[idx] = True  # 标记为已出现
                    res += c  # 添加到结果串
            
            return res
        
        # 判断去重后是否相同
        if rmdup(s1) == rmdup(s2):
            print("YES")
        else:
            print("NO")

if __name__ == "__main__":
    solve()

• Cpp

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

// 去重函数，保留每个字符第一次出现的位置
string rmdup(const string& s) {
    bool seen[26] = {false};  // 记录字符是否出现过
    string res;  // 结果字符串
    
    for (char c : s) {
        int idx = c - 'a';  // 转换为索引
        if (!seen[idx]) {  // 如果字符未出现过
            seen[idx] = true;  // 标记为已出现
            res += c;  // 添加到结果串
        }
    }
    
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        string s1, s2;
        cin >> s1 >> s2;
        
        // 判断去重后是否相同
        if (rmdup(s1) == rmdup(s2)) {
            cout << "YES\n";
        } else {
            cout << "NO\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));
        int t = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < t; i++) {
            String s1 = br.readLine();
            String s2 = br.readLine();
            
            // 判断去重后是否相同
            if (rmdup(s1).equals(rmdup(s2))) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
    
    // 去重函数，保留每个字符第一次出现的位置
    private static String rmdup(String s) {
        boolean[] seen = new boolean[26];  // 记录字符是否出现过
        StringBuilder res = new StringBuilder();  // 结果字符串
        
        for (char c : s.toCharArray()) {
            int idx = c - 'a';  // 转换为索引
            if (!seen[idx]) {  // 如果字符未出现过
                seen[idx] = true;  // 标记为已出现
                res.append(c);  // 添加到结果串
            }
        }
        
        return res.toString();
    }
}

02. 人才资源优化配置

问题描述

小毛是一家企业的人力资源经理，面临一个任务分配问题。公司有 个任务，每个任务都有一个所需能力值和完成后的收益值。同时，公司有 名员工，每名员工都有自己的能力值。

员工只有在自身能力值不低于任务所需能力值的情况下，才能完成该任务。多名员工可以完成同一个任务，每完成一次该任务，公司就能获得相应的收益。每名员工最多只能被分配一个任务。

小毛想知道在这些条件下，公司能获得的最大总收益是多少。

输入格式

每个测试文件包含多组测试数据。

第一行输入一个整数 ，代表数据组数。

对于每组测试数据： 第一行输入两个整数 ，分别表示任务数量和员工数量。 第二行输入 个整数 ，其中 表示第 个任务所需的能力值。 第三行输入 个整数 ，其中 表示第 个任务的收益值。 第四行输入 个整数 ，其中 表示第 个员工的能力值。

数据保证同一个文件内 的总和不超过 ， 的总和不超过 。

输出格式

对于每组测试数据，输出一个整数，表示公司能获得的最大总收益。

样例输入

1
5 4
2 4 6 8 10
10 20 30 40 50
4 5 6 7

样例输出

100

数据范围

样例 解释说明

样例1	我们可以安排第1个员工(能力值4)和第2个员工(能力值5)完成第2个任务(能力要求4,收益20)，安排第3个员工(能力值6)和第4个员工(能力值7)完成第3个任务(能力要求6,收益30)。总收益为：220 + 230 = 100

• 
• 
• 
• 
• 同一个文件内 的总和不超过
• 同一个文件内 的总和不超过

题解

这道题乍一看像是一个匹配问题，但实际上可以用贪心的思路来解决。

关键洞察点是：每个员工都应该被分配到他能完成的、收益最高的任务上。

解题步骤如下：

1. 首先，我们将所有任务按照能力值要求从小到大排序
2. 对于能力值相同的任务，我们当然希望选择收益更高的任务
3. 但是一个任务可以被多个员工完成，所以我们需要维护一个前缀最大收益数组
4. 对于每个员工，我们用二分查找找到他能完成的所有任务中，收益最大的那个

具体来说，我们使用一个数组 pref，其中 pref[i] 表示在所有能力值要求 ≤ 第 i 个任务能力值要求的任务中，收益最大的是多少。这样，对于一个能力值为 b 的员工，我们只需要二分查找到最大的索引 idx，使得 tasks[idx].first ≤ b，然后将 pref[idx] 累加到答案中即可。

时间复杂度为 O((n + m) log n)，其中二分查找需要 O(log n) 的时间，我们需要对 m 个员工都进行一次二分查找。空间复杂度为 O(n)，用于存储排序后的任务和前缀最大收益数组。

参考代码

• Python

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

def solve():
    t = int(input())
    
    for _ in range(t):
        n, m = map(int, input().split())
        
        # 读取任务所需能力值
        a = list(map(int, input().split()))
        # 读取任务收益
        p = list(map(int, input().split()))
        # 读取员工能力值
        b = list(map(int, input().split()))
        
        # 将任务按能力要求排序
        tasks = [(a[i], p[i]) for i in range(n)]
        tasks.sort()  # 按能力要求从小到大排序
        
        # 计算前缀最大收益
        pref = [0] * n
        pref[0] = tasks[0][1]
        for i in range(1, n):
            pref[i] = max(pref[i-1], tasks[i][1])
        
        # 计算总收益
        ans = 0
        for ab in b:
            # 二分查找员工能完成的最高能力要求的任务
            l, r = 0, n-1
            while l <= r:
                mid = (l + r) // 2
                if tasks[mid][0] <= ab:
                    l = mid + 1
                else:
                    r = mid - 1
            
            # 如果找到了合适的任务，累加收益
            if r >= 0:
                ans += pref[r]
        
        print(ans)

if __name__ == "__main__":
    solve()

• 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, m;
        cin >> n >> m;
        
        // 读取任务能力要求和收益
        vector<pair<int, int>> tasks(n);
        for (int i = 0; i < n; i++) 
            cin >> tasks[i].first;
        for (int i = 0; i < n; i++) 
            cin >> tasks[i].second;
        
        // 读取员工能力值
        vector<int> worker(m);
        for (int i = 0; i < m; i++) 
            cin >> worker[i];
        
        // 按能力要求排序
        sort(tasks.begin(), tasks.end());
        
        // 计算前缀最大收益
        vector<ll> pref(n);
        pref[0] = tasks[0].second;
        for (int i = 1; i < n; i++)
            pref[i] = max(pref[i-1], (ll)tasks[i].second);
        
        // 计算总收益
        ll ans = 0;
        for (int ab : worker) {
            // 二分查找
            int idx = upper_bound(tasks.begin(), tasks.end(), 
                     make_pair(ab, INT_MAX)) - tasks.begin() - 1;
            
            if (idx >= 0) 
                ans += pref[idx];
        }
        
        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));
        int t = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            String[] line = br.readLine().split(" ");
            int n = Integer.parseInt(line[0]);
            int m = Integer.parseInt(line[1]);
            
            // 读取任务能力要求
            int[] a = new int[n];
            line = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(line[i]);
            }
            
            // 读取任务收益
            int[] p = new int[n];
            line = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                p[i] = Integer.parseInt(line[i]);
            }
            
            // 读取员工能力值
            int[] b = new int[m];
            line = br.readLine().split(" ");
            for (int i = 0; i < m; i++) {
                b[i] = Integer.parseInt(line[i]);
            }
            
            // 创建任务数组并排序
            Task[] tasks = new Task[n];
            for