✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

京东-2026.03.21

这套两题都属于“先把过程抽象清楚，再去实现”的类型。第一题要抓住压缩顺序固定这一点，把过程压成线性 DP；第二题则是典型的图论建模，把两个人的操作拆成到同一会合点的两段最短路。

题目一：三字符压缩的起点个数

关键在于每一步都只处理当前最前面的三个字符，所以整个压缩流程没有分支。长度每次减少 ，状态里只保留“当前前缀最后被压成哪个字符”就够了，转移时按规则统计方案数即可。

难度：中等

题目二：传送后的最短会合步数

本质是整数图最短路。先分别从 出发做一次 BFS，求出到每个城市的最短步数，再枚举会合点，取两段距离和的最小值。

难度：中等

01. 三字符压缩的起点个数

问题描述

小兰在调试一台字符串压缩器。机器里预先写好若干条规则，每条规则都会把长度为 的字符串替换成一个单字符。

这台压缩器的工作方式很死板：

• 当前字符串长度大于 时，总是取最前面的 个字符做一次替换。
• 一次替换后，字符串长度减少 。
• 整个过程持续到最终只剩下 个字符。

现在已经知道：

• 初始字符串长度恰好是 ，并且 为奇数；
• 替换规则一共有 条；
• 最终压缩结果必须是字符 。

请你计算，一共有多少个不同的初始字符串能够满足这个结果。

输入格式

• 第一行两个整数 ，分别表示初始字符串长度和规则数量，保证 为奇数。
• 接下来 行，每行两个字符串 ，表示一条规则 。
• 保证 ，。
• 最后一行一个字符 ，表示最终目标字符。

输出格式

输出一个整数，表示满足条件的初始字符串数量。

样例输入

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

样例输出

3

数据范围

• ，且 为奇数
• 
• 字符均为小写英文字母

题解

关键建模

因为每一步都压缩当前最前面的三个字符，所以压缩顺序是固定的。

设初始长度为 ，总共会做：

次压缩。

第 次压缩结束后，前缀长度从 压成了 个字符。于是状态可以定义为：

• ：当前已经处理到某一步时，前缀压成字符 的初始字符串数量。

转移方式

每条规则是 。

当上一轮前缀压成 ，并且后面再补上 这两个字符时，就能在下一轮压成 。

所以先预处理：

• ：当前字符是 ，再补两个字符后压成 的方案数。

然后做 轮线性 DP：

初始化时，长度为 的前缀里每个字符都对应唯一字符串，所以所有状态初值都是 。

最终答案是 。

正确性说明

固定的“最前 3 个字符压缩”顺序保证了：

• 每一轮只依赖上一轮压缩得到的单字符以及新补进来的两个字符。
• 不会出现区间重排或多种压缩顺序导致的状态歧义。

因此，状态 恰好覆盖“前缀压成 ”的所有初始字符串，而且每个初始字符串只会计入一次，转移完整且不重不漏。

复杂度分析

字符集固定为 26 个小写字母。

• 预处理 ：
• DP 每轮枚举 个字符对，共 轮：
• 空间复杂度：

参考代码

• Python

import sys

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


def solve() -> None:
    n, m = map(int, input().split())

    # trans[p][q]: 当前前缀压成字符 p，继续补两个字符后压成 q 的方案数
    trans = [[0] * 26 for _ in range(26)]
    seen = set()
    for _ in range(m):
        u, v = input().split()
        if len(u) != 3 or len(v) != 1:
            continue
        key = (u, v)
        if key in seen:
            continue
        seen.add(key)
        p = ord(u[0]) - 97
        q = ord(v[0]) - 97
        if 0 <= p < 26 and 0 <= q < 26:
            trans[p][q] += 1

    x = input().strip()
    if n == 1:
        # 只有一个字符时，初始串只能是 x 本身
        print(1)
        return

    if not x or not ('a' <= x <= 'z'):
        print(0)
        return

    steps = (n - 1) // 2

    # 长度为 1 的前缀：每个字符恰好对应 1 个字符串
    dp = [1] * 26
    for _ in range(steps):
        ndp = [0] * 26
        for p in range(26):
            if dp[p] == 0:
                continue
            base = dp[p]
            row = trans[p]
            for q in range(26):
                cnt = row[q]
                if cnt:
                    ndp[q] += base * cnt
        dp = ndp

    print(dp[ord(x) - 97])


if __name__ == "__main__":
    solve()

• Cpp

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

struct BigInt {
    static const int BASE = 1000000000;
    vector<int> d;

    BigInt(long long x = 0) { assign(x); }

    void assign(long long x) {
        d.clear();
        if (x == 0) return;
        while (x > 0) {
            d.push_back((int)(x % BASE));
            x /= BASE;
        }
    }

    bool isZero() const {
        return d.empty();
    }

    void trim() {
        while (!d.empty() && d.back() == 0) {
            d.pop_back();
        }
    }

    void addMul(const BigInt& other, int mul) {
        if (mul == 0 || other.isZero()) {
            return;
        }
        long long carry = 0;
        if (d.size() < other.d.size()) {
            d.resize(other.d.size(), 0);
        }
        for (size_t i = 0; i < other.d.size(); ++i) {
            long long cur = d[i] + 1LL * other.d[i] * mul + carry;
            d[i] = (int)(cur % BASE);
            carry = cur / BASE;
        }
        size_t i = other.d.size();
        while (carry > 0) {
            if (i == d.size()) {
                d.push_back(0);
            }
            long long cur = d[i] + carry;
            d[i] = (int)(cur % BASE);
            carry = cur / BASE;
            ++i;
        }
    }
};

ostream& operator<<(ostream& out, const BigInt& value) {
    if (value.d.empty()) {
        out << 0;
        return out;
    }
    out << value.d.back();
    for (int i = (int)value.d.size() - 2; i >= 0; --i) {
        out << setw(9) << setfill('0') << value.d[i];
    }
    return out;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> trans(26, vector<int>(26, 0));
    set<pair<string, string>> seen;

    for (int i = 0; i < m; ++i) {
        string u, v;
        cin >> u >> v;
        if ((int)u.size() != 3 || (int)v.size() != 1) {
            continue;
        }
        pair<string, string> key = {u, v};
        if (seen.count(key)) {
            continue;
        }
        seen.insert(key);
        int p = u[0] - 'a';
        int q = v[0] - 'a';
        if (0 <= p && p < 26 && 0 <= q && q < 26) {
            trans[p][q]++;
        }
    }

    string x;
    cin >> x;

    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }
    if (x.empty() || x[0] < 'a' || x[0] > 'z') {
        cout << 0 << '\n';
        return 0;
    }

    int steps = (n - 1) / 2;
    vector<BigInt> dp(26, BigInt(1)), ndp(26);

    for (int t = 0; t < steps; ++t) {
        for (int i = 0; i < 26; ++i) {
            ndp[i] = BigInt(0);
        }
        for (int p = 0; p < 26; ++p) {
            if (dp[p].isZero()) {
                continue;
            }
            for (int q = 0; q < 26; ++q) {