✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

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

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

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

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

题目一：小毛的评论审核

1️⃣：将问题转化为图论中的最大独立集问题

2️⃣：使用贪心策略构造独立集：排序后从左到右"能选就选"

3️⃣：根据奇偶性约束调整最终答案

难度：中等

这道题目巧妙地将评论冲突问题转化为图论问题。关键观察是每次删除操作必须删除偶数个元素，因此最终保留的元素数量与原数组具有相同的奇偶性。通过排序和贪心策略，可以在 时间内求解。

题目二：小兰的内容管理

1️⃣：使用游程编码将字符串转换为(字符, 长度)对的序列

2️⃣：直接模拟推荐过程：每轮除第一段外的段都失去首个创作者

3️⃣：动态维护段列表：删除空段并合并相邻同类型段

难度：中等

这道题目通过直接模拟推荐过程来求解。使用游程编码优化存储，每轮模拟中除了第一个段外，其他段都会有第一个创作者被推荐移除。关键是正确处理段的合并：当某段被完全删除后，相邻的同类型段会自动合并。算法简洁直观，时间复杂度为 。

题目三：小基的能量网络

1️⃣：将区间峰值问题转化为前缀和最大值问题

2️⃣：使用单调栈预处理每个位置的左右边界

3️⃣：枚举峰值位置，结合哈希表和二分查找统计答案

难度：困难

这道题目结合了前缀和、单调栈、哈希表和二分查找等多种算法技巧。核心思想是固定峰值位置，然后统计满足条件的区间数量。通过巧妙的数学转化和高效的数据结构，实现了 的时间复杂度。

01. 小毛的评论审核

问题描述

小毛是一位社交平台的内容审核专员，他负责维护平台评论区的内容质量。在日常工作中，小毛发现当评论的情感分数接近时，用户往往会产生观点冲突，影响社区氛围。

为了优化评论区的体验，小毛需要设计一套智能筛选机制。现在有 条评论，每条评论都有一个情感分数 。如果两条评论的分数差值不超过 （即 ），则认为这两条评论可能产生观点冲突。

小毛可以执行删除操作：每次选择两条可能产生冲突的评论，将它们同时删除（评论总数减少 ）。小毛希望经过若干次操作后，剩余的评论之间不会产生任何观点冲突，并且保留的评论数量尽可能多。

请帮助小毛计算，在最优策略下，最多能保留多少条评论。

输入格式

每个测试文件包含多组测试数据。第一行输入一个整数 ，表示测试数据的组数。

对于每组测试数据：

第一行包含两个整数 和 ，其中 ，，分别表示评论数量和冲突阈值。

第二行包含 个整数 ，其中 ，表示每条评论的情感分数。

保证单个测试文件中所有 的总和不超过 。

输出格式

对于每组测试数据，输出一个整数，表示最多能保留的评论数量。

样例输入

2
5 2
1 2 4 7 9
4 0
1 1 2 5

样例输出

3
2

数据范围

题解

这道题本质上是一个图论中的最大独立集问题，但由于特殊的约束条件，我们可以用贪心策略来解决。

核心思路：

1. 将所有评论按情感分数排序
2. 相邻分数差值不超过 的评论之间存在"冲突边"
3. 每次删除操作必须删除2条评论，因此被删除的评论总数必须是偶数
4. 最终保留的评论数量与原总数 必须具有相同的奇偶性

算法步骤：

1. 排序：将所有评论按分数升序排列
2. 贪心构造独立集：从左到右扫描，采用"能选就选"的策略：
   • 选择当前最小的未被禁止的分数
   • 跳过所有与它差值 ≤ 的后续分数
3. 奇偶性调整：
   • 如果独立集大小与 奇偶性相同，直接输出
   • 否则需要再删除1个元素，输出独立集大小-1

为什么贪心策略有效： 在一维数轴上，"最左能选就选"的贪心策略能够保证得到最大的独立集。这是因为选择更小的数不会影响后续更大数字的选择机会，而且能为后续选择留下更多空间。

时间复杂度：，主要消耗在排序上 空间复杂度：，用于存储数组

参考代码

• Python

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

def solve():
    n, d = map(int, input().split())
    a = list(map(int, input().split()))
    
    # 对评论分数进行排序
    a.sort()
    
    # 贪心构造最大独立集
    cnt = 0
    i = 0
    while i < n:
        cnt += 1  # 选择当前分数
        limit = a[i] + d  # 计算冲突范围上界
        i += 1
        # 跳过所有可能产生冲突的分数
        while i < n and a[i] <= limit:
            i += 1
    
    # 奇偶性调整：保证删除的评论数为偶数
    if (n - cnt) % 2 == 1:
        cnt -= 1
    
    return cnt

T = int(input())
for _ in range(T):
    print(solve())

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        long long d;
        cin >> n >> d;
        
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        // 对评论分数进行排序
        sort(a.begin(), a.end());
        
        // 贪心构造最大独立集
        int cnt = 0;
        int i = 0;
        while (i < n) {
            cnt++;  // 选择当前分数
            long long limit = a[i] + d;  // 计算冲突范围上界
            i++;
            // 跳过所有可能产生冲突的分数
            while (i < n && a[i] <= limit) {
                i++;
            }
        }
        
        // 奇偶性调整：保证删除的评论数为偶数
        if ((n - cnt) & 1) {
            cnt--;
        }
        
        cout << cnt << '\n';
    }
    
    return 0;
}

• Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        while (T-- > 0) {
            String[] line1 = br.readLine().split(" ");
            int n = Integer.parseInt(line1[0]);
            long d = Long.parseLong(line1[1]);
            
            String[] line2 = br.readLine().split(" ");
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(line2[i]);
            }
            
            // 对评论分数进行排序
            Arrays.sort(a);
            
            // 贪心构造最大独立集
            int cnt = 0;
            int i = 0;
            while (i < n) {
                cnt++;  // 选择当前分数
                long limit = a[i] + d;  // 计算冲突范围上界
                i++;
                // 跳过所有可能产生冲突的分数
                while (i < n && a[i] <= limit) {
                    i++;
                }
            }
            
            // 奇偶性调整：保证删除的评论数为偶数
            if ((n - cnt) % 2 == 1) {
                cnt--;
            }
            
            System.out.println(cnt);
        }
    }
}

02. 小兰的内容管理

问题描述

小兰是一位社交媒体平台的内容运营专员，她负责管理平台上的内容推荐系统。平台上有两种主要内容类型：生活分享（用 表示）和知识科普（用 表示）。

现在有 个内容创作者按照一定顺序排列，用长度为 的 字符串 表示他们的内容类型，其中：

• 若 ，则第 位创作者主要发布生活分享内容
• 若 ，则第 位创作者主要发布知识科普内容

平台会进行无限轮的内容互动推荐，每一轮的规则如下：

• 所有创作者同时向右侧（队列后方）进行内容推荐
• 每个创作者只会向右侧第一个不同类型的创作者推荐内容，如果右侧没有不同类型的创作者，则不会产生推荐
• 每轮所有推荐动作并行计算，然后将所有收到推荐的创作者移出队列，剩余创作者重新排列进入下一轮

这个过程会持续进行，直到不再有推荐发生为止。

请帮助小兰计算整个过程中总共有多少个创作者收到了推荐。

输入格式

第一行包含一个正整数 ，表示创作者的数量。

第二行包含一个长度为 且只由字符 '' 和 '' 构成的字符串 ，表示创作者的内容类型分布，其中 为从左向右第 位创作者的类型。

输出格式

输出一个整数，表示所有推荐结束后总共有多少个创作者收到了推荐。

样例输入

5
11101

样例输出

2

样例	解释说明
样例1	第一轮：第3个创作者（''）推荐给第4个创作者（''），第4个创作者（''）推荐给第5个创作者（''），共2个创作者收到推荐；移除后剩余前3个创作者形成""，此时全是生活分享类型，不再发生推荐

数据范围

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

题解

这道题需要直接模拟推荐过程，通过游程编码（Run-Length Encoding）来高效处理。

核心思路：

1. 将原字符串进行游程编码，得到连续段序列 的列表
2. 直接模拟推荐过程：每轮除了第一个段以外，其他段都会有第一个创作者被推荐
3. 被推荐的创作者移除后，相邻的同类型段会自动合并
4. 重复此过程直到只剩一个段为止

模拟过程详解：

• 每轮推荐：除第一个段外，每个段的第一个创作者都会收到推荐
• 段长度减少：每个被推荐的段长度减1
• 空段删除：长度为0的段被完全移除
• 同类型合并：相邻的同类型段会立即合并

算法步骤：

1. 对原字符串进行游程编码
2. 循环模拟推荐过程：
   • 统计本轮被推荐的创作者数量
   • 更新各段长度（除第一段外都减1）
   • 删除空段并合并相邻同类型段
3. 累加所有轮次的推荐数量

时间复杂度： 空间复杂度：

参考代码

• Python

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

def solve():
    n = int(input())
    s = input().strip()
    
    # 游程编码：将字符串转换为(字符, 长度)对的列表
    runs = []
    i = 0
    while i < n:
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        runs.append((s[i], j - i))
        i = j
    
    ans = 0  # 收到推荐的创作者总数
    
    # 模拟推荐过程
    while len(runs) > 1:
        # 本轮被推荐的创作者数量 = 除第一个段外的段数
        ans += len(runs) - 1
        
        # 第一步：除第一个段外，每个段都失去第一个创作者
        for i in range(1, len(runs)):
            runs[i] = (runs[i][0], runs[i][1] - 1)
        
        # 第二步：重建段列表，删除空段并合并相邻同类型段
        new_runs = [runs[0]]  # 第一个段始终保留
        for i in range(1, len(runs)):
            if runs[i][1] == 0:  # 段完全消失
                continue
            # 如果与前一个段类型相同，则合并
            if new_runs[-1][0] == runs[i][0]:
                char, length = new_runs[-1]
                new_runs[-1] = (char, length + runs[i][1])
            else:
                new_runs.append(runs[i])
        
        runs = new_runs
    
    return ans

pr