✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

京东

题目一：小毛的密码破译

1️⃣：使用位掩码记录每种字符出现次数的奇偶性

2️⃣：贪心策略维护当前片段，当掩码中1的个数超过1时进行分割

3️⃣：时间复杂度 O(n)，空间复杂度 O(1)

难度：中等

这道题的核心在于理解"平衡"片段的数学本质：一个片段是平衡的当且仅当其中最多只有一种字符出现奇数次。通过位掩码技巧可以高效地判断和维护这个条件，结合贪心策略得到最优解。

题目二：小兰的花园观赏计划

1️⃣：使用扫描线算法统计不同时间段的花朵绽放情况

2️⃣：计算每种花独自绽放和双花绽放的时间长度

3️⃣：通过调整收益公式找到最优的花朵调整方案

难度：中等偏难

这道题结合了区间处理和优化问题。关键是理解调整一种花的位置会如何影响"恰好一种花绽放"的时间长度，通过扫描线算法高效计算各种情况下的时间贡献，最终找到最优调整策略。

01. 小毛的密码破译

问题描述

小毛是一名密码学专家，最近他收到了一份来自古代的加密信息。这份信息由一串小写字母组成，每个字母代表一种特殊的符号。

根据古籍记载，要成功破译这段加密信息，需要将其分割成若干个片段。对于每个片段，相同的符号可以两两配对消除。如果一个片段经过配对消除后，要么所有符号都被消除，要么只剩下一个符号，那么这个片段就被认为是"平衡的"。

小毛想知道，最少需要将这段加密信息分割成多少个片段，才能使得每个片段都是平衡的。

输入格式

输入一行，包含一个由小写字母组成的字符串 ，表示加密信息。字符串长度不超过 。

输出格式

输出一个整数，表示最少需要分割成的片段数。

样例输入

xyz

abcdabcd

rrzbbaau

样例输出

3

1

2

数据范围

• 
• 只包含小写字母 到

题解

这道题的关键在于理解什么样的片段是"平衡的"。

对于一个片段，如果相同字符两两消除后最多剩下1个字符，那么这个片段中所有字符的出现次数最多只能有1个是奇数。

我们可以用一个26位的二进制数（掩码）来表示当前片段中每种字符出现次数的奇偶性。如果某个字符出现奇数次，对应位为1；出现偶数次，对应位为0。

一个片段是平衡的，当且仅当其掩码中1的个数不超过1个。

算法采用贪心策略：从左到右扫描字符串，维护当前片段的掩码。每当加入一个新字符后，掩码中1的个数超过1时，就必须在这个字符之前进行分割，然后从当前字符开始新的片段。

这个贪心策略是正确的，因为如果存在更优解（延后分割），那么前面的片段必然包含更多字符，但此时掩码中1的个数已经超过1，不满足平衡条件。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

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

def solve():
    s = input()
    ans = 1  # 至少需要一段
    mask = 0  # 当前段的奇偶掩码
    
    for ch in s:
        # 计算加入当前字符后的新掩码
        bit_pos = ord(ch) - ord('a')
        new_mask = mask ^ (1 << bit_pos)
        
        # 检查1的个数是否超过1
        if bin(new_mask).count('1') <= 1:
            mask = new_mask  # 继续当前段
        else:
            ans += 1  # 必须分割
            mask = 1 << bit_pos  # 新段从当前字符开始
    
    print(ans)

solve()

• Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    
    int cnt = 1;  // 至少一段
    int mask = 0;  // 当前段的奇偶位掩码
    
    for (char c : s) {
        int bit = 1 << (c - 'a');
        int new_mask = mask ^ bit;
        
        // 检查popcount是否不超过1
        if (__builtin_popcount(new_mask) <= 1) {
            mask = new_mask;  // 继续当前段
        } else {
            cnt++;  // 必须切割
            mask = bit;  // 新段开始
        }
    }
    
    cout << cnt << "\n";
    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();
        
        int segCnt = 1;  // 至少一段
        int bitMask = 0;  // 当前段的奇偶掩码
        
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int bitPos = ch - 'a';
            int newMask = bitMask ^ (1 << bitPos);
            
            // 检查二进制1的个数
            if (Integer.bitCount(newMask) <= 1) {
                bitMask = newMask;  // 继续当前段
            } else {
                segCnt++;  // 必须分割
                bitMask = 1 << bitPos;  // 新段开始
            }
        }
        
        System.out.println(segCnt);
        sc.close();
    }
}

02. 小兰的花园观赏计划

问题描述

小兰是一位园艺爱好者，她在自己的花园里种植了 种特殊的花卉。这些花卉具有一个独特的特性：每种花都会在特定的时间段内绽放，且绽放时间都是 个时间单位。

具体来说，第 种花会在时间段 内绽放。

小兰有一个特殊的癖好：她认为当花园中恰好有一种花在绽放时，景色是最美的。如果同时有多种花绽放，她觉得过于繁华而失去了优雅；如果没有花绽放，她又觉得过于单调。

作为一位园艺大师，小兰可以使用一次特殊的园艺技巧：她可以选择任意一种花，将其绽放开始时间 调整为任意正整数值。

小兰想知道，通过最多一次调整，她最多能让"恰好有一种花绽放"的时间持续多久？

输入格式

第一行包含一个正整数 ，表示测试用例的数量。

对于每个测试用例：

第一行包含两个正整数 和 ，分别表示花的种类数和每种花的绽放时长。

第二行包含 个正整数 ，表示每种花的初始绽放开始时间。

输出格式

对于每个测试用例，输出一行一个非负整数，表示恰好有一种花绽放的最大时间长度。

样例输入

2
4 10
1 3 12 20
5 5
2 1 10 3 11

样例输出

36
12

数据范围

• 
• 
• 
• 调整时 可以设置为任意正整数

题解

这道题需要我们理解一个关键点：通过调整一种花的绽放时间，我们希望最大化"恰好有一种花绽放"的时间长度。

首先分析不调整时的情况。我们可以使用扫描线算法来计算：

1. 恰好有一种花绽放的总时间长度
2. 对于每种花 ，计算它独自绽放的时间长度（记为 ）
3. 对于每种花 ，计算它与恰好一种其他花同时绽放的时间长度（记为 ）

当我们将第 种花调整到一个与其他所有花都不重叠的位置时：

• 增加 个时间单位（这种花将独自绽放 个时间单位）
• 失去 个时间单位（原来这种花独自绽放的时间被移走）
• 增加 个时间单位（原来有两种花同时绽放的时间段，现在只有一种花绽放）

因此，调整第 种花的收益为：

最终答案是：，其中 是初始状态下恰好一种花绽放的