✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：物品种类统计

1️⃣：使用集合或哈希表统计不同物品编号的数量

2️⃣：利用数学公式 n - 不同种类数 计算最终答案

难度：简单

这道题目的关键在于理解"保持物品种类多样性不变"的含义。对于每种不同的物品编号，都必须至少保留一件，因此答案就是总数减去不同种类数。算法简单直观，时间复杂度为 O(n)。

题目二：书籍排列游戏

1️⃣：统计字符串中每个字母的出现次数

2️⃣：计算出现奇数次的字母个数

3️⃣：利用回文串性质，答案为 max(1, 奇数次字母个数)

难度：中等

这道题目结合了字符串处理和回文串的性质。关键洞察是在回文串中最多只能有一个字符出现奇数次，其余字符都必须成对出现。通过统计奇数次字符的数量，可以直接得出最少分割数。

题目三：网络监控数据分析

1️⃣：使用扫描线算法离线处理所有查询

2️⃣：维护两个树状数组分别记录奇数次异或和唯一值异或

3️⃣：利用异或性质计算偶数次异或，通过前缀异或回答区间查询

难度：中等偏难

这道题目是一个复杂的区间查询问题，需要理解异或运算的性质和树状数组的应用。通过扫描线算法和两个树状数组的配合，可以在 O((n+q)log n) 时间内高效解决所有查询，体现了算法设计的巧妙性。

01. 物品种类统计

问题描述

小兰是一位收纳达人，她有一个储物箱里装着 件物品。每件物品都有一个编号，相同编号的物品表示同一种类。小兰希望精简储物箱，但要求保持物品种类的多样性不变，即每种物品至少要保留一件。

现在小兰想知道，在满足条件的前提下，她最多可以移出多少件物品？

输入格式

第一行包含一个正整数 ，表示物品的总数量。

第二行包含 个正整数 ，表示每件物品的编号。

输出格式

输出一个整数，表示最多可以移出的物品数量。

样例输入

5
1 2 3 4 5

4
2 1 1 2

样例输出

0

2

样例	解释说明
样例1	每种物品都只有一件，无法移出任何物品
样例2	编号为1和2的物品各有两件，可以各移出一件，共移出2件物品

数据范围

• 
• 

题解

这道题的核心思路是理解"保持物品种类多样性不变"的含义。

如果要保持物品种类不变，那么对于每种不同的物品编号，都必须至少保留一件。换句话说，如果某种编号的物品有多件，那么除了保留一件外，其余的都可以移出。

具体做法：

1. 统计数组中有多少种不同的物品编号
2. 假设物品总数为 ，不同物品种类数为
3. 那么最多可以移出的物品数量就是

举个例子：如果有物品编号 [2, 1, 1, 2]，其中编号1出现2次，编号2出现2次，总共有2种不同的物品。为了保持种类不变，编号1和编号2都至少要保留1件，所以最多可以移出 4 - 2 = 2 件物品。

时间复杂度：，只需要遍历一次数组统计不同元素个数。

参考代码

Python

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

n = int(input())
arr = list(map(int, input().split()))

# 使用集合统计不同物品种类数
unique_cnt = len(set(arr))

# 最多可移出的物品数 = 总数 - 不同种类数
print(n - unique_cnt)

Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 使用哈希集合统计不同物品种类
    unordered_set<int> kinds;
    for (int i = 0; i < n; i++) {
        int item;
        cin >> item;
        kinds.insert(item);  // 添加到集合中
    }
    
    // 输出最多可移出的物品数
    cout << n - kinds.size() << endl;
    
    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 n = Integer.parseInt(br.readLine());
        String[] tokens = br.readLine().split(" ");
        
        // 使用HashSet统计不同物品种类数
        HashSet<Integer> kindSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int itemId = Integer.parseInt(tokens[i]);
            kindSet.add(itemId);  // 添加到集合
        }
        
        // 输出最多可移出的物品数量
        System.out.println(n - kindSet.size());
    }
}

02. 书籍排列游戏

问题描述

小毛是一位图书管理员，他有一排书架用来存放标有字母标签的书籍。现在他收到了一串由小写英文字母组成的书籍标签序列，他可以任意重新排列这些书籍的顺序。

