✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：密码转换器

1️⃣：删除原始字符串中所有奇数位置的字符

2️⃣：将剩余字符串反转

3️⃣：将所有小写字母转换为大写字母

难度：简单

这道题目考察基本的字符串处理能力，包括字符筛选、反转和大小写转换。通过三个简单步骤即可完成转换，实现复杂度为O(n)的解法。

题目二：乐园游览线规划

1️⃣：维护一个有序集合存储所有分割点

2️⃣：使用多重集合存储各段线路长度

3️⃣：动态更新线路段并查询最大长度

难度：中等

这道题目要求处理线段的动态分割和查询，通过合适的数据结构来维护分割点和线段长度，可以高效地处理各种操作。时间复杂度为O(Q log Q)。

题目三：彩色灯带设计

1️⃣：分析距离限制对颜色选择的影响

2️⃣：计算可能的颜色块数量

3️⃣：使用数学公式和快速幂计算总方案数

难度：中等偏难

这道题目需要理解特殊的距离限制条件，并设计数学模型来计算不同的方案数。通过分析颜色块的性质，结合快速幂算法，可以高效地计算出结果，时间复杂度为O(T log n)。

01. 密码转换器

问题描述

小基正在开发一种全新的密码转换系统，用于企业内部文件的安全传输。该系统有一个特殊的转换规则：首先删除原始字符串中所有处于奇数位置的字符（位置从1开始计数），然后将剩余字符反转，最后将所有小写字母转换为大写字母。小基需要你帮忙实现这个转换器的核心功能。

输入格式

第一行输入一个由大小写字母混合构成的字符串 ，字符串长度满足 。

输出格式

输出经过转换规则处理后得到的最终字符串。

样例输入

WhilE

样例输出

LH

数据范围

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

题解

这道题目的要求很直观：删除奇数位置的字符、反转字符串、将小写字母转为大写。

解题思路可以分为三个明确的步骤：

1. 删除奇数位置的字符：遍历原始字符串，只保留偶数位置的字符（从1开始计数，即索引为1,3,5...的位置）。在实现时，如果使用0开始的索引，我们需要保留索引为1,3,5...的字符。

2. 反转字符串：将上一步得到的字符串进行反转。大多数编程语言都提供了字符串或数组的反转方法。

3. 小写转大写：遍历反转后的字符串，将所有小写字母转换为对应的大写字母。

时间复杂度分析：

• 遍历原字符串一次，时间复杂度为 O(n)
• 反转字符串的时间复杂度为 O(n)
• 大小写转换的时间复杂度为 O(n)

总的时间复杂度为 O(n)，其中n是字符串的长度。空间复杂度也是 O(n)，主要用于存储处理过程中的中间字符串。

这个问题不需要特别复杂的算法或数据结构，关键是按照题目要求正确实现每一步转换。

参考代码

• Python

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

# 读取输入字符串
s = input()
result = ""

# 步骤1：保留偶数位置字符（删除奇数位置字符）
for i in range(1, len(s), 2):
    result += s[i]

# 步骤2：反转字符串
result = result[::-1]

# 步骤3：转换为大写
result = result.upper()

# 输出结果
print(result)

• Cpp

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

int main() {
    // 优化输入输出速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s, t;
    cin >> s;
    int n = s.size();
    
    // 步骤1：提取偶数位置的字符（奇数索引）
    for (int i = 1; i < n; i += 2) {
        t.push_back(s[i]);
    }
    
    // 步骤2：反转字符串
    reverse(t.begin(), t.end());
    
    // 步骤3：转换为大写
    for (char &c : t) {
        if (c >= 'a' && c <= 'z') {
            c -= 32; // 'a' - 'A' = 32
        }
    }
    
    cout << t << endl;
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuilder res = new StringBuilder();
        
        // 步骤1：提取偶数位置的字符
        for (int i = 1; i < s.length(); i += 2) {
            res.append(s.charAt(i));
        }
        
        // 步骤2：反转字符串
        res.reverse();
        
        // 步骤3：转换为大写
        String result = res.toString().toUpperCase();
        
        System.out.println(result);
        sc.close();
    }
}

