✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

饿了么

题目一：魔法对线匹配

1️⃣：统计数组中所有数对，检查是否满足特定的三角形条件

2️⃣：利用异或运算的性质，高效计算满足条件的数对数量

难度：中等

这道题目要求统计能形成特定条件三角形的数对。通过理解异或运算和三角形不等式，我们可以高效地解决问题，避免暴力枚举所有可能的数对。

题目二：魔法卷轴优化

1️⃣：按照字典序贪心地修改字符串

2️⃣：根据剩余操作次数决定最优转换策略

3️⃣：从左到右处理每个字符，确保获得字典序最小结果

难度：中等

这道题目需要通过贪心策略，在有限的操作次数内将字符串转换为字典序最小的形式。通过分析每种操作的成本和效果，我们可以制定出最优的转换策略。

题目三：宝藏森林优化

1️⃣：构建树结构并确定父子节点关系

2️⃣：使用动态规划求解每个子树的最大收益

3️⃣：比较保留节点或执行操作的收益，选择最优方案

难度：中等偏难

这道题目需要理解树结构上的动态规划，并在每个节点处做出最优决策。通过比较不同操作策略的净收益，我们可以找到使根节点所在连通块收益最大的方案。

01. 魔法对线匹配

问题描述

在魔法世界的对决竞技场中，魔法师可以组合两种元素进行对战。A小姐是一位元素魔法研究员，她发现当两种元素 和 产生对抗时，会形成第三种融合元素，其强度为 （两元素的异或值）。

A小姐将元素组合 {} 称为"强力对线"，当且仅当元素 、元素 和融合元素 这三种力量能形成一个稳定的魔法三角阵。魔法三角阵要求任意两种元素的强度之和必须大于第三种元素的强度。

现在，A小姐收集了一系列元素样本 ，她想知道从中能够形成多少种不同的"强力对线"组合。具体来说，她需要计算有多少对下标 满足 ，且对应的元素组合 {} 是一对"强力对线"。

输入格式

第一行包含一个正整数 ，表示元素样本的数量。

第二行包含 个正整数 ，表示每个元素样本的强度。

输出格式

输出一个整数，表示满足条件的"强力对线"组合数量。

样例输入

4
2 3 4 5

样例输出

1

数据范围

• 
• 

样例 解释说明

样例1	在这个样例中，只有一对下标 对应的元素组合 {} 是强力对线。对于元素 和 ，它们的融合元素为 。我们可以验证 ，，，满足魔法三角阵的条件。

题解

这道题目主要考察位运算和基本数学中的三角不等式性质。

首先，我们需要理解"强力对线"的定义：两个元素 和 及其异或值 能够满足三角形的三边条件，即任意两边之和大于第三边。

对于三角形三边条件，我们需要验证以下三个不等式：

1. 
2. 
3. 

分析这个问题，我们可以采用两种方法：

1. 枚举法：遍历所有可能的元素对 ，其中 ，然后检查它们是否满足三角形条件。
2. 计数优化：注意到元素的范围较小（不超过1000），我们可以先统计每个元素出现的次数，然后枚举所有可能的元素值对，而不是枚举索引对。

第二种方法效率更高，特别是当有大量重复元素时。以下是算法步骤：

1. 统计数组中每个元素出现的次数。
2. 双重循环枚举所有可能的元素对 ，其中 。
3. 计算异或值 。
4. 检查是否满足三角形条件：，，。
5. 如果满足条件，根据 和 是否相等，计算这样的对数：
   • 如果 ，那么贡献是 。
   • 如果 ，那么贡献是 （从相同元素中选择两个的组合数）。

时间复杂度分析：

• 统计次数：O(n)
• 枚举元素对：O(1000²) = O(10⁶)
• 总体时间复杂度：O(n + 10⁶)，对于给定的约束条件（n ≤ 10⁵）是可以接受的。

这个算法避免了直接枚举所有可能的索引对（最坏情况下为O(n²)），而是利用了元素值的范围有限这一特性，大大提高了效率。

参考代码

• Python

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

# 读取输入
n = int(input())
a = list(map(int, input().split()))

# 统计每个元素出现的次数
cnt = [0] * 1001
for x in a:
    cnt[x] += 1

# 计算满足条件的对数
ans = 0
# 枚举所有可能的元素对
for u in range(1, 1001):
    if cnt[u] == 0:
        continue
    for v in range(u, 1001):
        if cnt[v] == 0:
            continue
        # 计算异或值
        w = u ^ v
        # 检查三角形条件
        if u + v > w and u + w > v and v + w > u:
            if u < v:
                # 不同的元素
                ans += cnt[u] * cnt[v]
            else:  # u == v
                # 相同的元素，计算组合数
                ans += cnt[u] * (cnt[u] - 1) // 2

