✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

美团

题目一：小毛的魔法药剂配制

1️⃣：枚举所有可能的材料分配方式到三种系数

2️⃣：计算每种分配下的魔法效力公式值并取模

3️⃣：返回模意义下的最大魔法效力

难度：中等

这道题目的关键在于理解魔法药剂配制的分配规则。由于恰好有 3 种材料和 3 个系数，每种材料必须分配到一个系数位置，因此总共有 3! = 6 种分配方式。通过枚举所有排列并计算模值，我们可以找到最优的材料分配策略。

题目二：小兰的智能导航优化

1️⃣：分析同号和异号坐标的最优移动策略

2️⃣：计算同步移动和交叉移动的有效成本

3️⃣：用贪心策略处理公共距离，剩余距离用精准移动

难度：中等

这道题目结合了贪心算法和策略选择，需要理解不同移动模式的效率比较。通过分析坐标的符号关系，我们可以选择最优的移动组合，实现最小能耗的导航路径。

题目三：小基的密码学研究

1️⃣：质因数分解并独立处理每个质因子

2️⃣：动态规划计算单个质因子的构造方案数

3️⃣：矩阵快速幂优化大数据范围的递推计算

难度：难

这道题目需要深入理解最小公倍数的性质，并结合质因数分解、动态规划和矩阵快速幂等高级算法技巧。通过将复杂问题分解为独立的子问题，我们可以高效地处理大数据范围的序列计数问题。

01. 小毛的魔法药剂配制

问题描述

小毛是一位著名的魔法师，他正在研制一种新型的魔法药剂。这个药剂的效果取决于三种神秘成分的配比：催化剂系数 、增强剂系数 和稳定剂系数 。

小毛有 种魔法材料，每种材料都有一个魔法值 。为了配制药剂，他需要将这些材料分别投入到催化剂、增强剂和稳定剂三个容器中，但有以下限制：

• 每种材料必须投入到恰好一个容器中
• 每个容器必须至少投入一种材料
• 最终药剂的魔法效力公式为：

其中 、、 分别是投入对应容器的所有材料魔法值之和。

现在有 个客人想要购买药剂，每个客人都有自己的魔法亲和度 。由于魔法的特殊性，最终的魔法效力需要对一个神秘常数 取模。小毛希望知道，对于每个客人，他能获得的最大魔法效力值是多少？

输入格式

第一行包含三个正整数 ，分别表示魔法材料数量、神秘常数和客人数量。

第二行包含 个正整数 ，表示每种魔法材料的魔法值。

第三行包含 个非负整数 ，表示每个客人的魔法亲和度。

输出格式

对于每个客人，输出一行，包含一个整数，表示该客人能获得的最大魔法效力值（对 取模后的结果）。

样例输入

3 4 2
1 2 5
2 0

样例输出

3
2

数据范围

• 
• 
• 
• 
• 

样例	解释说明
样例1	对于客人1（魔法亲和度为2）：最优分配是将材料分别分配为 ，得到 ，对4取模得3
样例1	对于客人2（魔法亲和度为0）：最优分配是将材料分配为 ，得到 ，对4取模得1。但还有其他分配方案能得到2

题解

这道题的关键在于理解题目的本质：我们有3种材料和3个系数位置，需要找到最优的分配方案。

由于材料数量恰好为3，且每个系数位置必须至少分配一种材料，所以每种材料恰好分配给一个系数。这样总共有 种分配方式。

算法思路：

1. 枚举所有排列：对于3种材料，我们可以枚举所有 种分配到 、、 的方法
2. 计算函数值：对每种分配方案，计算 的值
3. 取模并比较：将结果对 取模，取所有方案中的最大值

具体实现时，需要注意：

• 由于 可能很大，需要先对 取模再计算 ，避免溢出
• 每个系数也需要对 取模
• 最终结果要对 取模

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

参考代码

Python

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

