✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

携程

题目一：热销商品统计

1️⃣：维护A类商品和B类商品的计数器

2️⃣：遍历字符串，比较两个计数器大小并更新答案

难度：低

这道题目的关键在于理解前缀和的概念，维护两个计数器分别统计A和B的出现次数，并在每个位置比较两者大小。通过一次遍历即可得到答案，是一道简单的模拟题。

题目二：艺术设计对称变换

1️⃣：明确中心对称的定义，使得矩阵位置(i,j)的元素等于位置(n-1-i,m-1-j)的元素

2️⃣：遍历矩阵的一半位置，统计需要替换的位置数量

难度：中等

这道题目的关键在于理解中心对称的定义，并找出需要检查的位置对。通过只遍历矩阵的一半位置来避免重复计数，使用O(n×m)的时间复杂度即可解决问题。需要注意的是只能将'◯'变成'◆'，不能反向操作。

题目三：乐曲片段整理

1️⃣：分析和谐片段的特性：无下降或恰有一次下降且末元素不大于首元素

2️⃣：使用双指针和树状数组，高效统计满足条件的连续子序列数量

难度：中等偏难

这道题目需要深入理解连续子序列的性质，以及旋转后能形成非降序序列的条件。通过双指针技术结合树状数组数据结构，实现O(n log n)的时间复杂度解法。关键在于维护最近两次下降位置，并动态更新查询区间。

题目四：网络节点优化策略

1️⃣：定义两个状态，keep[u]表示保留节点u时的最大权值，bypass[u]表示删除节点u时的最大权值

2️⃣：自底向上的树形DP，计算每个节点的最优选择

难度：高

这道题目需要理解树结构上的操作特性，并设计合适的状态表示。通过树形动态规划，我们可以自底向上地计算每个节点的最优选择。关键是理解两个状态及其转移方程，并通过后序遍历有效地实现O(n)时间复杂度的解法。

01. 热销商品统计

问题描述

小基 经营着一家在线商店，她想分析哪种商品更受欢迎。每天，她会记录下商店的访问情况，用一个由字符 和 组成的字符串 来表示。其中，第 个字符 表示在第 时刻有人浏览了 A 类商品； 表示在第 时刻有人浏览了 B 类商品。

小基 想知道，从商店开业到现在（即考虑字符串的每个前缀），有多少个时刻 A 类商品的浏览次数严格多于 B 类商品。

输入格式

第一行一个整数 ，表示记录的总时长。

第二行一个长度为 的字符串，保证输入只含 或者 。

输出格式

一个整数，表示有多少个时刻 A 类商品的浏览次数严格多于 B 类商品。

样例输入

4
BAAA

样例输出

2

样例 解释说明

样例1	在检查每个前缀后：第一个时刻前缀"B"（A:0, B:1），A类商品浏览次数少于B类；第二个时刻前缀"BA"（A:1, B:1），A类商品浏览次数等于B类；第三个时刻前缀"BAA"（A:2, B:1），A类商品浏览次数多于B类；第四个时刻前缀"BAAA"（A:3, B:1），A类商品浏览次数多于B类。因此答案是2个时刻。

数据范围

• 
• 字符串中只包含字符 和

题解

这道题目的本质是统计前缀和。我们需要计算每个前缀中A类商品的浏览次数是否严格多于B类商品的浏览次数。

解题思路很直观：从左到右遍历字符串，维护两个计数器，分别记录A类商品和B类商品的浏览次数。每次遍历一个字符后，比较两个计数器的大小。如果A的计数器值严格大于B的计数器值，就说明当前时刻满足条件，答案加1。

具体步骤如下：

1. 初始化A类商品计数器cntA和B类商品计数器cntB都为0，初始化答案ans为0
2. 从左到右遍历字符串：
   • 如果当前字符是'A'，则cntA加1
   • 如果当前字符是'B'，则cntB加1
   • 检查如果cntA > cntB，则ans加1
3. 遍历结束后，ans即为所求

这种方法的时间复杂度是O(n)，其中n是字符串的长度，我们只需要遍历一遍字符串。空间复杂度是O(1)，只需要常数级别的额外空间来存储计数器和答案。

对于本题的数据范围（n ≤ 10^5），这个解法可以轻松应对，不会超时。

参考代码

• Python

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

# 读取输入
n = int(input())
s = input()

# 初始化计数器和答案
cnt_a = 0
cnt_b = 0
ans = 0

# 遍历字符串
for c in s:
    if c == 'A':  # 如果是A类商品
        cnt_a += 1
    else:  # 如果是B类商品
        cnt_b += 1
    
    # 检查条件并更新答案
    if cnt_a > cnt_b:
        ans += 1