02. 乐园游览线规划

问题描述

小柯是一家主题乐园的规划师，她设计了一条长度为 的游览线路，并在线路上均匀地设置了 个游览点（包括起点和终点），这些游览点的编号从 到 ，相邻游览点之间的距离相等。

为了方便游客体验不同的线路组合，小柯计划设置若干个临时休息站，游客可以在休息站处离开主线路，去体验其他景点后再返回。她想要测试不同的休息站布局，并进行以下操作：

操作一：在编号为 的游览点（）设置一个休息站。 操作二：如果在当前所有设置了休息站的游览点处将线路分割，询问是否存在长度大于等于 的连续线路段。

小柯计划进行 次操作，每次操作二都是独立的（即假设分割线路，但实际并不执行分割）。请你帮助小柯回答每次询问。

输入格式

第一行输入两个整数 和 （；），分别表示游览线路的游览点数量和操作次数。

接下来 行，每行先输入一个整数 （）表示操作类型，随后：

• 当 时，在同一行输入一个整数 （），表示在游览点 处设置休息站。
• 当 时，在同一行输入一个整数 （），询问如果将当前所有休息站处的线路分割，是否存在长度大于等于 的连续线路段。

输出格式

对于每个操作二，如果存在长度大于等于 的连续线路段，输出 ；否则，输出 。

样例输入

8 7
2 7
1 4
2 4
2 5
1 6
2 3
2 4

样例输出

YES
YES
NO
YES
NO

数据范围

• 
• 
• （对于操作一）
• （对于操作二）

题解

这道题目本质上是在处理线段的动态分割和查询问题。我们需要维护一个不断变化的线段集合，并快速回答有关最长线段长度的查询。

核心思路如下：

1. 使用一个有序集合（如set）来存储所有的分割点（包括端点1和n）。
2. 使用一个多重集合（如multiset）来存储每个线段的长度。
3. 当添加新的分割点时，我们需要：
   • 找到新分割点所在的线段
   • 从多重集合中删除这个线段的长度
   • 将线段分成两部分，并将新的两个长度添加到多重集合中
   • 将新分割点添加到有序集合中
4. 当查询最长线段长度时，只需查看多重集合中的最大值并与查询值k比较。

在实现上，我们需要注意几个关键点：

• 初始时，整条线路是完整的，长度为n-1，分割点只有两个端点1和n。
• 对于每个操作一，我们需要找到新分割点在有序集合中的位置，确定它将分割哪个现有线段。
• 对于每个操作二，我们只需要查询当前多重集合中的最大值即可。

时间复杂度分析：

• 在有序集合中查找和插入分割点的时间复杂度为O(log Q)。
• 在多重集合中插入和删除线段长度的时间复杂度为O(log Q)。
• 总时间复杂度为O(Q log Q)，其中Q是操作次数。

这种方法充分利用了数据结构来高效地处理动态变化的线段集合，避免了每次查询时的重新计算，使得算法能够在规定的时间内处理大量操作。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()
from sortedcontainers import SortedSet, SortedList

n, q = map(int, input().split())

# 存储分割点
cuts = SortedSet([1, n])
# 存储各段长度
lens = SortedList([n - 1])

for _ in range(q):
    op, x = map(int, input().split())
    
    if op == 1:
        # 操作一：设置休息站
        if x <= 1 or x >= n or x in cuts:
            continue
            
        # 找到新分割点的位置
        idx = cuts.bisect_left(x)
        right = cuts[idx]
        left = cuts[idx - 1]
        
        # 更新段长度
        old_len = right - left
        lens.remove(old_len)
        lens.add(x - left)
        lens.add(right - x)
        
        # 添加新分割点
        cuts.add(x)
        
    else:
        # 操作二：查询是否存在长度≥k的线路段
        k = x
        max_len = lens[-1] if lens else 0
        print("YES" if max_len >= k else "NO")

• Cpp

#include <iostream>
#include <set>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_wi