✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：小兰的魔法卡牌配对

1️⃣：统计每种余数的出现次数，利用模运算性质简化配对判断

2️⃣：分别处理余数为0、互补余数对和特殊情况（m为偶数时的m/2）

难度：中等

这道题目的关键在于理解模运算的性质，将原问题转化为余数配对问题。通过数学推导，避免了暴力枚举所有商品对的 O(n²) 复杂度，实现了 O(n+m) 的高效解法。

题目二：小基的智能农场管理

1️⃣：计算每台机器的总营养液消耗量

2️⃣：使用贪心策略按消耗量升序排序

3️⃣：依次选择消耗最小的机器直到预算耗尽

难度：中等

这道题目是典型的贪心选择问题，关键在于正确计算每台机器的总消耗并证明贪心策略的正确性。通过排序优化，将选择问题转化为简单的累加判断。

题目三：小毛的探险路线规划

1️⃣：利用答案的单调性进行二分查找

2️⃣：设计判定函数检查给定危险等级上限是否可行

3️⃣：在连续合法区间内使用贪心策略判断是否满足积分要求

难度：中等偏难

这道题目结合了二分查找和贪心算法，需要理解问题的单调性质并设计高效的判定函数。通过将连续区间问题转化为分段贪心判断，实现了 O(N log D) 的时间复杂度。

题目四：小柯的花园景观设计

1️⃣：使用前缀和技术检测问题区域

2️⃣：维护当前区域内的前缀和集合

3️⃣：遇到冲突时立即分割区域，确保不存在禁止的总和

难度：中等偏难

这道题目需要理解前缀和的性质，并设计巧妙的分段策略来解决约束问题。通过哈希集合维护状态和及时重置，确保算法的正确性和效率。

01. 小兰的魔法卡牌配对

问题描述

小兰是一位热爱收集魔法卡牌的法师。她的卡牌收藏室里有 张不同的魔法卡牌，每张卡牌都有一个独特的魔法值 。

最近，小兰发现了一个古老的魔法配对仪式。根据这个仪式的规则，如果能找到两张卡牌，使得它们的魔法值之和恰好是魔法数 的倍数，那么这两张卡牌就能组成一个强大的魔法组合，释放出惊人的力量。

由于魔法仪式的限制，小兰每次最多只能选择两张卡牌进行配对。她想知道，在她的收藏中，总共有多少种不同的方式可以选择两张卡牌组成有效的魔法组合？

输入格式

第一行包含两个正整数 和 ，分别表示魔法卡牌的数量和魔法数。

第二行包含 个正整数 ，表示每张卡牌的魔法值。

输出格式

输出一个整数，表示小兰能够选择的有效魔法组合的数量。

最终结果对 取模。

样例输入

2 4
1 3

5 2
1 2 3 4 5

样例输出

1

4

样例	解释说明
样例1	小兰有1种方式组成魔法组合：第1张卡牌（魔法值1）和第2张卡牌（魔法值3），它们的和4是魔法数4的倍数
样例2	小兰有4种方式组成魔法组合：(1,3)、(2,4)、(1,5)、(3,5)，它们的和都是魔法数2的倍数

数据范围

• 
• 
• 

题解

这道题的核心思想是利用模运算的性质来简化问题。

当我们要判断两个数的和是否是 的倍数时，实际上只需要看这两个数分别对 取模后的结果。如果两个数对 的余数相加等于 （或者0），那么原来两个数的和就是 的倍数。

具体分析过程：

1. 将每张卡牌的魔法值按 取模，统计每种余数出现的次数
2. 对于余数为0的卡牌，它们只能和其他余数为0的卡牌配对，组合数为
3. 对于余数为 的卡牌，它们需要和余数为 的卡牌配对
4. 特殊情况：当 为偶数时，余数为 的卡牌只能和其他余数为 的卡牌配对

这种方法避免了枚举所有卡牌对的暴力解法，时间复杂度从 优化到了 。

算法步骤：

1. 用数组 cnt 统计每种余数的出现次数
2. 计算余数为0的卡牌能组成的组合数
3. 遍历余数1到 ，计算互补余数对的组合数
4. 如果 是偶数，单独处理余数为 的情况

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

参考代码

Python

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

MOD = 998244353

# 读取输入数据
n, m = map(int, input().split())
vals = list(map(int, input().split()))

# 统计每种余数的出现次数
freq = [0] * m
for val in vals:
    freq[val % m] += 1

# 计算组合数C(x,2) = x*(x-1)/2
def calc_pairs(x):
    return x * (x - 1) // 2 % MOD

result = 0

# 余数为0的情况：只能自己配对
result = (result + calc_pairs(freq[0])) % MOD

