✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：魅力数字识别器

1️⃣：判断质因子和的奇偶性，转化为统计奇质因子个数

2️⃣：利用数论知识，只需判断不同奇质因子个数的奇偶性

难度：中等

这道题目的关键在于理解质因子和的奇偶性规律。由于2是唯一的偶质数，所以质因子和的奇偶性完全由奇质因子的个数决定。通过质因数分解和奇偶性判断，可以在 O(√n) 时间内高效求解。

题目二：评论区平衡艺术

1️⃣：识别所有不对称的位置对

2️⃣：将问题转化为区间翻转，统计连续段数量

3️⃣：利用贪心思想，每次操作修复一个连续段

难度：中等

这道题目结合了字符串处理和贪心算法。关键洞察是区间翻转操作对对称性的影响具有连续性，因此可以将问题转化为统计不对称位置的连续段数量，实现 O(n) 的高效解法。

题目三：艺术品展览馆规划

1️⃣：按观赏价值排序，处理连续性约束

2️⃣：使用贪心策略分配艺术品到展厅

3️⃣：维护活跃展厅状态，动态调整分组方案

难度：中等偏难

这道题目综合考查了贪心算法和数据结构的应用。通过巧妙的状态维护和贪心分配策略，将复杂的分组优化问题转化为可在 O(n log n) 时间内求解的算法问题。

01. 魅力数字识别器

问题描述

小兰是一位数学爱好者，她定义了一种特殊的"魅力数字"。对于一个正整数 ，如果它的所有不同质因子之和为奇数，那么这个数字就被称为魅力数字。

具体来说：

• 对于数字 ，它的不同质因子为 ，质因子和为 （奇数），所以 是魅力数字
• 特别地，当 时，没有质因子，质因子和视为 （偶数），所以 不是魅力数字

现在 小兰收集了许多数字，请帮助她判断每个数字是否为魅力数字。

输入格式

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

接下来 行，每行包含一个正整数 （），表示需要判断的数字。

输出格式

对于每个测试用例，输出一行。如果该数字是魅力数字，输出 YES，否则输出 NO。

样例输入

3
2
5
12

样例输出

NO
YES
YES

数据范围

样例	解释说明
样例1	数字 的不同质因子只有 ，质因子和为 （偶数），不是魅力数字
样例2	数字 的不同质因子只有 ，质因子和为 （奇数），是魅力数字
样例3	数字 的不同质因子为 ，质因子和为 （奇数），是魅力数字

题解

这道题的关键在于理解魅力数字的定义：一个数的所有不同质因子之和为奇数。

首先分析质因子和的奇偶性：

• 质数 是唯一的偶质数
• 所有其他质数都是奇数

因此，质因子和的奇偶性只取决于奇质因子的个数：

• 如果奇质因子个数为奇数个，那么和为奇数
• 如果奇质因子个数为偶数个，那么和为偶数

算法思路：

1. 特判 的情况，直接返回 NO
2. 统计 中不同奇质因子的个数
3. 如果个数为奇数，则是魅力数字

具体实现时，可以从 开始枚举所有奇数，检查是否为 的因子。对于每个因子，将其完全除掉后继续检查。最后如果 且为奇数，说明还有一个大的奇质因子。

时间复杂度为 ，对于给定的数据范围完全可以接受。

参考代码

• Python

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

def is_charm(n):
    if n == 1:
        return False
    
    odd_cnt = 0
    # 检查因子2
    if n % 2 == 0:
        while n % 2 == 0:
            n //= 2
    
    # 检查奇数因子
    i = 3
    while i * i <= n:
        if n % i == 0:
            odd_cnt += 1
            while n % i == 0:
                n //= i
        i += 2
    
    # 剩余的大质因子
    if n > 1:
        odd_cnt += 1
    
    return odd_cnt % 2 == 1

T = int(input())
for _ in range(T):
    n = int(input())
    print("YES" if is_charm(n) else "NO")

• Cpp

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

