✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

题目一：光影文字游戏

1️⃣：定义具有垂直对称轴的字符集合作为辅助判断

2️⃣：枚举所有子串并判断是否满足回文和对称性质

3️⃣：累计满足条件的子串数量

难度：中等

这道题目需要理解垂直对称字符的概念，结合回文串性质判断。通过双重循环枚举所有子串，并使用高效的判断方法，可以实现O(n³)的时间复杂度，在给定数据范围内高效解决问题。

题目二：无序区间中位数探索

1️⃣：理解"稳定数组"性质，即数组中位位置的元素刚好是中位数

2️⃣：枚举所有奇数长度区间并检验是否满足条件

3️⃣：通过计算区间内小于和大于中位数的元素个数来判断

难度：中等

这道题目通过巧妙的数学推导，发现满足条件的区间必须有相等数量的小于和大于中位数的元素。实现上需要注意时间复杂度优化，可以通过前缀和或滑动窗口降低到O(n²)，有效处理题目给定的数据范围。

题目三：字符串交织优化

1️⃣：构建前缀差数组，遇0加1，遇1减1

2️⃣：利用排序技巧计算所有子串的"不平衡度"之和

3️⃣：结合数学公式高效求解子串和谐度总和

难度：中等

这道题目通过巧妙的数学分析，将子串的和谐度转化为前缀差的绝对值，并用排序技巧避免枚举所有子串。算法的时间复杂度为O(n log n)，相比传统O(n²)的枚举方法更加高效，能够处理大规模测试数据。

题目四：青蛙跳跃轨迹预测

1️⃣：使用位集合(bitset)跟踪青蛙可能的位置

2️⃣：针对不同指令类型更新位置集合

3️⃣：特别处理边界情况，确保不越界

难度：中等偏难

这道题目需要理解青蛙随机跳跃的所有可能性。通过使用位运算或集合操作高效处理大范围的坐标，实现O(n*m)的时间复杂度。特别是位集合(bitset)的运用使得算法在处理大规模数据时更加高效。

01. 光影文字游戏

问题描述

小基正在参加一个特殊的文字游戏。游戏中她有一个长度为 的字符串 ，她需要找出所有长度大于 的"光影字符串"。

"光影字符串"是指同时满足以下两个条件的子串：

1. 该子串是回文串（从左往右读和从右往左读完全相同）
2. 该子串中的每个字符都具有垂直对称轴

以下大写字母具有垂直对称轴：''、''、''、''、''、''、''、''、''、''、''。

小基想知道字符串 中共有多少个长度大于 的"光影字符串"。

输入格式

输入一个长度为 的字符串 ，字符串中仅包含大写字母。

输出格式

输出一个整数，表示字符串 中长度大于 的"光影字符串"的数量。

样例输入

AHHAMTT

样例输出

3

数据范围

• 

样例 解释说明

AHHAMTT	共有3个长度大于1的"光影字符串"： "HH"、"AHHA"、"TT"

题解

这道题目要求我们找出所有满足两个条件的子串：是回文串且每个字符都有垂直对称轴。解决这个问题的思路其实很直观。

首先，我们需要知道哪些字符具有垂直对称轴。题目已经给出，这些字符是：A、H、I、M、O、T、U、V、W、X、Y。我们可以用一个哈希集合来存储这些字符，便于快速查找。

解题步骤如下：

1. 定义一个集合，存储所有具有垂直对称轴的字符。
2. 枚举字符串的所有子串（可以通过两个循环实现，外循环选择子串的起始位置，内循环选择子串的结束位置）。
3. 对于每个长度大于1的子串，检查它是否是回文串，以及其中的每个字符是否都有垂直对称轴。
4. 如果满足条件，计数器加1。

时间复杂度分析：

• 枚举所有子串需要 O(n²) 的时间。
• 对于每个子串，需要 O(len) 的时间检查是否是回文串且每个字符是否符合要求，这里 len 是子串的长度，最大为 n。
• 因此，总的时间复杂度是 O(n³)。

考虑到题目中 n 的范围是 1 到 100，这个时间复杂度是完全可以接受的。

