✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：魅力数字识别器

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

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

难度：中等

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

题目二：评论区平衡艺术

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

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

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

难度：中等

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

题目三：音乐盒旋律协调器

1️⃣：利用动态规划计算概率分布

2️⃣：使用快速幂计算逆元进行模运算

3️⃣：状态转移考虑相邻约束条件

难度：困难

这道题目将概率论与动态规划巧妙结合，需要理解条件概率的计算方法。通过状态转移和模运算，可以在 O(6n) 时间内求解复杂的概率计算问题，展现了算法在概率统计领域的实际应用。

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<Integer> diffPos = new ArrayList<>();
            // 找出所有不对称的位置
            for (int i = 0; i < n / 2; i++) {
                if (s.charAt(i) != s.charAt(n - 1 - i)) {
                    diffPos.add(i);
                }
            }
            
            if (diffPos.isEmpty()) {
                System.out.println(0);
                continue;
            }
            
            // 统计连续段数量
            int cnt = 1;
            for (int i = 1; i < diffPos.size(); i++) {
                if (diffPos.get(i) != diffPos.get(i-1) + 1) {
                    cnt++;
                }
            }
            
            System.out.println(cnt);
        }
    }
}

03. 音乐盒旋律协调器

问题描述

小毛是一位音乐盒设计师，他正在制作一个特殊的音乐盒。这个音乐盒由 个音符轮组成，按顺序排列在一条轨道上。每个音符轮有 6 个音符槽位，分别对应不同的音调。

第 个音符轮的 6 个槽位上的音调分别为：。

当音乐盒启动时，每个音符轮会随机旋转，最终每个轮子都会有一个音符朝上。为了确保音乐的和谐性，小毛要求相邻两个音符轮朝上的音调必须不同。

现在小毛想知道，当所有音符轮随机旋转后，能够产生和谐旋律（即相邻音符轮的音调都不相同）的概率是多少。

输入格式

第一行包含一个正整数 （），表示音符轮的数量。

接下来 行，每行包含 6 个正整数 ，表示第 个音符轮上 6 个槽位的音调编号。

输出格式

输出一个整数，表示产生和谐旋律的概率 在模 意义下的结果。

样例输入

2
1 2 3 4 5 6
1 2 3 4 5 6

样例输出

831870295

数据范围

样例	解释说明
样例1	第一个音符轮任意音调朝上（6种可能），第二个音符轮必须与第一个不同（5种选择），概率为 ，模 998244353 的结果为 831870295

题解

这道题本质上是一个概率动态规划问题。需要计算相邻音符轮旋转后音调都不相同的概率。

观察发现，每个音符轮的旋转结果只依赖于前一个音符轮的结果，这提示可以使用动态规划来解决。

状态设计：

• 用 dp[v] 表示处理完当前音符轮，且当前轮朝上音调为 时的概率
• 用 sum 记录当前音符轮满足条件的总概率

状态转移： 对于第 个音符轮，设它各音调出现次数为 cnt[v]，则：

• 该轮旋转出音调 的概率为
• 新的状态：dp_new[v] = P(v) × (sum - dp_old[v])

其中 (sum - dp_old[v]) 表示前一个音符轮不是音调 的概率。

算法步骤：

1. 第一个音符轮：直接计算各音调的概率
2. 后续音符轮：使用状态转移公式更新概率分布
3. 最终答案为所有可能音调的概率之和

模运算处理：

• 使用快速幂计算 6 的逆元
• 注意减法时要先加模数再取模，避免负数

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

参考代码

• Python

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

MOD = 998244353

def pow_mod(a, b):
    # 快速幂计算 a^b mod MOD
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

n = int(input())
inv6 = pow_mod(6, MOD - 2)  # 6的逆元

dp = {}  # 当前概率分布
total = 0  # 总概率

for i in range(n):
    line = list(map(int, input().split()))
    
    # 统计当前轮各音调出现次数
    cnt = {}
    for val in line:
        cnt[val] = cnt.get(val, 0) + 1
    
    new_dp = {}
    if i == 0:
        # 第一个音符轮
        for val, freq in cnt.items():
            new_dp[val] = freq * inv6 % MOD
    else:
        # 后续音符轮
        for val, freq in cnt.items():
            prob_v = freq * inv6 % MOD  # 转到v的概率
            prev_v = dp.get(val, 0)     # 前轮为v的概率
            valid = (total - prev_v + MOD) % MOD  # 前轮不为v的概率
            new_dp[val] = prob_v * valid % MOD
    
    # 更新状态
    dp = new_dp
    total = sum(dp.values()) % MOD

print(total)

• Cpp

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

const int MOD = 998244353;

long long pow_mod(long long a, long long b) {
    // 快速幂计算 a^b mod MOD
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    long long inv6 = pow_mod(6, MOD - 2);  // 6的逆元
    
    unordered_map<int, long long> dp;  // 当前概率分布
    long long total = 0;  // 总概率
    
    for (int i = 0; i < n; ++i) {
        unordered_map<int, int> cnt;  // 当前轮音调计数
        for (int j = 0; j < 6; ++j) {
            int val;
            cin >> val;
            cnt[val]++;
        }
        
        unordered_map<int, long long> new_dp;
        if (i == 0) {
            // 第一个音符轮
            for (auto [val, freq] : cnt) {
                new_dp[val] = freq * inv6 % MOD;
            }
        } else {
            // 后续音符轮
            for (auto [val, freq] : cnt) {
                long long prob_v = freq * inv6 % MOD;  // 转到val的概率
                long long prev_v = dp.count(val) ? dp[val] : 0;  // 前轮为val的概率
                long long valid = (total - prev_v + MOD) % MOD;  // 前轮不为val的概率
                new_dp[val] = prob_v * valid % MOD;
            }
        }
        
        // 更新状态
        dp = move(new_dp);
        total = 0;
        for (auto& [val, prob] : dp) {
            total = (total + prob) % MOD;
        }
    }
    
    cout << total << '\n';
    return 0;
}

• Java

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

public class Main {
    static final int MOD = 998244353;
    
    static long powMod(long a, long b) {
        // 快速幂计算 a^b mod MOD
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        long inv6 = powMod(6, MOD - 2);  // 6的逆元
        
        Map<Integer, Long> dp = new HashMap<>();  // 当前概率分布
        long total = 0;  // 总概率
        
        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            Map<Integer, Integer> cnt = new HashMap<>();  // 当前轮音调计数
            
            for (String s : line) {
                int val = Integer.parseInt(s);
                cnt.put(val, cnt.getOrDefault(val, 0) + 1);
            }
            
            Map<Integer, Long> newDp = new HashMap<>();
            if (i == 0) {
                // 第一个音符轮
                for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
                    int val = entry.getKey();
                    int freq = entry.getValue();
                    newDp.put(val, freq * inv6 % MOD);
                }
            } else {
                // 后续音符轮
                for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
                    int val = entry.getKey();
                    int freq = entry.getValue();
                    long probV = freq * inv6 % MOD;  // 转到val的概率
                    long prevV = dp.getOrDefault(val, 0L);  // 前轮为val的概率
                    long valid = (total - prevV + MOD) % MOD;  // 前轮不为val的概率
                    newDp.put(val, probV * valid % MOD);
                }
            }
            
            // 更新状态
            dp = newDp;
            total = 0;
            for (long prob : dp.values()) {
                total = (total + prob) % MOD;
            }
        }
        
        System.out.println(total);
    }
}