小毛希望将重新排列后的书籍分成若干个连续的区间，使得每个区间内的书籍标签序列都是对称的（即从左往右读和从右往左读完全相同）。请问小毛最少需要将书架分成多少个区间？

输入格式

输入一行，包含一个由小写英文字母组成的字符串 ，其中 ， 表示字符串的长度。

输出格式

输出一个整数，表示最少需要分成的区间数量。

样例输入

baozii

zrnstnsr

样例输出

4

2

样例	解释说明
样例1	可以重排为 baoizi，然后分成 b, a, o, izi 四个对称区间
样例2	可以重排为合适的顺序，最少分成2个对称区间

数据范围

• 
• 字符串仅包含小写英文字母

题解

这道题的关键是理解对称字符串（回文串）的性质。

在一个回文串中，除了可能存在一个位于中间的字符外，其他所有字符都必须成对出现。也就是说，在一个回文串中，最多只能有一个字符出现奇数次，其余字符必须出现偶数次。

基于这个性质，我们可以分析：

1. 统计输入字符串中每个字母的出现次数
2. 计算有多少个字母出现了奇数次，设这个数量为
3. 由于每个回文串最多只能容纳一个出现奇数次的字母，所以至少需要 个回文串来安排这些奇数次字母
4. 特殊情况：如果所有字母都出现偶数次（），那么整个字符串可以排列成一个回文串

因此，答案就是 。

构造方案也很简单：

• 将所有出现偶数次的字母平均分配到各个回文串中
• 将每个出现奇数次的字母分别放到不同回文串的中心位置

时间复杂度：，只需要统计各字母的出现次数。

参考代码

Python

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

s = input()

# 统计每个字母的出现次数
char_cnt = {}
for ch in s:
    char_cnt[ch] = char_cnt.get(ch, 0) + 1

# 计算出现奇数次的字母个数
odd_cnt = 0
for cnt in char_cnt.values():
    if cnt % 2 == 1:
        odd_cnt += 1

# 输出最少区间数
print(max(1, odd_cnt))

Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    
    // 统计26个字母的出现次数
    vector<int> freq(26, 0);
    for (char ch : s) {
        freq[ch - 'a']++;
    }
    
    // 计算出现奇数次的字母个数
    int odd_num = 0;
    for (int cnt : freq) {
        if (cnt & 1) {  // 判断是否为奇数
            odd_num++;
        }
    }
    
    // 输出最少分割数
    cout << max(1, odd_num) << endl;
    
    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));
        
        String str = br.readLine();
        
        // 使用数组统计26个字母的出现次数
        int[] charFreq = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            charFreq[ch - 'a']++;
        }
        
        // 统计出现奇数次的字母数量
        int oddCount = 0;
        for (int freq : charFreq) {
            if (freq % 2 == 1) {
                oddCount++;
            }
        }
        
        // 输出最少区间数量
        System.out.println(Math.max(1, oddCount));
    }
}

03. 网络监控数据分析

问题描述

小基是一名网络安全工程师，她需要分析一段时间内的网络监控数据。监控系统记录了 个时刻的网络状态值，形成了一个数组 。

为了检测网络异常，小基需要对特定时间段进行分析。她设计了两种分析方式：

• 方式一：在时间段 内，找出所有出现次数为奇数的状态值，计算这些值的异或结果；

• 方式二：在时间段 内，找出所有出现次数为偶数且至少出现两次的状态值，计算这些值的异或结果。

如果某个时间段内没有符合条件的状态值，则结果为 。

现在小基有 个时间段需要分析，请帮助她快速得到每个查询的结果。

输入格式

第一行包含两个正整数 ，分别表示监控数据的长度和查询次数。

第二行包含 个正整数 ，表示各时刻的网络状态值。

接下来 行，每行包含三个整数 ，其中 表示分析方式（ 或 ）， 表示时间段的左右端点。

输出格式

对每个查询，输出一行整数，表示对应的异或结果。

样例输入

10 5
1 2 2 3 1 5 8 9 1 7
1 1 2
1 5 9
2 1 2
2 5 9
2 2 9

样例输出

3
4
0