# 输出结果
print(ans)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    int n;
    string s;
    cin >> n >> s;
    
    // 初始化计数器和答案
    int cnt_a = 0, cnt_b = 0, ans = 0;
    
    // 遍历字符串
    for (char c : s) {
        if (c == 'A') {  // 如果是A类商品
            cnt_a++;
        } else {  // 如果是B类商品
            cnt_b++;
        }
        
        // 检查条件并更新答案
        if (cnt_a > cnt_b) {
            ans++;
        }
    }
    
    // 输出结果
    cout << ans << "\n";
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        int n = sc.nextInt();
        String s = sc.next();
        
        // 初始化计数器和答案
        int cntA = 0, cntB = 0, ans = 0;
        
        // 遍历字符串
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == 'A') {  // 如果是A类商品
                cntA++;
            } else {  // 如果是B类商品
                cntB++;
            }
            
            // 检查条件并更新答案
            if (cntA > cntB) {
                ans++;
            }
        }
        
        // 输出结果
        System.out.println(ans);
    }
}

02. 艺术设计对称变换

问题描述

小毛是一位艺术设计师，他在设计一款新的图案，想要使其具有中心对称性。他有一个 的矩阵画布，上面已经绘制了一些符号，用 和 表示。为了达到中心对称的效果，小毛需要将一些 符号替换为 符号（但不能将 替换为 ）。

中心对称的定义是：如果将矩阵绕中心点旋转 ，得到的矩阵与原矩阵完全相同。

小毛想知道，最少需要进行多少次替换操作，才能使整个画布达到中心对称的效果。

输入格式

第一行输入两个整数 ，表示矩阵的行数和列数。

接下来 行，每行输入一个长度为 的字符串 ，仅由字符 和 组成，表示初始矩阵。

输出格式

输出一个整数，表示最少需要进行的替换操作次数。

样例输入

2 2
◯◯
◯◆

样例输出

1

样例 解释说明

样例1	初始画布为： ◯◯ ◯◆ 将左上角的 ◯ 替换为 ◆，得到： ◆◯ ◯◆ 可以验证，此时矩阵具有中心对称性（旋转180°后不变）。只需要1次替换操作。

数据范围

• 
• 矩阵中只包含字符 和

题解

这道题目要求我们将矩阵变成中心对称的，只能将 '◯' 变成 '◆'，不能反向操作。

首先，我们需要理解中心对称的含义。如果将矩阵绕中心点旋转180°后不变，那么矩阵中任意位置 (i, j) 的元素应该等于位置 (n-1-i, m-1-j) 的元素。这两个位置形成一个对称点对。

解题思路：

1. 遍历矩阵的每个位置 (i, j)
2. 找到其对称位置 (n-1-i, m-1-j)
3. 如果两个位置的字符不同，并且至少有一个是 '◯'，那么必须进行替换操作
4. 为了避免重复计数，我们只处理矩阵的一半位置，即满足 (i < n-1-i) || (i == n-1-i && j <= m-1-j) 的位置

具体算法实现：

1. 遍历符合条件的位置 (i, j)
2. 计算对称位置 (ii = n-1-i, jj = m-1-j)
3. 如果 (i, j) 和 (ii, jj) 的字符不同，答案加1

注意，由于只能将 '◯' 变成 '◆'，如果对称点对中两个位置都是 '◆'，则无法达成对称，但题目保证有解，因此不会出现这种情况。

时间复杂度：O(n×m)，我们只需要遍历矩阵的一半位置。 空间复杂度：O(n×m)，用于存储矩阵。

参考代码

• Python

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

# 读取输入
n, m = map(int, input().split())
grid = []
for _ in range(n):
    grid.append(input())

# 计算最小操作次数
ans = 0
for i in range(n):
    for j in range(m):
        # 计算对称位置
        ii, jj = n - 1 - i, m - 1 - j
        # 只处理每对位置一次
        if i > ii or (i == ii and j > jj):
            continue
        # 如果对称位置字符不同，需要进行替换
        if grid[i][j] != grid[ii][jj]:
            ans += 1

