✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：厨艺大师的配菜比赛

1️⃣：枚举所有可能的三份食材组合，检查总和是否为10的倍数

2️⃣：计算最优策略，使剩余两份食材的比较值最大

3️⃣：根据比赛规则分情况讨论并确定获胜者

难度：简单

这道题目的关键在于理解配菜比赛的评判规则，通过枚举所有可能的食材组合来寻找最优策略。由于数据规模很小，可以直接暴力枚举所有C(5,3)=10种组合，实现简洁高效的解法。

题目二：武术训练场的修炼计划

1️⃣：设计状态表示每轮训练后的最大功力提升

2️⃣：考虑防御训练对下一轮攻击的增强效果

3️⃣：使用动态规划优化训练序列安排

难度：中等

这道题目是典型的动态规划问题，需要理解防御训练的延迟收益机制。通过设计两个状态来记录上一轮的训练方式，实现O(n)时间复杂度的最优解，体现了状态设计的重要性。

题目三：知识传播网络的扩散方案

1️⃣：理解知识传播的约束条件，转化为树的拓扑序问题

2️⃣：使用经典组合数学公式计算方案数量

3️⃣：预处理阶乘和逆元，高效计算大数取模

难度：困难

这道题目结合了树形结构和组合数学知识，需要深入理解拓扑序的本质。通过数学推导得出优雅的公式解，展现了将复杂问题转化为数学计算的能力，是算法竞赛中的经典题型。

01. 厨艺大师的配菜比赛

问题描述

小兰和小柯正在参加一场厨艺配菜比赛。比赛规则如下：每位参赛者需要从给定的食材中选择配菜组合。

比赛中有 种不同的食材，编号为 到 ，每种食材都有 份。比赛开始时，小兰和小柯各自获得了 份不同的食材。

比赛的评判规则如下：

• 如果两位参赛者都无法从各自的 份食材中选出 份，使得它们的营养价值总和为 的倍数，则比较各自食材中营养价值最高的那一份，数值较大者获胜；如果最大营养价值相同，则平局

• 如果只有一位参赛者能选出这样的 份食材组合，则该参赛者直接获胜

• 如果两位参赛者都能选出符合条件的 份食材组合，则各自选择一种最优方案，使得剩余 份食材的营养价值总和为 时，比较 的大小（即将 中的 视作 ），数值较大者获胜；如果两个数值相同，则平局

现在给出两位参赛者的食材配置，请判断每场比赛的结果。

输入格式

第一行包含一个正整数 （），表示比赛场次数量。

接下来每场比赛的输入格式如下：

• 第一行包含 个正整数 （），表示小兰的食材营养价值

• 第二行包含 个正整数 （），表示小柯的食材营养价值

保证输入合法：同一种营养价值的食材在两人配置中的总数量不超过 。

输出格式

对于每场比赛，输出一行结果：

• 如果小兰获胜，输出 Tk

• 如果小柯获胜，输出 wida

• 如果平局，输出 emm

样例输入

3
10 1 9 2 3
6 6 6 6 1
6 6 6 6 1
10 1 9 2 3
3 3 3 1 1
3 2 2 1 1

样例输出

Tk
wida
emm

数据范围

• 
• 
• 同一营养价值的食材总数不超过

题解

这道题的核心是理解配菜比赛的评判规则，需要分情况讨论并找到最优策略。

首先明确三种情况的处理优先级：

1. 能选出营养价值总和为10倍数的3份食材组合的参赛者有优势
2. 如果都能或都不能选出，则需要进一步比较

算法步骤：

1. 检查是否存在和为10倍数的三份食材组合：枚举所有可能的3份食材组合（共C(5,3)=10种），检查总和是否为10的倍数
2. 计算最优策略：如果存在多种符合条件的组合，选择使剩余2份食材总和的比较值最大的方案
3. 比较结果：根据规则进行最终比较

关键技巧：

• 使用三重循环枚举所有可能的3份食材组合
• 对于剩余2份食材总和x，比较值计算公式为：((x-1) mod 10) + 1
• 分情况讨论：都不能选出、只有一方能选出、两方都能选出

由于数据规模很小（每次只有5份食材），直接暴力枚举所有组合即可，时间复杂度为O(1)。

参考代码

• Python

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

def calc_score(x):
    # 计算比较值：((x-1) mod 10) + 1，将0映射为10
    return ((x - 1) % 10) + 1

def solve_player(foods):
    max_food = max(foods)  # 最大营养价值
    best_score = -1
    can_make = False
    
    # 枚举所有3份食材组合
    for i in range(5):
        for j in range(i + 1, 5):
            for k in range(j + 1, 5):
                sum_three = foods[i] + foods[j] + foods[k]
                if sum_three % 10 == 0:  # 能被10整除
                    can_make = True
                    # 计算剩余2份的总和
                    remain = []
                    for idx in range(5):
                        if idx != i and idx != j and idx != k:
                            remain.append(foods[idx])
                    
                    remain_sum = sum(remain)
                    score = calc_score(remain_sum)
                    best_score = max(best_score, score)
    
    return can_make, best_score, max_food