我们还可以进一步优化：在检查子串是否为回文串时，如果发现它不是回文串，就可以立即停止检查，不需要再判断每个字符是否有垂直对称轴。

另外，对于一个长度为 k 的子串，如果它是回文串，那么只需要检查前 k/2 个字符是否等于后 k/2 个字符（从末尾开始倒数）。这样可以减少一些比较操作。

在给定的约束条件下，这个解法已经足够高效，能够在短时间内解决问题。

参考代码

• Python

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

def solve():
    # 读取输入
    s = input()
    n = len(s)
    
    # 定义具有垂直对称轴的字符集合
    sym = {'A', 'H', 'I', 'M', 'O', 'T', 'U', 'V', 'W', 'X', 'Y'}
    
    # 计数器
    cnt = 0
    
    # 枚举所有长度大于1的子串
    for i in range(n):
        for j in range(i+1, n):
            # 获取子串
            sub = s[i:j+1]
            
            # 检查是否是回文串
            if sub != sub[::-1]:
                continue
            
            # 检查每个字符是否有垂直对称轴
            valid = True
            for ch in sub:
                if ch not in sym:
                    valid = False
                    break
            
            # 如果满足条件，计数器加1
            if valid:
                cnt += 1
    
    # 输出结果
    print(cnt)

if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int solve() {
    // 读取输入
    string s;
    cin >> s;
    int n = s.size();
    
    // 定义具有垂直对称轴的字符集合
    unordered_set<char> sym = {'A', 'H', 'I', 'M', 'O', 'T', 'U', 'V', 'W', 'X', 'Y'};
    
    // 计数器
    int cnt = 0;
    
    // 枚举所有长度大于1的子串
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            // 检查是否是回文串
            bool is_pal = true;
            for (int k = i, l = j; k < l; ++k, --l) {
                if (s[k] != s[l]) {
                    is_pal = false;
                    break;
                }
            }
            
            if (!is_pal) continue;
            
            // 检查每个字符是否有垂直对称轴
            bool valid = true;
            for (int k = i; k <= j; ++k) {
                if (sym.find(s[k]) == sym.end()) {
                    valid = false;
                    break;
                }
            }
            
            // 如果满足条件，计数器加1
            if (valid) {
                cnt++;
            }
        }
    }
    
    // 输出结果
    cout << cnt << endl;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();
        
        // 定义具有垂直对称轴的字符集合
        Set<Character> sym = new HashSet<>();
        char[] symChars = {'A', 'H', 'I', 'M', 'O', 'T', 'U', 'V', 'W', 'X', 'Y'};
        for (char c : symChars) {
            sym.add(c);
        }
        
        // 计数器
        int cnt = 0;
        
        // 枚举所有长度大于1的子串
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                // 检查是否是回文串
                boolean isPal = true;
                for (int k = i, l = j; k < l; k++, l--) {
                    if (s.charAt(k) != s.charAt(l)) {
                        isPal = false;
                        break;
                    }
                }
                
                if (!isPal) continue;
                
                // 检查每个字符是否有垂直对称轴
                boolean valid = true;
                for (int k = i; k <= j; k++) {
                    if (!sym.contains(s.charAt(k))) {
                        valid = false;
                        break;
                    }
                }
                
                // 如果满足条件，计数器加1
                if (valid) {
                    cnt++;
                }
            }
        }
        
        // 输出结果
        System.out.println(cnt);
    }
}

02. 无序区间中位数探索

问题描述

小毛最近在研究一种特殊的数组性质。他将"自然中位数"定义为：在一个长度为奇数的数组中，即使不对数组进行排序，其下标为 （从1开始计数）的元素恰好等于该数组排序后的中位数。

小毛称满足这一特性的数组为"稳定数组"。现在，他有一个长度为 的排列 ，想要知道 中有多少个连续的区间满足"稳定数组"的性质。

具体来说，他需要计算有多少对下标 ，满足区间长度 为奇数，且区间 构成一个"稳定数组"。

输入格式

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

第一行一个正整数 ，表示测试数据的组数。

对于每组测试数据，输入包含两行：

• 第一行一个整数 ，表示排列 的长度。
• 第二行 个整数 ，表示排列 。