n, m, q = map(int, input().split())
magic_vals = list(map(int, input().split()))
queries = list(map(int, input().split()))

for x in queries:
    max_effect = 0
    # 计算 x^2 mod m，避免后续溢出
    x_mod = x % m
    x2_mod = (x_mod * x_mod) % m
    
    # 枚举所有3种材料的排列方式
    for perm in permutations(magic_vals):
        a, b, c = perm
        # 计算魔法效力并取模
        effect = (a % m * x2_mod + b % m * x_mod + c % m) % m
        max_effect = max(max_effect, effect)
    
    print(max_effect)

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, q;
    cin >> n >> m >> q;
    
    vector<long long> vals(n);
    for (int i = 0; i < n; i++) {
        cin >> vals[i];
    }
    
    for (int i = 0; i < q; i++) {
        long long x;
        cin >> x;
        
        long long x_mod = x % m;
        long long x2_mod = (x_mod * x_mod) % m;
        
        int max_effect = 0;
        vector<int> idx = {0, 1, 2};
        
        // 枚举所有排列
        do {
            long long a = vals[idx[0]] % m;
            long long b = vals[idx[1]] % m;
            long long c = vals[idx[2]] % m;
            
            long long effect = (a * x2_mod + b * x_mod + c) % m;
            max_effect = max(max_effect, (int)effect);
        } while (next_permutation(idx.begin(), idx.end()));
        
        cout << max_effect << '\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));
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int m = Integer.parseInt(firstLine[1]);
        int q = Integer.parseInt(firstLine[2]);
        
        String[] valStrs = br.readLine().split(" ");
        long[] magicVals = new long[n];
        for (int i = 0; i < n; i++) {
            magicVals[i] = Long.parseLong(valStrs[i]);
        }
        
        String[] queryStrs = br.readLine().split(" ");
        long[] queries = new long[q];
        for (int i = 0; i < q; i++) {
            queries[i] = Long.parseLong(queryStrs[i]);
        }
        
        StringBuilder result = new StringBuilder();
        
        for (int i = 0; i < q; i++) {
            long x = queries[i];
            long xMod = x % m;
            long x2Mod = (xMod * xMod) % m;
            
            int maxEff = 0;
            // 枚举所有排列
            int[] indices = {0, 1, 2};
            
            do {
                long coeffA = magicVals[indices[0]] % m;
                long coeffB = magicVals[indices[1]] % m;
                long coeffC = magicVals[indices[2]] % m;
                
                long effect = (coeffA * x2Mod + coeffB * xMod + coeffC) % m;
                maxEff = Math.max(maxEff, (int)effect);
            } while (nextPerm(indices));
            
            result.append(maxEff).append('\n');
        }
        
        System.out.print(result.toString());
    }
    
    // 生成下一个排列的辅助函数
    private static boolean nextPerm(int[] arr) {
        int i = arr.length - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) {
            i--;
        }
        if (i < 0) return false;
        
        int j = arr.length - 1;
        while (arr[j] <= arr[i]) {
            j--;
        }
        
        // 交换
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        
        // 反转后缀
        reverse(arr, i + 1, arr.length - 1);
        return true;
    }
    
    private static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }
}

02. 小兰的智能导航优化

问题描述

小兰正在开发一款智能导航系统。该系统能够控制无人车在二维平面上移动，目标是从任意起始位置 移动到原点 。

导航系统提供了三种移动模式，每种模式都有对应的能耗成本：

• 精准移动：消耗 单位能量，可以将 坐标或 坐标中的任意一个增加或减少
• 同步移动：消耗 单位能量，可以同时将 和 坐标都增加 ，或者都减少
• 交叉移动：消耗 单位能量，可以将坐标变为 或

小兰需要为不同的起始位置计算最小能耗路径。请你帮助她设计算法，计算从给定起始位置到原点的最小总能耗。

注意：移动过程中坐标可以为负数，操作次数不限。

输入格式