print(ans)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    int n;
    cin >> n;
    
    // 统计每个元素出现的次数
    vector<int> cnt(1001, 0);
    for (int i = 0, x; i < n; i++) {
        cin >> x;
        cnt[x]++;
    }
    
    // 计算满足条件的对数
    long long res = 0;
    // 枚举所有可能的元素对
    for (int u = 1; u <= 1000; u++) {
        if (cnt[u] == 0) continue;
        for (int v = u; v <= 1000; v++) {
            if (cnt[v] == 0) continue;
            
            // 计算异或值
            int w = u ^ v;
            
            // 检查三角形条件
            if (u + v > w && u + w > v && v + w > u) {
                if (u < v) {
                    // 不同的元素
                    res += (long long)cnt[u] * cnt[v];
                } else {  // u == v
                    // 相同的元素，计算组合数
                    res += (long long)cnt[u] * (cnt[u] - 1) / 2;
                }
            }
        }
    }
    
    cout << res << "\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 n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        
        // 统计每个元素出现的次数
        int[] cnt = new int[1001];
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(line[i]);
            cnt[x]++;
        }
        
        // 计算满足条件的对数
        long ans = 0;
        // 枚举所有可能的元素对
        for (int u = 1; u <= 1000; u++) {
            if (cnt[u] == 0) continue;
            for (int v = u; v <= 1000; v++) {
                if (cnt[v] == 0) continue;
                
                // 计算异或值
                int w = u ^ v;
                
                // 检查三角形条件
                if (u + v > w && u + w > v && v + w > u) {
                    if (u < v) {
                        // 不同的元素
                        ans += (long)cnt[u] * cnt[v];
                    } else {  // u == v
                        // 相同的元素，计算组合数
                        ans += (long)cnt[u] * (cnt[u] - 1) / 2;
                    }
                }
            }
        }
        
        System.out.println(ans);
    }
}

02. 魔法卷轴优化

问题描述

在遥远的魔法王国里，小基是一位精通魔法文字的法师。她正研究一种古老的魔法卷轴，这种卷轴上记载的咒语由大小写字母组成，其魔力强度与字符的字典序有关，字典序越小，魔力越强。

小基可以对卷轴进行最多 次魔法操作，每次可以选择以下任意一种：

• 将一个大写字母变为对应的小写字母（例如将 变为 ）
• 将一个小写字母变为对应的大写字母（例如将 变为 ）
• 将一个大写字母变为任意一个大写字母
• 将一个小写字母变为任意一个小写字母

小基想要在有限的操作次数内，使卷轴上的咒语的魔力最强（即字典序最小）。请你帮她找到操作后能够得到的字典序最小的字符串。

在这个魔法王国中，字符的字典序遵循一般规则：从字符串的第一个字符开始逐个比较，直至发现第一个不同的位置，比较这个位置字符的ASCII码。其中 ，ASCII码较小的字符串字典序也较小；如果比较到其中一个字符串的结尾时依旧全部相同，则较短的字符串字典序更小。

输入格式

第一行包含两个正整数 和 ，分别表示字符串长度和最多能进行的操作次数。

第二行包含一个长度为 的字符串 ，仅由大小写英文字母组成。

输出格式

输出一个字符串，表示经过不超过 次操作后能得到的字典序最小的字符串。

样例输入

3 2
Aab

样例输出

AAB

数据范围

• 
• 字符串 仅由大小写英文字母组成

样例 解释说明

样例1	初始字符串为 "Aab"。进行两次操作：第一次将 'a' 变为 'A'，第二次将 'b' 变为 'B'，得到字典序最小的字符串 "AAB"。
样例2	初始字符串为 "Y"。使用一次操作将 'Y' 变为 'A'，得到字典序最小的字符串 "A"。

题解

这道题目要求在有限的操作次数内，将一个字符串变成字典序最小的字符串。由于字典序的比较是从左到右进行的，我们的策略是贪心地从左到右处理每个字符，尽可能地使每个位置的字符尽量小。

我们知道，在ASCII码中，大写字母的值比小写字母小，而大写字母中，'A'的ASCII码最小。因此，我们的目标是尽可能多地将字符串中的字符变为'A'，特别是前面的字符。

具体的贪心策略如下：

1. 从左到右遍历字符串的每个字符。
2. 如果当前字符是大写字母：
   • 如果它不是'A'且我们还有操作次数，则将其变为'A'，消耗1次操作。
   • 否则保持不变。
3. 如果当前字符是小写字母：
   • 如果是'a'，并且我们有操作次数，则将其变为'A'，消耗1次操作。
   • 如果不是'a'，并且我们有至少2次操作次数，则将其变为'A'，消耗2次操作（先将其变为对应的大写字母，再将大写字母变为'A'）。
   • 如果不是'a'，但我们只有1次操作次数，则将其变为对应的大写字母，消耗1次操作。
   • 如果没有操作次数剩余，则保持不变。

这个贪心策略保证了在有限的操作次数内，我们能得到字典序最小的字符串。这是因为：

1. 将一个字符变为'A'总是比保持其他任何字符更优（因为'A'的ASCII码最小）。
2. 在无法变为'A'的情况下，将小写字母变为对应的大写字母也是更优的选择。

时间复杂度：O(n)，其中n是字符串的长度。我们只需要遍历字符串一次，对每个字符进行常数时间的操作。

空间复杂度：O(n)，需要保存修改后的字符串。

参考代码

• Python

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

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

# 从左到右贪心处理每个字符
result = list(s)
for i in range(n):
    c = s[i]
    # 如果是大写字母
    if 'A' <= c <= 'Z':
        # 如果不是'A'且有操作次数，变为'A'
        if c != 'A' and k >= 1:
            result[i] = 'A'
            k -= 1
    # 如果是小写字母
    else:  # 'a' <= c <= 'z'
        # 如果是'a'
        if c == 'a':
            # 有操作次数，变为'A'
            if k >= 1:
                result[i] = 'A'
                k -= 1
        else:  # 不是'a'
            # 有至少2次操作，变为'A'
            if k >= 2:
                result[i] = 'A'
                k -= 2
            # 只有1次操作，变为对应大写
            elif k == 1:
                result[i] = chr(ord(c) - ord('a') + ord('A'))
                k -= 1

print(''.join(result))

• Cpp

#include <iostream>
#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;
    
    // 从左到右贪心处理每个字符
    for (int i = 0; i < n && k > 0; i++) {
        char c = s[i];
        
        // 如果是大写字母
        if (c >= 'A' && c <= 'Z')