✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

题目一：小兰的菜谱安排

1️⃣：特殊情况处理，当k=0时直接快速幂计算m^n

2️⃣：动态规划+前缀和优化，状态转移考虑相邻约束条件

难度：中等

这道题目的关键在于理解相邻元素差值约束的动态规划问题。当k=0时为无约束情况，直接用快速幂计算。当k>0时需要用DP，通过前缀和优化区间求和，实现O(nm)时间复杂度的高效解法。

题目二：小毛的机器人导航

1️⃣：状态扩展BFS，将移动方向作为状态维度

2️⃣：三元组状态(x,y,dir)表示位置和上一步移动方向

3️⃣：根据移动方向约束进行状态转移

难度：中等

这道题目需要理解带有特殊约束的最短路径问题。关键在于将"上一步移动方向"纳入状态，使用三维BFS来处理方向交替的约束条件。通过合理的状态设计和转移，可以在O(nm)时间内求出最短路径。

01. 小兰的菜谱安排

问题描述

小兰是一名美食博主，她每天都要更新自己的料理日记。为了让观众们不觉得单调，小兰决定制定一个 天的菜谱计划，确保连续两天制作的菜品风格不能太相似。

小兰总共掌握 种不同的菜品，每种菜品都有一个独特的风味编号（从 到 ）。她认为只有当两种菜品的风味编号相差至少 时，它们的口味才算是明显不同的。

现在小兰想知道：在满足相邻两天菜品风味差异至少为 的条件下，一共有多少种不同的 天菜谱安排方案？

由于方案数可能很大，请将结果对 取模。

输入格式

输入一行包含三个正整数 ，分别表示计划天数、菜品总数和最小风味差异值。

输出格式

输出一行，包含一个整数，表示合法的菜谱安排方案数，结果对 取模。

样例输入

3 4 2

样例输出

10

数据范围

题解

这道题本质上是一个动态规划问题，需要计算满足相邻元素差值约束的序列数量。

首先分析问题的特殊情况：当 时，相邻菜品没有任何限制，每天都可以选择任意菜品，答案就是 ，可以用快速幂快速计算。

当 时，就需要考虑相邻约束了。可以用动态规划来解决：

定义状态 dp[i][j] 表示前 天，第 天选择菜品 的方案数。

状态转移时，第 天选择菜品 ，那么第 天的菜品 必须满足 ，也就是 或者 。

因此转移方程为：

为了快速计算这两个区间和，可以维护前缀和数组。对于第 层的状态，计算前缀和 pre[x] = dp[i][1] + dp[i][2] + ... + dp[i][x]，这样就能用 的时间计算任意区间和。

算法的时间复杂度是 ，对于 的数据范围完全可以接受。

参考代码

• Python

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

MOD = 998244353

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

def add_mod(a, b):
    # 模意义下的加法
    return (a + b) % MOD

def sub_mod(a, b):
    # 模意义下的减法
    return (a - b + MOD) % MOD

n, m, k = map(int, input().split())

# 特殊情况：无约束条件
if k == 0:
    print(pow_mod(m, n))
else:
    # 动态规划求解
    dp = [1] * (m + 1)  # dp[i] 表示选择菜品i的方案数
    
    for day in range(2, n + 1):
        # 计算前缀和
        pre = [0] * (m + 1)
        for i in range(1, m + 1):
            pre[i] = add_mod(pre[i-1], dp[i])
        
        total = pre[m]  # 所有方案数的总和
        new_dp = [0] * (m + 1)
        
        for u in range(1, m + 1):
            # 计算 v <= u-k 的方案数
            left_sum = pre[u-k] if u-k >= 1 else 0
            # 计算 v >= u+k 的方案数  
            right_sum = sub_mod(total, pre[u+k-1]) if u+k <= m else 0
            new_dp[u] = add_mod(left_sum, right_sum)
        
        dp = new_dp
    
    # 计算最终答案
    ans = 0
    for i in range(1, m + 1):
        ans = add_mod(ans, dp[i])
    
    print(ans)

• Cpp

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

const int MOD = 998244353;

// 快速幂函数
long long pow_mod(long long a, long long e) {
    long long res = 1;
    while (e > 0) {
        if (e & 1) res = res * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return res;
}

// 模意义下的加法
inline int add_mod(int a, int b) {
    return (a + b) >= MOD ? (a + b - MOD) : (a + b);
}

// 模意义下的减法
inline int sub_mod(int a, int b) {
    return (a - b) < 0 ? (a - b + MOD) : (a - b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, k;
    cin >> n >> m >> k;
    
    // 特殊情况处理
    if (k == 0) {
        cout << pow_mod(m, n) << "\n";
        return 0;
    }
    
    // 初始化dp数组，第一天每种菜品都可以选
    vector<int> dp(m + 1, 1);
    
    for (int day = 2; day <= n; ++day) {
        // 计算前缀和数组
        vector<int> pre(m + 1, 0);
        for (int i = 1; i <= m; ++i) {
            pre[i] = add_mod(pre[i-1], dp[i]);
        }
        
        int total = pre[m];
        vector<int> new_dp(m + 1, 0);
        
        for (int u = 1; u <= m; ++u) {
            // 计算满足条件的方案数
            int left_sum = (u - k >= 1) ? pre[u - k] : 0;
            int right_sum = (u + k <= m) ? sub_mod(total, pre[u + k - 1]) : 0;
            new_dp[u] = add_mod(left_sum, right_sum);
        }
        
        dp = move(new_dp);
    }
    
    // 统计最终答案
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
        ans = add_mod(ans, dp[i]);
    }
    
    cout << ans << "\n";
    return 0;
}

• Java

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

public class Main {
    static final int MOD = 998244353;
    
    // 快速幂函数
    static long powMod(long a, long e) {
        long res = 1;
        while (e > 0) {
            if ((e & 1) == 1) res = res * a % MOD;
            a = a * a % MOD;
            e >>= 1;
        }
        return res;
    }
    
    // 模意义下的加法
    static int addMod(int a, int b) {
        return (a + b) >= MOD ? (a + b - MOD) : (a + b);
    }
    
    // 模意义下的减法
    static int subMod(int a, int b) {
        return (a - b) < 0 ? (a - b + MOD) : (a - b);
    }
    
    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());
        int k = Integer.parseInt(st.nextToken());
        
        // 特殊情况：无约束
        if (k == 0) {
            System.out.println(powMod(m, n));
            return;
        }
        
        // DP求解
        int[] dp = new int[m + 1];
        Arrays.fill(dp, 1, m + 1, 1);  // 第一天每种菜都可选
        
        for (int day = 2; day <= n; ++day) {
            // 计算前缀和
            int[] prefSum = new int[m + 1];
            for (int i = 1; i <= m; ++i) {
                prefSum[i] = addMod(prefSum[i-1], dp[i]);
            }
            
            int totalSum = prefSum[m];
            int[] newDp = new int[m + 1];