每个测试文件包含多组测试数据。

第一行包含一个正整数 ，表示测试数据的组数。

接下来 行，每行包含五个整数 ，分别表示起始位置的坐标和三种移动模式的能耗成本。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示从起始位置到原点的最小总能耗。

样例输入

2
3 3 5 3 100
4 -1 2 7 3

样例输出

9
9

数据范围

• 
• 
• 

样例	解释说明
样例1	起始位置：使用3次同步移动到达原点，能耗为
样例2	起始位置：先用1次交叉移动变为，能耗3；再用3次精准移动处理坐标，能耗，总能耗

题解

这道题需要分析不同移动策略的效率，并根据起始坐标的特点选择最优方案。

关键观察：

1. 精准移动：单独处理一个坐标，每次移动1个单位，成本为
2. 同步移动：相当于两次精准移动的组合，但成本为。只有当时才更有效率
3. 交叉移动：也相当于两次精准移动，但处理的是异号坐标，成本为。只有当时才更有效率

算法思路：

1. 计算有效单价：

   • 同向移动的有效成本：
   • 反向移动的有效成本：

2. 根据坐标符号选择策略：

   • 如果 和 同号（包括其中一个为0）：可以使用同步移动处理公共部分
   • 如果 和 异号：可以使用交叉移动处理公共部分

3. 贪心处理：

   • 设，
   • 先处理公共部分：
   • 剩余部分： 只能用精准移动处理

时间复杂度： 每组测试数据。

参考代码

Python

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

t = int(input())
for _ in range(t):
    x, y, a, b, c = map(int, input().split())
    
    # 计算绝对值
    abs_x = abs(x)
    abs_y = abs(y)
    
    total_cost = 0
    
    # 判断坐标符号关系
    if (x >= 0) == (y >= 0):  # 同号（包括0）
        # 可以使用同步移动
        common_dist = min(abs_x, abs_y)
        cost_sync = min(b, 2 * a)  # 同步移动的有效单价
        total_cost += common_dist * cost_sync
        abs_x -= common_dist
        abs_y -= common_dist
    else:  # 异号
        # 可以使用交叉移动
        common_dist = min(abs_x, abs_y)
        cost_cross = min(c, 2 * a)  # 交叉移动的有效单价
        total_cost += common_dist * cost_cross
        abs_x -= common_dist
        abs_y -= common_dist
    
    # 处理剩余距离（只能用精准移动）
    total_cost += (abs_x + abs_y) * a
    
    print(total_cost)

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--) {
        ll x, y, a, b, c;
        cin >> x >> y >> a >> b >> c;
        
        ll absX = abs(x);
        ll absY = abs(y);
        
        ll totalCost = 0;
        
        // 检查坐标符号关系
        if ((x >= 0) == (y >= 0)) {
            // 同号情况：使用同步移动
            ll commonDist = min(absX, absY);
            ll syncCost = min(b, 2 * a);
            totalCost += commonDist * syncCost;
            absX -= commonDist;
            absY -= commonDist;
        } else {
            // 异号情况：使用交叉移动
            ll commonDist = min(absX, absY);
            ll crossCost = min(c, 2 * a);
            totalCost += commonDist * crossCost;
            absX -= commonDist;
            absY -= commonDist;
        }
        
        // 剩余距离用精准移动
        totalCost += (absX + absY) * a;
        
        cout << totalCost << '\n';
    }
    
    return 0;
}

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(reader.readLine());
        
        StringBuilder result = new StringBuilder();
        
        while (testCases-- > 0) {
            String[] parts = reader.readLine().split(" ");
            long x = Long.parseLong(parts[0]);
            long y = Long.parseLong(parts[1]);
            long a = Long.parseLong(parts[2]);
            long b = Long.parseLong(parts[3]);
            long c = Long.parseLong(parts[4]);
            
            long absX = Math.abs(x);
            long absY = Math.abs(y);
            
            long totalCost = 0;