✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：小兰的宝石收藏优化

1️⃣：理解最大公约数的性质，发现乘以常数后的变化规律

2️⃣：证明选择整个区间进行增幅能够达到理论上限

3️⃣：使用数学推导得出最终答案为原数组最大公约数乘以增幅系数

难度：中等

这道题目考查对最大公约数性质的深入理解。关键洞察是无论选择哪个子区间进行增幅，最终结果都不会超过整个数组增幅后的最大公约数。通过数学分析，我们可以直接得出答案，避免了复杂的区间枚举。

题目二：小基的扑克牌组合游戏

1️⃣：理解"魔法组合"的定义：恰好两种点数，出现次数为3和2

2️⃣：统计每种点数的出现频率，转化为组合数学问题

3️⃣：枚举所有点数对，使用组合数公式计算满足条件的子序列数量

难度：中等

这道题目将扑克牌问题转化为组合数学计算。通过统计频率和枚举点数对，结合组合数公式 ，可以高效计算出所有满足条件的"魔法组合"数量，体现了组合数学在实际问题中的应用。

题目三：小毛的古董排列艺术

1️⃣：分析最大公约数在序列中的单调性和累积效应

2️⃣：理解前缀对总和的重复贡献，发现贪心策略的合理性

3️⃣：采用降序排序策略，最大化所有子数组最大公约数的总和

难度：中等偏难

这道题目结合了最大公约数理论和贪心算法思想。虽然严格证明最优性比较复杂，但通过分析最大公约数的单调性和子数组的重复贡献，降序排序能够在给定数据范围内获得最优解。

题目四：小柯的神秘数字三元组

1️⃣：深入分析复杂的数学条件，将其拆解为可处理的子情况

2️⃣：使用哈希表统计数值频率，结合前缀和优化查询

3️⃣：运用容斥原理避免重复计数，精确计算满足条件的三元组数量

难度：困难

这道题目涉及复杂的数学条件分析和高效的数据结构运用。通过将条件拆分为互斥情况，结合前缀和技术和容斥原理，能够在合理时间内处理大规模数据。体现了算法设计中的分治思想和数学建模能力。

01. 小兰的宝石收藏优化

问题描述

小兰是一位珠宝收藏家，她拥有 颗珍贵的宝石，每颗宝石都有一个特定的能量值。小兰发现，当多颗宝石放在一起时，它们会产生共鸣，这种共鸣的强度等于所有宝石能量值的最大公约数。

为了提升宝石收藏的整体价值，小兰可以对其中一段连续的宝石进行能量增幅处理，将这段区间内所有宝石的能量值都乘以一个固定的增幅系数 。她最多只能进行一次这样的操作。

现在小兰想知道，经过最优的能量增幅操作后，整个宝石收藏的共鸣强度（即所有宝石能量值的最大公约数）最大能达到多少。

输入格式

每个测试文件包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：

第一行输入两个正整数 ，分别代表宝石的数量和能量增幅系数。

第二行输入 个整数 ，表示每颗宝石的初始能量值。

除此之外，保证单个测试文件的 之和不超过 。

输出格式

对于每一组测试数据，新起一行，输出一个整数，表示操作结束后，宝石收藏的最大共鸣强度。

样例输入

2
5 3
1 1 3 6 9
3 1
1 2 3

样例输出

3
1

数据范围

• 
• 
• 
• 
• 单个测试文件的 之和不超过

样例编号	解释说明
样例1	选择区间 进行增幅，数组变为 ，最大公约数为
样例2	无论选择哪个区间进行增幅，数组的最大公约数都保持为

题解

这道题乍一看可能会想要枚举所有可能的区间，但仔细分析后会发现有更简单的规律。

首先我们要理解最大公约数的性质。如果我们对整个数组的所有元素都乘以 ，那么新数组的最大公约数就是原数组最大公约数的 倍。

关键观察是：无论我们选择哪个子区间进行增幅操作，最终的最大公约数都不会超过 。

为什么呢？考虑任意一个区间 ：

• 设原数组的最大公约数为
• 设区间内元素的最大公约数为 ，区间外元素的最大公约数为
• 操作后的最大公约数为

由于 和 都能被 整除，所以 也能被 整除，且不会超过 。

而当我们选择整个数组作为增幅区间时，就能恰好达到 这个上界。

因此答案就是原数组最大公约数乘以 。

算法步骤很简单：

1. 计算原数组所有元素的最大公约数
2. 输出

时间复杂度为 ，只需要一次遍历计算最大公约数。

参考代码

Python

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

from math import gcd

def solve():
    # 读取宝石数量和增幅系数
    n, k = map(int, input().split())
    # 读取宝石能量值
    gems = list(map(int, input().split()))
    
    # 计算所有宝石能量值的最大公约数
    g = 0
    for val in gems:
        g = gcd(g, val)
    
    # 输出最大共鸣强度
    print(g * k)

