✅ 春招备战指南 ✅

💡 学习建议：

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

🧸 题面描述等均已深度改编，所有题面背景均为原创，做法和题目本质基本不变。

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

互联网必备刷题宝典🔗

2025.03.08-米哈游

题目一：字符变换大师

1️⃣：字符分类处理 2️⃣：ASCII码操作与模运算 3️⃣：字符串遍历与构建

整体难度：简单

该题目要求对字符串中的每个字符进行特定规则的变换：大写字母变为下一个字母，小写字母变为上一个字母，数字加1，其他字符变为下划线。通过遍历字符串并根据字符类型应用相应的变换规则，可以高效地解决问题。时间复杂度O(n)，其中n是字符串的长度。

题目二：双重翻转的奥秘

1️⃣：寻找回文子串 2️⃣：检查不重叠的回文对 3️⃣：验证翻转操作的有效性

整体难度：中等

该题目要求找到两个不重叠的区间，对它们分别执行翻转操作后，字符串保持不变。关键是寻找长度为2或3的回文子串，因为翻转回文子串后，字符串本身不会改变。通过枚举所有可能的回文子串对，可以找到满足条件的解。时间复杂度O(n²)，其中n是字符串的长度。

题目三：字符串团队管理

1️⃣：计算字符串差异值 2️⃣：构建字符串关系图 3️⃣：寻找最大连通分量

整体难度：中等偏难

该题目涉及字符串之间的差异值计算和图论中的连通分量分析。通过计算任意两个字符串之间的差异值，构建一个无向图，然后使用深度优先搜索(DFS)或广度优先搜索(BFS)找到最大的连通分量，从而确定最少需要删除的字符串数量。时间复杂度O(n²m)，其中n是字符串数量，m是字符串长度。

01. 字符变换大师

问题描述

小兰是一位密码学爱好者，她设计了一种特殊的字符变换规则，用于加密和解密信息。她有一个长度为 的字符串，需要对其中的每个字符按照以下规则进行变换：

• 如果是大写字母，则将其替换为字母表中的下一个字母（Z 替换为 A）
• 如果是小写字母，则将其替换为字母表中的上一个字母（a 替换为 z）
• 如果是数字，则将其替换为该数字加 1 的结果（9 替换为 0）
• 如果是其他字符（如空格、标点符号等），则将其替换为下划线"_"

小兰想请你帮她实现这个字符变换算法，将给定的字符串按照上述规则进行变换，并输出变换后的结果。

输入格式

第一行输入一个整数 ，表示字符串的长度。

第二行输入一个长度为 的字符串 ，由数字、大小写字母、空格及 这七个常见半角符号构成。保证字符串的首尾不为空格。

输出格式

在一行上输出一个字符串，表示按照规则变换后的字符串。

样例输入

12
Ab91!?.+-*/

样例输出

Ba02________

数据范围

• 
• 字符串 由数字、大小写字母、空格及 这七个常见半角符号构成
• 保证字符串的首尾不为空格

样例 解释说明

样例1	原字符串"Ab91!?.+-*/"中：A变为B，b变为a，9变为0，1变为2，其余字符全部变为下划线

题解

这道题目要求我们对一个字符串中的每个字符按照特定规则进行变换。变换规则很直观：大写字母变为下一个字母，小写字母变为上一个字母，数字加1，其他字符变为下划线。

解决这个问题的关键是正确识别字符的类型，并应用相应的变换规则。我们可以使用ASCII码的特性来判断字符类型：

• 大写字母的ASCII码范围是65-90（A-Z）
• 小写字母的ASCII码范围是97-122（a-z）
• 数字的ASCII码范围是48-57（0-9）

对于每种类型的字符，我们需要处理循环的情况：

• 对于大写字母Z，下一个字母应该是A
• 对于小写字母a，上一个字母应该是z
• 对于数字9，加1后应该是0

这些循环可以通过模运算（%）来优雅地处理。例如，对于大写字母，我们可以使用(c - 'A' + 1) % 26 + 'A'来计算下一个字母。