# 互补余数配对：r 和 (m-r)
for r in range(1, (m + 1) // 2):
    result = (result + freq[r] * freq[m - r]) % MOD

# 特殊情况：m为偶数时，余数为m/2的只能自己配对
if m % 2 == 0:
    result = (result + calc_pairs(freq[m // 2])) % MOD

print(result)

Cpp

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

const long long MOD = 998244353LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    // 统计每种余数的出现次数
    vector<long long> freq(m, 0);
    for (int i = 0; i < n; ++i) {
        long long val;
        cin >> val;
        ++freq[val % m];
    }
    
    // 计算组合数C(x,2)的函数
    auto calc_pairs = [](long long x) -> long long {
        return x * (x - 1) / 2 % MOD;
    };
    
    long long result = 0;
    
    // 余数为0的情况
    result = (result + calc_pairs(freq[0])) % MOD;
    
    // 互补余数配对
    for (int r = 1; r * 2 < m; ++r) {
        result = (result + freq[r] * freq[m - r]) % MOD;
    }
    
    // m为偶数时的特殊情况
    if (m % 2 == 0) {
        result = (result + calc_pairs(freq[m / 2])) % MOD;
    }
    
    cout << result << '\n';
    return 0;
}

Java

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

public class Main {
    private static final long MOD = 998244353L;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        // 统计每种余数的出现次数
        long[] freq = new long[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            long val = Long.parseLong(st.nextToken());
            freq[(int)(val % m)]++;
        }
        
        long result = 0;
        
        // 余数为0的情况
        result = (result + calcPairs(freq[0])) % MOD;
        
        // 互补余数配对
        for (int r = 1; r * 2 < m; r++) {
            result = (result + freq[r] * freq[m - r]) % MOD;
        }
        
        // m为偶数时的特殊情况
        if (m % 2 == 0) {
            result = (result + calcPairs(freq[m / 2])) % MOD;
        }
        
        System.out.println(result);
    }
    
    // 计算组合数C(x,2)
    private static long calcPairs(long x) {
        return x * (x - 1) / 2 % MOD;
    }
}

02. 小基的智能农场管理

问题描述

小基拥有一座现代化的智能农场，农场配备了先进的自动化种植系统。农场的中央仓库目前储存着 单位的特殊营养液。

从明天开始的 天里，每天都会有一台新的自动种植机器被激活。这些机器有着不同的工作效率：如果第 天激活的机器被允许工作，那么从第 天开始直到第 天结束，每天都需要消耗 单位的营养液来维持正常运转。

小基希望农场里工作的机器越多越好，这样能够提高农场的整体产量。但是，她必须确保每台被激活的机器在其整个工作周期内都能获得足够的营养液供应，绝不能出现营养液短缺的情况。

小基可以选择拒绝激活任何一台机器。被拒绝的机器将不会启动，也不会消耗任何营养液。

请问，在第 天结束时，小基的农场最多能有多少台机器正常工作？

输入格式

第一行包含两个正整数 和 ，分别表示总天数和中央仓库的初始营养液储量。

第二行包含 个正整数 ，其中 表示第 天激活的机器每天需要的营养液消耗量。

输出格式

输出一个整数，表示在保证所有工作机器都能获得充足营养液的前提下，农场最多能同时工作的机器数量。

样例输入

3 8
2 2 2

3 12
2 2 2

样例输出

2

3

样例	解释说明
样例1	可以激活第2、3天的机器。第2天机器工作2天消耗4单位，第3天机器工作1天消耗2单位，总计6单位 ≤ 8单位
样例2	可以激活所有3台机器。第1天机器工作3天消耗6单位，第2天机器工作2天消耗4单位，第3天机器工作1天消耗2单位，总计12单位 = 12单位

数据范围

• 
• 
• 

题解

这是一个经典的贪心选择问题。关键观察是：每台机器的总消耗是固定的，我们需要在有限的资源下选择尽可能多的机器。

首先分析每台机器的总消耗：第 台机器如果被激活，会从第 天工作到第 天，总共工作 天，总消耗为 。

问题转化为：在所有机器中选择尽可能多的机器，使得它们的总消耗不超过 。这是一个典型的"在预算限制下最多能买几件物品"的问题。

贪心策略很明显：总是优先选择总消耗最小的机器。证明如下：假设存在最优解没有选择某个消耗较小的机器A，但选择了消耗较大的机器B，那么我们可以用A替换B，得到一个更优的解（或至少同样好的解）。

算法步骤：

1. 计算每台机器的总消耗
2. 将所有机器按总消耗从小到大排序
3. 依次选择机器，直到总消耗超过预算为止

时间复杂度主要由排序决定，为 。空间复杂度为 。

参考代码

Python

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

# 读取输入数据
n, budget = map(int, input().split())
daily_cost = list(map(int, input().split()))

# 计算每台机器的总消耗
total_costs = []
for i in range(n):
    work_days = n - i  # 工作天数（从第i+1天到第n天）
    total_cost = daily_cost[i] * work_days
    total_costs.append(total_cost)

# 按总消耗升序排序
total_costs.sort()

# 贪心选择机器
machines = 0
used_budget = 0
for cost in total_costs:
    if used_budget + cost <= budget:
        used_budget += cost
        machines += 1
    else:
        break

print(machines)

Cpp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    ll budget;
    cin >> n >> budget;
    
    vector<ll> daily_cost(n);
    for (int i = 0; i < n; ++i) {
        cin >> daily_cost[i];
    }
    
    // 计算每台机器的总消耗
    vector<ll> total_costs(n);
    for (int i = 0; i < n; ++i) {
        ll work_days = n - i;  // 工作天数
        total_costs[i] = daily_cost[i] * work_days;
    }
    
    // 按总消耗升序排序
    sort(total_costs.begin(), total_costs.end());
    
    // 贪心选择机器
    int machines = 0;
    ll used_budget = 0;
    for (auto cost : total_costs) {
        if (used_budget + cost <= budget) {
            used_budget += cost;
            ++machines;
        } else {
            break;
        }
    }
    
    cout << machines << '\n';
    return 0;
}

Java

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

public class M