# 处理多组测试数据
T = int(input())
for _ in range(T):
    solve()

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        ll k;
        cin >> n >> k;
        
        // 计算所有宝石能量值的最大公约数
        ll g = 0;
        for (int i = 0; i < n; i++) {
            ll val;
            cin >> val;
            g = __gcd(g, val);  // 累积计算最大公约数
        }
        
        // 输出最大共鸣强度
        cout << g * k << "\n";
    }
    
    return 0;
}

Java

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

public class Main {
    // 计算两个数的最大公约数
    private static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    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 k = Long.parseLong(line1[1]);
            
            String[] line2 = br.readLine().split(" ");
            
            // 计算所有宝石能量值的最大公约数
            long g = 0;
            for (int i = 0; i < n; i++) {
                long val = Long.parseLong(line2[i]);
                g = gcd(g, val);  // 累积计算最大公约数
            }
            
            // 输出最大共鸣强度
            System.out.println(g * k);
        }
        
        br.close();
    }
}

02. 小基的扑克牌组合游戏

问题描述

小基是一位扑克牌高手，她正在研究一种特殊的牌型组合。在她的游戏规则中，一个"魔法组合"必须恰好包含 张牌，且满足以下条件：这 张牌中恰好有两种不同的点数，其中一种点数出现 次，另一种点数出现 次。

例如，牌组 就是一个魔法组合，因为它包含了点数 （出现3次）和点数 （出现2次）。而牌组 和 都不是魔法组合。

现在小基手中有一副特殊的牌，她想知道从这副牌中能选出多少种不同的魔法组合。需要注意的是，这里说的是子序列，即可以从原牌组中任意选择位置的牌来组成新的组合，不要求连续。

输入格式

第一行输入一个正整数 ，代表牌组的大小。

第二行输入 个正整数 ，代表每张牌的点数。

输出格式

输出一个整数，代表能组成的魔法组合数量。

样例输入

6
1 1 4 5 1 4

6
1 1 4 4 4 1

样例输出

1

6

数据范围

题解

这道题要求我们统计满足特定条件的5元素子序列数量。关键是理解什么是"魔法组合"：恰好包含两种不同的点数，一种出现3次，另一种出现2次。

首先统计每种点数的出现次数。设某个点数 在原数组中出现了 次。

要形成一个魔法组合，我们需要：

1. 选择两种不同的点数 和
2. 从点数 中选择3张牌，从点数 中选择2张牌，或者反过来

对于两种不同的点数 和 ，能形成的魔法组合数量为：

• 出现3次， 出现2次：
• 出现2次， 出现3次：

其中 表示从 个元素中选择 个的组合数，当 时值为0。

算法步骤：

1. 统计每种点数的出现次数
2. 枚举所有不同的点数对
3. 对每对点数，计算能形成的魔法组合数并累加到答案中

时间复杂度为 ，其中 是不同点数的个数，最坏情况下 。

参考代码

Python

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

def comb(n, k):
    """计算组合数C(n,k)"""
    if n < k:
        return 0
    if k == 2:
        return n * (n - 1) // 2
    if k == 3:
        return n * (n - 1) * (n - 2) // 6
    return 0

def solve():
    n = int(input())
    cards = list(map(int, input().split()))
    
    # 统计每种点数的出现次数
    cnt = {}
    for card in cards:
        cnt[card] = cnt.get(card, 0) + 1
    
    # 将出现次数提取到列表中
    freq = list(cnt.values())
    m = len(freq)
    
    ans = 0
    # 枚举所有不同的点数对
    for i in range(m):
        for j in range(i + 1, m):
            ci, cj = freq[i], freq[j]
            # i点数出现3次，j点数出现2次
            ans += comb(ci, 3) * comb(cj, 2)
            # i点数出现2次，j点数出现3次
            ans += comb(ci, 2) * comb(cj, 3)
    
    print(ans)

solve()

C++

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

// 计算组合数C(n,k)
ll comb(ll n, int k) {
    if (n < k) return 0;
    if (k == 2) return n * (n - 1) / 2;
    if (k == 3) return n * (n - 1) * (n - 2) / 6;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 统计每种点数的出现次数
    unordered_map<int, ll> cnt;
    for (int i = 0; i < n; i++) {
        int card;
        cin >> card;
        cnt[card]++;
    }
    
    // 将出现次数提取到向量中
    vector<ll> freq;
    for (auto& p : cnt) {
        freq.push_back(p.second);
    }
    
    int m = freq.size();
    ll ans = 0;
    
    // 枚举所有不同的点数对
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            ll ci = freq[i], cj = freq[j];
            // i点数出现3次，j点数出现2次
            ans += comb(ci, 3) * comb(cj, 2);
            // i点数出现2次，j点数出现3次
            ans += comb(ci, 2) * comb(cj, 3);
        }
    }