算法的时间复杂度是O(n)，其中n是字符串的长度，因为我们需要遍历字符串中的每个字符并进行变换。空间复杂度也是O(n)，用于存储变换后的字符串。

这个问题是一个典型的字符处理问题，通过简单的条件判断和字符变换，我们可以高效地解决它。

参考代码

• Python

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

def transform_string(s):
    """
    根据规则变换字符串
    """
    result = []
    for char in s:
        # 处理大写字母
        if 'A' <= char <= 'Z':
            # 将大写字母变为下一个字母
            next_char = chr((ord(char) - ord('A') + 1) % 26 + ord('A'))
            result.append(next_char)
        # 处理小写字母
        elif 'a' <= char <= 'z':
            # 将小写字母变为上一个字母
            prev_char = chr((ord(char) - ord('a') - 1) % 26 + ord('a'))
            result.append(prev_char)
        # 处理数字
        elif '0' <= char <= '9':
            # 将数字加1
            next_digit = chr((ord(char) - ord('0') + 1) % 10 + ord('0'))
            result.append(next_digit)
        # 处理其他字符
        else:
            # 将其他字符变为下划线
            result.append('_')
    
    return ''.join(result)

# 主函数
n = int(input())
s = input()
print(transform_string(s))

• Cpp

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

string transform_string(const string& s) {
    // 存储变换后的字符串
    string result;
    result.reserve(s.length());
    
    for (char c : s) {
        // 处理大写字母
        if (c >= 'A' && c <= 'Z') {
            // 将大写字母变为下一个字母
            char next_char = (c - 'A' + 1) % 26 + 'A';
            result.push_back(next_char);
        }
        // 处理小写字母
        else if (c >= 'a' && c <= 'z') {
            // 将小写字母变为上一个字母
            char prev_char = (c - 'a' + 25) % 26 + 'a'; // +25 等同于 -1 再加26
            result.push_back(prev_char);
        }
        // 处理数字
        else if (c >= '0' && c <= '9') {
            // 将数字加1
            char next_digit = (c - '0' + 1) % 10 + '0';
            result.push_back(next_digit);
        }
        // 处理其他字符
        else {
            // 将其他字符变为下划线
            result.push_back('_');
        }
    }
    
    return result;
}

int main() {
    int n;
    string s;
    
    // 读取输入
    cin >> n;
    cin.ignore(); // 忽略换行符
    getline(cin, s);
    
    // 输出变换后的字符串
    cout << transform_string(s) << endl;
    
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static String transformString(String s) {
        // 使用StringBuilder高效构建字符串
        StringBuilder result = new StringBuilder(s.length());
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            // 处理大写字母
            if (c >= 'A' && c <= 'Z') {
                // 将大写字母变为下一个字母
                char nextChar = (char)((c - 'A' + 1) % 26 + 'A');
                result.append(nextChar);
            }
            // 处理小写字母
            else if (c >= 'a' && c <= 'z') {
                // 将小写字母变为上一个字母
                char prevChar = (char)((c - 'a' + 25) % 26 + 'a'); // +25 等同于 -1 再加26
                result.append(prevChar);
            }
            // 处理数字
            else if (c >= '0' && c <= '9') {
                // 将数字加1
                char nextDigit = (char)((c - '0' + 1) % 10 + '0');
                result.append(nextDigit);
            }
            // 处理其他字符
            else {
                // 将其他字符变为下划线
                result.append('_');
            }
        }
        
        return result.toString();
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int n = scanner.nextInt();
        scanner.nextLine(); // 消耗换行符
        String s = scanner.nextLine();
        
        // 输出变换后的字符串
        System.out.println(transformString(s));
        
        scanner.close();
    }
}

02. 双重翻转的奥秘

问题描述

小基是一位字符串研究专家，她正在研究一种特殊的字符串翻转操作。对于一个字符串，翻转操作定义为将一个区间 内的字符顺序完全颠倒，即将原来的 变为 。

小基想知道，对于一个给定的字符串，是否存在两个不重叠的区间 和 （满足 ），使得先对区间 进行翻转操作，再对区间 进行翻转操作后，得到的字符串与原始字符串完全相同。