bool is_charm(long long n) {
    if (n == 1) return false;
    
    int odd_cnt = 0;
    // 处理因子2
    if (n % 2 == 0) {
        while (n % 2 == 0) n /= 2;
    }
    
    // 检查奇数因子
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            odd_cnt++;
            while (n % i == 0) n /= i;
        }
    }
    
    // 剩余的大质因子
    if (n > 1) odd_cnt++;
    
    return odd_cnt & 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;
        cout << (is_charm(n) ? "YES" : "NO") << '\n';
    }
    return 0;
}

• Java

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

public class Main {
    public static boolean isCharm(long n) {
        if (n == 1) return false;
        
        int oddCnt = 0;
        // 处理因子2
        if (n % 2 == 0) {
            while (n % 2 == 0) n /= 2;
        }
        
        // 检查奇数因子
        for (long i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                oddCnt++;
                while (n % i == 0) n /= i;
            }
        }
        
        // 剩余的大质因子
        if (n > 1) oddCnt++;
        
        return oddCnt % 2 == 1;
    }
    
    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) {
            long n = Long.parseLong(br.readLine());
            System.out.println(isCharm(n) ? "YES" : "NO");
        }
    }
}

02. 评论区平衡艺术

问题描述

小基是一位社交平台的内容运营专员，她负责管理用户评论区的互动状态。在一个热门话题下，有 条评论，每条评论都有一个互动状态：赞同（用 1 表示）或反对（用 0 表示）。

为了营造良好的讨论氛围，小基希望通过调整操作让整个评论区呈现"对称平衡"的状态，即第一条评论和最后一条评论的状态相同，第二条评论和倒数第二条评论的状态相同，以此类推。

小基的调整操作定义如下：

• 选择一个区间 （）
• 对该区间内的所有评论进行状态翻转：原本赞同的变为反对，原本反对的变为赞同

请计算小基最少需要进行多少次调整操作，才能让评论区达到对称平衡状态。

输入格式

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

对于每个测试用例：

• 第一行包含一个正整数 （），表示评论的数量
• 第二行包含一个长度为 的字符串 ，由字符 0 和 1 组成，表示评论的互动状态

所有测试用例的 之和不超过 。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示使评论区达到对称平衡所需的最少调整操作次数。

样例输入

2
2
01
3
010

样例输出

1
0

数据范围

• 
• 
• 所有测试用例的 之和不超过

题解

这道题的核心是理解对称平衡的含义：对于位置 和 ，它们的状态必须相同。

首先，我们找出所有不满足对称条件的位置对。设 表示位置 和 的状态不同，需要修复。

关键观察：一次区间翻转操作 对每个位置对 的影响是：

• 如果区间恰好只覆盖其中一个位置，则该位置对的 状态会翻转
• 可以证明，被一次操作影响的位置对在 数组中必定形成连续的一段

因此，问题转化为：使用最少的操作次数，让所有 都变为 0。由于每次操作最多能修复一段连续的 区间，所以答案就是 数组中值为 1 的连续段数量。

算法步骤：

1. 构建 数组，标记所有不对称的位置对
2. 扫描 数组，统计连续的 1 段的数量

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

参考代码

• Python

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

T = int(input())
for _ in range(T):
    n = int(input())
    s = input()
    
    # 找出所有不对称的位置
    diff_pos = []
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            diff_pos.append(i)
    
    if not diff_pos:
        print(0)
        continue
    
    # 统计连续段数量
    cnt = 1
    for i in range(1, len(diff_pos)):
        if diff_pos[i] != diff_pos[i-1] + 1:
            cnt += 1
    
    print(cnt)

• 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;
        string s;
        cin >> n >> s;
        
        vector<int> diff_pos;
        // 找出所有不对称的位置
        for (int i = 0; i < n / 2; ++i) {
            if (s[i] != s[n - 1 - i]) {
                diff_pos.push_back(i);
            }
        }
        
        if (diff_pos.empty()) {
            cout << 0 << '\n';
            continue;
        }
        
        // 统计连续段数量
        int cnt = 1;
        for (int i = 1; i < diff_pos.size(); ++i) {
            if (diff_pos[i] != diff_pos[i-1] + 1) {
                cnt++;
            }
        }
        
        cout << cnt << '\n';
    }
    return 0;
}

• Java

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

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) {
            int n = Integer.parseInt(br.readLine());
            String s = br.readLine();
            
            List<I