✅ 秋招备战指南 ✅

💡 学习建议：

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

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

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

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

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

京东-2025.11.22

题目一：魔法咒语解码

1️⃣：将压缩规则建模为有向图，每条规则视为一条边

2️⃣：使用动态规划计算长度为 k 的路径数，其中 k = (n-1)/2

3️⃣：状态转移：枚举所有规则进行路径扩展

难度：中等

题目二：咖啡师的时间艺术

1️⃣：分析两两顾客的服务顺序，推导贪心准则

2️⃣：按照 的准则对顾客排序

3️⃣：依次累加服务时间，使用公式 更新

难度：中等

1. 魔法咒语解码

问题描述

小兰是一位魔法学院的研究员，她最近在研究古老的魔法咒语编码系统。在这个系统中，存在一种特殊的咒语压缩规则：每次可以将咒语开头的三个连续魔法符号按照特定规则压缩成一个符号。

经过多次压缩操作后，一段完整的咒语最终会被压缩成单个魔法符号。小兰手里有一本魔法压缩手册，记录了所有可用的压缩规则。

有一天，小兰在整理实验笔记时，发现自己记录了一个压缩后的最终符号 ，以及使用的压缩规则表，但原始的完整咒语却遗失了。现在她想知道，有多少种不同的原始咒语可能被压缩成这个符号 ？

输入格式

第一行包含两个正整数 ，分别表示原始咒语的长度和压缩规则的数量。保证 为奇数。

接下来 行，每行包含两个字符串 ，表示一条压缩规则（将 压缩成 ）。保证 的长度为 ， 的长度为 。保证不会有完全相同的两条压缩规则（即不存在 满足 且同时满足 和 ）。

接下来一行包含一个字符 ，表示经过压缩后最终得到的单个符号。

对于本题中出现的所有字符和字符串（包括 ），保证它们仅由小写英文字母组成。

输出格式

输出一行一个整数，表示可能的原始咒语有多少种不同的可能。

样例输入

5 5
acd b
acf b
bcc c
bdd e
ccc e
e

9 4
abc d
def g
ghi j
jkl m
m

样例输出

3

1

样例	解释说明
样例1	长度为 的咒语需要经过 次压缩才能变成单个符号。通过分析所有可能的压缩路径，可以找到 种不同的原始咒语能够最终压缩成符号 e。
样例2	长度为 的咒语需要经过 次压缩。按照给定的规则链 abc→d→g→j→m，只有一种可能的原始咒语序列能够最终得到符号 m。

数据范围

• 

• 

• 为奇数

题解

这道题乍一看可能觉得复杂，但其实可以用一个巧妙的动态规划思路来解决。

问题本质

首先理解压缩过程：每次从字符串开头取 个字符，根据规则表压缩成 个字符。一个长度为 的字符串需要压缩 次才能变成单个字符。

关键观察：每条压缩规则 ，我们只关心 的第一个字符和 ，因为压缩是从字符串开头进行的。可以把每条规则看作一条有向边：从字符 到字符 。

那么问题就转化成：在这张有向多重图中，有多少条长度为 的路径，使得终点是字符 ？注意起点可以是任意字符。

动态规划思路

定义状态： 表示经过 次压缩后，当前字符为 的方案数。

初始化：当 时，每条规则都能直接使用一次（因为起点不限），所以对于每条规则 ，我们让 加 。

状态转移：对于第 次压缩（），遍历所有规则。对于规则 ，如果上一步的结果是 ，那么这一步可以转移到 ，即：

最终答案就是 。

特殊情况：当 时，原始咒语本身就是单个字符 ，答案是 。

复杂度分析

时间复杂度：，其中 ，，非常高效。

空间复杂度：，其中 是字符集大小。

参考代码

• Python

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

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

# 特殊情况：n=1 时直接输出 1
if n == 1:
    x = input()
    print(1)
else:
    k = (n - 1) // 2  # 需要压缩的次数
    
    # 存储所有规则的起点和终点
    rules = []
    for _ in range(m):
        line = input().split()
        u, v = line[0], line[1]
        # 只关心起点的第一个字符和终点字符
        u_ch = ord(u[0]) - ord('a')
        v_ch = ord(v[0]) - ord('a')
        rules.append((u_ch, v_ch))
    
    x = input().strip()
    x_idx = ord(x) - ord('a')
    
    # dp[c] 表示当前步数下字符 c 的方案数
    dp = [0] * 26
    
    # 初始化：第一次压缩，每条规则都可以使用
    for u_ch, v_ch in rules:
        dp[v_ch] += 1
    
    # 动态规划：从第 2 次到第 k 次压缩
    for step in range(2, k + 1):
        nxt = [0] * 26  # 下一步的状态
        for u_ch, v_ch in rules:
            # 如果上一步得到了 u_ch，这一步可以转移到 v_ch
            nxt[v_ch] += dp[u_ch]
        dp = nxt
    
    print(dp[x_idx])

• Cpp

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    // 特殊情况：长度为 1
    if (n == 1) {
        char x;
        cin >> x;
        cout << 1 << "\n";
        return 0;
    }
    
    int k = (n - 1) / 2;  // 压缩次数
    
    // 存储规则：u[i] -> v[i]
    vector<int> u_chs(m), v_chs(m);
    for (int i = 0; i < m; i++) {
        string u_str, v_str;
        cin >> u_str >> v_str;
        u_chs[i] = u_str[0] - 'a';  // 只取第一个字符
        v_chs[i] = v_str[0] - 'a';
    }
    
    char x;
    cin >> x;
    int x_id = x - 'a';
    
    // dp[c] 表示当前字符 c 的方案数
    vector<ull> dp(26, 0), nxt(26, 0);
    
    // 第一次压缩：每条规则都可直接使用
    for (int i = 0; i < m; i++) {
        dp[v_chs[i]]++;
    }
    
    // 后续压缩：从第 2 次到第 k 次
    for (int step = 2; step <= k; step++) {
        fill(nxt.begin(), nxt.end(), 0);
        // 枚举所有规则进行转移
        for (int i = 0; i < m; i++) {
            nxt[v_chs[i]] += dp[u_chs[i]];
        }
        dp.swap(nxt);
    }
    
    cout << dp[x_id] << "\n";
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));