t = int(input())
for _ in range(t):
    tk_foods = list(map(int, input().split()))
    wida_foods = list(map(int, input().split()))
    
    tk_can, tk_score, tk_max = solve_player(tk_foods)
    wida_can, wida_score, wida_max = solve_player(wida_foods)
    
    # 根据规则判断结果
    if not tk_can and not wida_can:
        # 都不能选出，比较最大值
        if tk_max > wida_max:
            print("Tk")
        elif tk_max < wida_max:
            print("wida")
        else:
            print("emm")
    elif tk_can and not wida_can:
        print("Tk")
    elif not tk_can and wida_can:
        print("wida")
    else:
        # 都能选出，比较得分
        if tk_score > wida_score:
            print("Tk")
        elif tk_score < wida_score:
            print("wida")
        else:
            print("emm")

• Cpp

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

struct Result {
    bool can_make;    // 是否能选出和为10倍数的组合
    int best_score;   // 最优得分
    int max_val;      // 最大营养价值
};

int calc_score(int x) {
    // 计算比较值
    return ((x - 1) % 10 + 10) % 10 + 1;
}

Result solve_player(vector<int>& foods) {
    Result res;
    res.can_make = false;
    res.best_score = -1;
    res.max_val = *max_element(foods.begin(), foods.end());
    
    // 枚举所有三份食材组合
    for (int i = 0; i < 5; i++) {
        for (int j = i + 1; j < 5; j++) {
            for (int k = j + 1; k < 5; k++) {
                int sum_val = foods[i] + foods[j] + foods[k];
                if (sum_val % 10 == 0) {
                    res.can_make = true;
                    
                    // 找剩余两个位置
                    vector<int> remain_idx;
                    for (int t = 0; t < 5; t++) {
                        if (t != i && t != j && t != k) {
                            remain_idx.push_back(t);
                        }
                    }
                    
                    int remain_sum = foods[remain_idx[0]] + foods[remain_idx[1]];
                    int score = calc_score(remain_sum);
                    res.best_score = max(res.best_score, score);
                }
            }
        }
    }
    
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        vector<int> tk_foods(5), wida_foods(5);
        
        for (int i = 0; i < 5; i++) cin >> tk_foods[i];
        for (int i = 0; i < 5; i++) cin >> wida_foods[i];
        
        Result tk_res = solve_player(tk_foods);
        Result wida_res = solve_player(wida_foods);
        
        string ans;
        if (!tk_res.can_make && !wida_res.can_make) {
            // 都不能选出，比较最大值
            if (tk_res.max_val > wida_res.max_val) ans = "Tk";
            else if (tk_res.max_val < wida_res.max_val) ans = "wida";
            else ans = "emm";
        } else if (tk_res.can_make && !wida_res.can_make) {
            ans = "Tk";
        } else if (!tk_res.can_make && wida_res.can_make) {
            ans = "wida";
        } else {
            // 都能选出，比较得分
            if (tk_res.best_score > wida_res.best_score) ans = "Tk";
            else if (tk_res.best_score < wida_res.best_score) ans = "wida";
            else ans = "emm";
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}

• Java

import java.util.*;

public class Main {
    static class GameResult {
        boolean canMake;     // 是否能选出符合条件的组合
        int bestScore;       // 最优得分
        int maxValue;        // 最大营养价值
        
        GameResult(boolean can, int score, int max) {
            canMake = can;
            bestScore = score;
            maxValue = max;
        }
    }
    
    static int calcScore(int x) {
        // 计算比较值：((x-1) mod 10) + 1
        return ((x - 1) % 10 + 10) % 10 + 1;
    }
    
    static GameResult solvePlayer(int[] foods) {
        boolean canMake = false;
        int bestScore = -1;
        int maxValue = Arrays.stream(foods).max().orElse(0);
        
        // 枚举所有三份食材组合
        for (int i = 0; i < 5; i++) {
            for (int j = i + 1; j < 5; j++) {
                for (int k = j + 1; k < 5; k++) {
                    int sumThree = foods[i] + foods[j] + foods[k];
                    if (sumThree % 10 == 0) {
                        canMake = true;
                        
                        // 计算剩余两份的总和
                        List<Integer> remainIdx = new ArrayList<>();
                        for (int t = 0; t < 5; t++) {
                            if (t != i && t != j && t != k) {
                                remainIdx.add(t);
                            }
                        }
                        
                        int remainSum = foods[remainIdx.get(0)] + foods[remainIdx.get(1)];
                        int score = calcScore(remainSum);
                        bestScore = Math.max(bestScore, score);
                    }
                }
            }
        }
        
        return new GameResult(canMake, bestScore, maxValue);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCases = sc.nex