如果存在这样的两个区间，请输出"YES"并给出一组满足条件的 、、、 值；如果不存在，则输出"NO"。

输入格式

第一行一个整数 ，表示字符串长度。

第二行一个长度为 的字符串 ，保证输入仅由小写字母组成。

输出格式

若可以满足题意，第一行输出"YES"，第二行输出 个整数，代表 ，以空格隔开，若有多组解，输出任意一个。

若不能，输出"NO"。

样例输入

4
abcd

样例输出

NO

样例输入

13
abbagggfkfggc

样例输出

YES
1 4 6 12

数据范围

• 
• 字符串 仅由小写字母组成

样例 解释说明

样例1	对于字符串"abcd"，不存在满足条件的两个区间
样例2	对于字符串"abbagggfkfggc"，可以先翻转区间[1,4]得到"abbaggfkfggc"，再翻转区间[6,12]得到"abbagggfkfggc"，与原字符串相同

题解

这道题目要求我们找到两个不重叠的区间，对它们分别进行翻转操作后，字符串保持不变。这个问题乍看起来很复杂，但实际上有一个关键的观察：如果一个区间是回文串，那么对它进行翻转操作后，这个区间的字符不会发生变化。

基于这个观察，我们可以推导出一个重要结论：要使两次翻转后字符串保持不变，必须满足以下条件之一：

1. 两个区间都是回文串
2. 两个区间互为镜像（即翻转第一个区间后得到的子串与第二个区间相同）

对于条件1，如果两个区间都是回文串，那么无论怎么翻转，这两个区间的字符都不会改变，整个字符串自然保持不变。

对于条件2，这种情况比较复杂，需要考虑两个区间的相对位置和长度。

为了简化问题，我们可以专注于寻找回文子串。特别是，我们可以寻找长度为2或3的回文子串，因为这些是最简单的回文形式：

• 长度为2的回文：两个相同的字符，如"aa"
• 长度为3的回文：首尾字符相同的三字符串，如"aba"

算法步骤如下：

1. 遍历字符串，找出所有长度为2或3的回文子串
2. 检查是否存在两个不重叠的回文子串
3. 如果存在，输出"YES"和对应的区间；否则输出"NO"

这个算法的时间复杂度是O(n²)，其中n是字符串的长度。在最坏情况下，我们需要检查O(n²)对回文子串。但实际上，回文子串的数量通常远小于n²，所以算法在实践中效率较高。

参考代码

• Python

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

def find_palindrome_pairs(s, n):
    """
    寻找字符串中所有长度为2或3的回文子串
    """
    palindromes = []
    
    # 寻找长度为2的回文
    for i in range(n-1):
        if s[i] == s[i+1]:
            palindromes.append((i+1, i+2))  # 转换为1-based索引
    
    # 寻找长度为3的回文
    for i in range(n-2):
        if s[i] == s[i+2]:
            palindromes.append((i+1, i+3))  # 转换为1-based索引
    
    return palindromes

def check_non_overlapping_pairs(palindromes):
    """
    检查是否存在两个不重叠的回文子串
    """
    for i in range(len(palindromes)):
        a, b = palindromes[i]
        for j in range(i+1, len(palindromes)):
            c, d = palindromes[j]
            if b < c:  # 确保区间不重叠
                return a, b, c, d
    
    return None

# 主函数
n = int(input())
s = input()

# 寻找所有长度为2或3的回文子串
palindromes = find_palindrome_pairs(s, n)

# 检查是否存在两个不重叠的回文子串
result = check_non_overlapping_pairs(palindromes)

if result:
    print("YES")
    print(*result)
else:
    print("NO")

• Cpp

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

vector<pair<int, int>> find_palindrome_pairs(const string& s, int n) {
    // 存储所有长度为2或3的回文子串
    vector<pair<int, int>> palindromes;
    
    // 寻找长度为2的回文
    for (int i = 0; i < n-1; ++i) {
        if (s[i] == s[i+1]) {
            // 转换为1-based索引