# 输出结果
print(ans)

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 读取输入
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    
    // 计算最小操作次数
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 计算对称位置
            int ii = n - 1 - i;
            int jj = m - 1 - j;
            
            // 只处理每对位置一次
            if (i > ii || (i == ii && j > jj)) {
                continue;
            }
            
            // 如果对称位置字符不同，需要进行替换
            if (grid[i][j] != grid[ii][jj]) {
                ans++;
            }
        }
    }
    
    // 输出结果
    cout << ans << "\n";
    return 0;
}

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] grid = new char[n][m];
        
        for (int i = 0; i < n; i++) {
            String line = sc.next();
            for (int j = 0; j < m; j++) {
                grid[i][j] = line.charAt(j);
            }
        }
        
        // 计算最小操作次数
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 计算对称位置
                int ii = n - 1 - i;
                int jj = m - 1 - j;
                
                // 只处理每对位置一次
                if (i > ii || (i == ii && j > jj)) {
                    continue;
                }
                
                // 如果对称位置字符不同，需要进行替换
                if (grid[i][j] != grid[ii][jj]) {
                    ans++;
                }
            }
        }
        
        // 输出结果
        System.out.println(ans);
    }
}

03. 乐曲片段整理

问题描述

小柯是一位音乐编辑，她正在整理一段乐曲的音符序列。她发现一个"和谐片段"有一个特殊的性质：如果将该片段的一个后缀移动到最前面，整个片段的音符序列就会变成非降序排列（即每个音符的音高不低于前一个音符）。

例如：

• 音符序列 [4, 7, 8, 9, 2, 3] 是一个和谐片段，因为可以将 [2, 3] 移动到最前面，得到 [2, 3, 4, 7, 8, 9]，这是一个非降序序列。
• 音符序列 [1, 2, 3, 4, 5] 是一个和谐片段，因为它本身就是非降序的。
• 音符序列 [5, 2, 2, 1] 不是一个和谐片段，因为无论怎么移动后缀，都无法得到非降序序列。

现在小柯有一段完整的乐曲音符序列，她想知道这段乐曲中有多少个非空的连续子片段是和谐片段。

输入格式

第一行输入一个正整数 ，表示乐曲的音符数量。

第二行输入 个正整数 ，表示每个音符的音高。

输出格式

输出一个整数，表示乐曲中和谐片段的数量。

样例输入

3
3 2 1

样例输出

5

样例 解释说明

样例1	乐曲中的非空连续子片段有：[3]、[2]、[1]、[3,2]、[2,1]、[3,2,1]。 其中，[3]、[2]、[1]是单个音符，显然是和谐片段。 [3,2]可以将[2]移到前面得到[2,3]，是和谐片段。 [2,1]可以将[1]移到前面得到[1,2]，是和谐片段。 [3,2,1]无论怎么移动后缀，都无法得到非降序序列，不是和谐片段。 因此，共有5个和谐片段。

数据范围

• 
• 

题解

这道题要求我们计算有多少个连续子序列是"和谐片段"，即可以通过将某个后缀移到最前面使序列变成非降序。

先分析下什么样的序列可以变成非降序：

1. 本身就是非降序的序列（例如[1,2,3,4]）
2. 有一次下降，且最后一个元素不大于第一个元素（例如[3,4,1,2]）

对于有多次下降的序列，无论如何调整都不可能变成非降序。

基于这个特性，我们可以遍历数组中的每个位置作为右端点，然后考虑不同的左端点，统计满足条件的子序列个数。

具体算法如下：

1. 使用双指针法，维护右端点r和两个左指针：

   • l0：确保子序列中没有下降（即子序列是非降序的）
   • l1：确保子序列最多有一次下降

2. 对于每个右端点r，我们需要计算：

   • 无下降的子序列数量：r - l0 + 1
   • 恰好有一次下降且满足条件的子序列数量

3. 为了高效计算第二类子序列的数量，我们需要维护一个数据结构（如树状数组），以便快速查询在区间[l1..l0-1]中，有多少个左端点l满足a[l] >= a[r]。

具体实现中，我们需要：

1. 跟踪最近两次下降的位置（d1和d2）
2. 动态维护l0和l1
3. 对于每个右端点，计算两类子序列的数量并累加到答案中

由于数组中的元素范围很大，我们需要进行离散化处理。

时间复杂度分析：

• 对于每个右端点，我们进行常数次树状数组操作，每次操作的时间复杂度为O(log n)
• 总体时间复杂度为O(n log n)，其中n是数组长度

空间复杂度：O(n)，用于存储数组和树状数组。

参考代码

• Python

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

# 树状数组类
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, i, val):
        while i <= self.n:
            self.tree[i] += val
            i += i & -i
    
    def query(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

# 主函数
n = int(input())
a = [0] + list(map(int, input().split()))

# 离散化
vals = sorted(set(a[1:]))
rank = {v: i for i, v in enumerate(vals, 1)}

# 初始化树状数组
bit = BIT(len(vals))

ans = 0
d1, d2 = -