✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

京东-2026.03.21-第二套

这套题一轻一中，节奏很像机考里的“先观察规律，再补标准 DP”。第一题虽然看起来是路径计数，但核心信息其实只有最后一步的形态，推出线性递推后直接上矩阵快速幂；第二题则是双目标资源分配，重点是把“最多完成多少”放在第一优先级，再在可行状态里找最小燃料。

题目一：灵动坐标系

这题最容易被题面里的“不能经过相同的点”吓到，实际上路径状态非常少。只要按“最后一步向上 / 最后一步水平”拆开，就能推出 ，后面就是标准矩阵快速幂。

难度：中等

题目二：星际快递

关键不是贪心挑哪个包裹更便宜，而是同时维护“已经送了多少件”和“用了多少张通行证”。用 记录达到该状态的最小燃料，再从大到小找第一个可行的 ，就能自然满足题目的双层目标。

难度：中等

01. 灵动坐标系

问题描述

本题是京东 2025.11.15 第 2 题的原题。

小 A 一觉醒来，发现自己站在一个无限大的平面直角坐标系原点。

他每一步只能选择下面三个方向之一，并且恰好走 个单位：

• 向上
• 向左
• 向右

还有一个额外限制：

• 整条路线中不能经过同一个点两次。

现在给定步数 ，请你计算一共有多少种合法走法。由于答案可能很大，请对 取模。

输入格式

输入只有一行，包含一个整数 。

输出格式

输出一个整数，表示合法方案数对 取模后的结果。

样例输入 1

2

样例输出 1

7

样例说明 1

走两步时，合法方案分别是：

• 上上
• 上左
• 上右
• 左上
• 左左
• 右上
• 右右

一共 种。

样例输入 2

3

样例输出 2

17

数据范围

• 

样例	解释说明
样例1	走两步时，只要下一步不会回到已经经过的点，就是合法方案。
样例2	走三步时答案为 ，继续暴力枚举就已经开始变得不划算了。

题解

这题看着像搜索，但 给到了 ，肯定不能真的把所有走法展开。

关键在于把“最后一步的形态”抽出来。

第一步：把路径按最后一步分类

设：

• 表示走了 步后，最后一步是“向上”的方案数。
• 表示走了 步后，最后一步是“向左或向右”的方案数。

总答案就是：

第二步：看下一步能怎么走

如果当前最后一步是向上，那么下一步有 种合法选择：

• 继续向上
• 向左
• 向右

因为上方、左方、右方都还没有走过。

如果当前最后一步是水平移动，比如刚刚向左走了一步，那么：

• 不能立刻向右，因为会回到刚才那个点；
• 可以继续向左；
• 也可以向上。

所以这种状态下一共只有 种选择。

于是有：

因为任何一个长度为 的合法路径，最后都可以再接一步“向上”。

同时：

因为：

• 从“最后一步向上”的状态出发，可以接“向左”或“向右”这 种水平走法；
• 从“最后一步水平”的状态出发，只能继续朝原来的水平方向延伸，贡献 种。

第三步：化成单变量递推

由 可以得到：

再把它代回去：

所以递推式就是：

初值为：

第四步：矩阵快速幂

线性递推最适合直接转成矩阵：

于是：

这样就能在 时间内求出答案。

复杂度分析

• 时间复杂度：
• 空间复杂度：

参考代码

• Python

import sys

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


def mul(a, b):
    # 计算两个 2x2 矩阵乘积。
    return [
        [
            (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD,
            (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD,
        ],
        [
            (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD,
            (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD,
        ],
    ]


def qpow(mat, exp):
    # 2x2 单位矩阵。
    res = [[1, 0], [0, 1]]
    while exp > 0:
        if exp & 1:
            res = mul(res, mat)
        mat = mul(mat, mat)
        exp >>= 1
    return res


def solve():
    n = int(input())
    if n == 1:
        print(3)
        return
    if n == 2:
        print(7)
        return

    trans = [[2, 1], [1, 0]]
    mat = qpow(trans, n - 2)

    # [f_n, f_{n-1}]^T = mat * [7, 3]^T
    ans = (mat[0][0] * 7 + mat[0][1] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    solve()

• Cpp

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

static const long long MOD = 1000000007LL;

struct Matrix {
    long long a[2][2];
};

Matrix multiply(const Matrix& x, const Matrix& y) {
    Matrix res{};
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                res.a[i][j] = (res.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
            }
        }
    }
    return res;
}

Matrix power(Matrix base, long long exp) {
    Matrix res{};
    res.a[0][0] = 1;
    res.a[1][1] = 1;
    while (exp > 0) {
        if (exp & 1) {
            res = multiply(res, base);
        }
        base = multiply(base, base);
        exp >>= 1;
    }
    return res;
}

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

    long long n;
    cin >> n;

    if (n == 1) {
        cout << 3 << '\n';
        return 0;
    }
    if (n == 2) {
        cout << 7 << '\n';
        return 0;
    }

    Matrix trans{};
    trans.a[0][0] = 2;
    trans.a[0][1] = 1;
    trans.a[1][0] = 1;
    trans.a[1][1] = 0;
    Matrix mat = power(trans, n - 2);

    // [f_n, f_{n-1}]^T = mat * [7, 3]^T
    long long ans = (mat.a[0][0] * 7 + mat.a[0][1] * 3) % MOD;
    cout << ans << '\n';
    return 0;
}

• Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static final long MOD = 1_000_000_007L;

    static class Matrix {
        long[][] a = new long[2][2];
    }

    static Matrix multiply(Matrix x, Matrix y) {
        Matrix res = new Matrix();
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    res.a[i][j] = (res.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
                }
            }
        }
        return res;
    }

    static Matrix power(Matrix base, long exp) {
        Matrix res = new Matrix();
        res.a[0][0] = 1;
        res.a[1][1] = 1;

        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = multiply(res, base);
            }
            base = multiply(base, base);
            exp >>= 1;
        }
        retu