保证输入是一个排列。 保证所有测试数据中 的总和不超过 。

输出格式

输出包含 行，每行一个整数，表示满足条件的区间对数。

样例输入

1
5
3 2 1 4 5

样例输出

7

数据范围

• 
• 
• 
• 所有测试数据中 的总和不超过10000

样例 解释说明

1 5 3 2 1 4 5	满足条件的区间有： [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [1, 3], [3, 5] 共7个区间

题解

这道题目要求我们找出排列中有多少个连续区间满足"稳定数组"的性质。所谓"稳定数组"，就是指长度为奇数的数组，其中位位置上的元素恰好等于该数组排序后的中位数。

首先，我们需要理解什么情况下一个区间满足"稳定数组"的性质。对于一个长度为奇数的数组，假设其长度为2k+1，中位数位置为k+1（从0开始计数），那么要使得该位置的元素是排序后的中位数，必须满足：恰好有k个元素比中位数小，k个元素比中位数大。

基于这个理解，我们可以设计一个算法：

1. 对于每一个长度为奇数的区间[l, r]，找出其中位位置mid = l + (r-l)/2
2. 计算区间内小于p[mid]的元素个数count_less和大于p[mid]的元素个数count_greater
3. 如果count_less == count_greater == (r-l)/2，则该区间满足条件

时间复杂度分析：

• 枚举所有长度为奇数的区间需要O(n²)的时间
• 对于每个区间，需要O(n)的时间计算小于和大于中位元素的个数
• 总时间复杂度为O(n³)

考虑到n最大为10000，直接使用O(n³)的算法会超时。我们需要优化算法。

优化思路：

1. 预处理：对于每个位置i，计算前缀中有多少元素小于p[i]和大于p[i]
2. 这样对于每个区间[l, r]，可以在O(1)时间内计算区间内小于p[mid]和大于p[mid]的元素个数

另一种思路是使用双指针或滑动窗口算法，维护当前区间内小于和大于中位元素的个数，但实现上会复杂一些。

最终，我们选择使用预处理的方法，它能将时间复杂度降低到O(n²)，足以通过题目的约束。

参考代码

• Python

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

def solve():
    # 读取测试用例数
    t = int(input())
    
    for _ in range(t):
        # 读取排列长度
        n = int(input())
        # 读取排列
        p = list(map(int, input().split()))
        
        # 计数器
        ans = 0
        
        # 枚举所有奇数长度区间
        for l in range(n):
            for r in range(l, n):
                # 检查区间长度是否为奇数
                if (r - l + 1) % 2 == 0:
                    continue
                
                # 计算中位数位置（从0开始）
                mid = l + (r - l) // 2
                mid_val = p[mid]
                
                # 计算区间内小于和大于mid_val的元素个数
                less_cnt = 0
                greater_cnt = 0
                for i in range(l, r + 1):
                    if p[i] < mid_val:
                        less_cnt += 1
                    elif p[i] > mid_val:
                        greater_cnt += 1
                
                # 检查是否满足条件
                if less_cnt == greater_cnt:
                    ans += 1
        
        # 输出结果
        print(ans)

if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

int solve() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n);
        for (int i = 0; i < n; ++i) {
            cin >> p[i];
        }
        
        int ans = 0;
        
        // 枚举所有奇数长度区间
        for (int l = 0; l < n; ++l) {
            for (int r = l; r < n; ++r) {
                // 检查区间长度是否为奇数
                if ((r - l + 1) % 2 == 0) {
                    continue;
                }
                
                // 计算中位数位置（从0开始）
                int mid = l + (r - l) / 2;
                int mid_val = p[mid];
                
                // 计算区间内小于和大于mid_val的元素个数
                int less_cnt = 0, greater_cnt = 0;
                for (int i = l; i <= r; ++i) {
                    if (p[i] < mid_val) {
                        less_cnt++;
                    } else if (p[i] > mid_val) {
                        greater_cnt++;
                    }
                }
                
                // 检查是否满足条件
                if (less_cnt == greater_cnt) {
                    ans++;
                }
            }
        }
        
        cout << ans << endl;
    }
    
    return 0;
}

int main() {
    ios::sync_with_stdio(false);