✅ 春招备战指南 ✅

💡 学习建议：

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

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

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

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

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

携程-2026.03.12

这套携程题的梯度很明显。前两题都是抓规律后可以快速落地的类型，第三题开始转成前缀和加二分的结构化题，第四题则直接要求认出 SOS DP 这个位运算经典模型。

题目一：纪念徽章尾号

这题本质上就是一个阶乘尾数规律题。只要意识到 n >= 5 后阶乘一定带因子 10，就能直接做到常数时间。

难度：Low

题目二：盲盒拆分计划

关键不在枚举素数，而在先证明“为了让数量最多，只会用到 2 和 3”。随后把问题收缩成奇偶性和最小合法奇素数个数的分类讨论即可。

难度：Mid

题目三：均衡货架切分

这题看似是递归切段，真正支点是“所有数都为正，所以前缀和严格递增”。有了这个性质，每个区间能不能切就能转成一次二分查找。

难度：High

题目四：子集口令求和

条件 (x & i) = i 等价于 “i 是 x 的二进制子集”，这是整题唯一的突破口。只要识别出这个模型，就可以直接上 SOS DP 预处理所有答案。

难度：High

01. 吉祥物尾牌

问题描述

A 先生正在给一批活动吉祥物挂牌编号。

第 个吉祥物的尾牌编号规则很特别，它被定义为：

也就是常见的阶乘 。

现在 A 先生只关心这个大数的最后一位数字。给定整数 ，请输出 的个位数字。

输入格式

输入一行，一个整数 。

输出格式

输出一个整数，表示 的个位数字。

样例输入

3

样例输出

6

数据范围

• 

样例	解释说明
样例1	，所以个位数字是 。
若输入为 1	，因此答案是 。

题解

这题真正考的不是怎么去算阶乘，而是观察个位数字什么时候会固定下来。

只要 ，那么 的乘积里一定同时包含：

• 一个因子
• 一个因子

而 ，这就意味着整个乘积末尾至少会出现一个 。所以：

• 当 时，答案一定是 。

剩下只需要处理前面几个很小的情况：

• 
• 
• 
• ，个位是

也就是说，这题根本不需要真的去做大整数乘法，只要分类讨论即可。

时间复杂度是 ，空间复杂度也是 。

参考代码

• Python

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


def solve():
    n = int(input())

    # 当 n >= 5 时，阶乘里一定出现因子 2 和 5，
    # 所以末尾至少有一个 0。
    if n >= 5:
        print(0)
        return

    # 直接保存 1! 到 4! 的个位数字。
    last = [0, 1, 2, 6, 4]
    print(last[n])


if __name__ == "__main__":
    solve()

• Cpp

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

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

    long long n;
    cin >> n;

    // n >= 5 时，n! 一定包含因子 10，个位固定为 0。
    if (n >= 5) {
        cout << 0 << '\n';
        return 0;
    }

    // 记录小范围阶乘的个位数字。
    int last[5] = {0, 1, 2, 6, 4};
    cout << last[n] << '\n';
    return 0;
}

• Java

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine().trim());

        // 当 n >= 5 时，阶乘末尾一定出现 0。
        if (n >= 5) {
            System.out.println(0);
            return;
        }

        int[] last = {0, 1, 2, 6, 4};
        System.out.println(last[(int) n]);
    }
}

02. 盲盒素数组装

问题描述

K 小姐正在准备一批盲盒礼包，总价值一共是 。

她打算把这份价值拆成若干个素数价值的小礼包，允许重复使用同一个素数。假设最终一共拆出了 个素数。

不过运营同学额外提出了一个限制：

• 所有被选中的奇素数，也就是除 以外的素数，其数量必须是 的正整数倍；
• 奇素数的数量不能是 。

在满足以上条件的前提下，K 小姐希望素数礼包的总个数 尽可能大。请输出这个最大的 ；如果不存在任何合法方案，输出 -1。

输入格式

第一行输入一个整数 ，表示测试数据组数。

接下来 行，每行输入两个整数 。

输出格式

对于每组数据，输出一行一个整数，表示最大的素数个数；若无解，输出 -1。

样例输入

4
6 2
2 1
30 4
1000000000000 1

样例输出

2
-1
13
499999999999

数据范围

• 
• 
• 

样例	解释说明
样例1 的第一组	可以拆成 ，奇素数个数为 ，刚好是 的正整数倍，因此答案是 。
样例1 的第二组	时只能用素数 ，但奇素数个数不能为 ，所以无解。

题解

如果想让素数个数尽量多，那么就应该尽量使用最小的素数。

最小的素数是 ，次小的奇素数是 。由于题目对奇素数数量有限制，所以最优方案一定长这样：

• 用尽可能少的奇素数去满足条件；
• 这些奇素数全都取成最小的 ；
• 剩下的部分全部用 去填。

这样才会让素数总个数最大。

接下来问题就变成：奇素数最少要取多少个。

设奇素数个数是 odd。

因为：

• odd 必须是 的正整数倍；
• 每个奇素数都是奇数，若用了 odd 个奇数，那么它们的总和奇偶性与 odd 相同；
• 剩余部分全部由若干个 组成，因此剩余和一定是偶数；

所以 odd 必须与 同奇偶，否则剩下的数不可能完全由 填满。

于是：

• 如果 和 同奇偶，那么最少取 odd = m；
• 如果 是奇数、 是偶数，那么最少取 odd = 2m；
• 如果 是偶数、 是奇数，那么无论取多少个 的倍数，奇素数个数都还是偶数，不可能与奇数的 同奇偶，因此无解。

确定了 odd 之后，还要保证最小总和不超过 。

因为每个奇素数最小只能是 ，所以至少需要：

若这个值已经大于 ，同样无解。

否则，剩下的部分全部补成 即可。设补了 two 个 ，那么：

总素数个数就是：

整题每组数据只需要做常数次判断，时间复杂度是 ，空间复杂度也是 。

参考代码

• Python

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


def solve():
    t = int(input())
    out = []

    for _ in range(t):
        n, m = map(int, input().split())

        # odd 表示最少需要选多少个奇素数。
        if (n & 1) == (m & 1):
            odd = m
        elif m & 1:
            odd = 2 * m
        else:
            out.append("-1")
            continue

        # 每个奇素数最小只能取 3，先判断最小和是否超出。
        if 3 * odd > n:
            out.append("-1")
            continue

        # 剩余部分全部由 2 填充，总个数化简为 (n - odd) // 2。
        out.append(str((n - odd) // 2))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128_t;

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

    int t;
    cin >> t;

    while (t--) {
        i64 n, m;
        cin >> n >> m;

        i128 odd;

        // 先求满足奇偶性的最少奇素数个数。
        if ((n & 1LL) == (m & 1LL)) {
            odd = m;
        } else if (m & 1LL) {
            odd = (i128)2 * m;
        } else {
            cout << -1 << '\n';
            continue;
        }

        // 最小奇素数都是 3，如果连最小和都放不下就无解。
        if ((i128)3 * odd > (i128)n) {
            cout << -1 << '\n';
            continue;
        }

        // 剩余都放成 2，答案可直接化简。
        i128 ans = ((i128)n - odd) / 2;
        cout << (long long)ans << '\n';
    }

    return 0;
}

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();

        for (int cs = 0; cs < t; cs++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long n = Long.parseLong(st.nextToken());
            long m = Long.parseLong(st.nextToken());

            long odd;

            // odd 表示最少需要的奇素数个数。
            if ((n & 1L) == (m & 1L)) {
                odd = m;
            } else if ((m & 1L) == 1L) {
                odd = 2L * m;
            } else {
                sb.append(-1).append('\n');
                continue;
            }

            // 先判断最小可能的奇素数总和是否超出 n。
            if (odd > n / 3L) {
                sb.append(-1).append('\n');
                continue;
            }

            long ans = (n - odd) / 2L;
            sb.append(ans).append('\n');
        }

        System.out.print(sb);
    }
}

03. 均衡货架切分

问题描述

K 小姐在整理一排仓储货架，第 个货架上放着价值为 的一组货物。

现在她想反复进行“均衡切分”操作：

• 一开始，整排货架只看作一个完整区间 ；
• 每次只能从当前已经存在的某个完整区间 中继续操作；
• 这个区间的长度必须严格大于 ；
• 选择一个切分点 mid，满足 ；
• 如果左半段和右半段的货物总价值相等，也就是

那么就可以把区间 切成两个新区间 和 ，以后只允许在这两个新区间上继续切。

请计算，在最优策略下，最多能进行多少次合法切分。

输入格式

第一行输入一个整数 ，表示货架数量。

第二行输入 个整数 ，表示每个货架上的货物价值。

输出格式

输出一个整数，表示最多的切分次数。如果不存在任何合法切分，输出 0。

样例输入

6
1 2 1 1 1 2

样例输出

2

数据范围

• 
• 

样例	解释说明
样例1	整段可以先切成 [1,3] 和 [4,6]，随后 [4,6] 还能再切一次，所以答案为 2。

题解

由于所有 都是正整数，所以前缀和数组是严格递增的，这一点非常关键。

设前缀和为：

对于某个区间 ，它的区间和为：

如果这个区间能够被平分，那么左右两边的和都应该等于区间总和的一半。因此只需要寻找一个位置 k，满足：

并且 l <= k <= r-1。此时切分点就是 mid = k + 1。

为什么可以二分查找？

• 因为所有 ，所以 pre 严格递增；
• 在严格递增数组里找某个目标值，直接二分就行。

整个过程可以用栈来模拟递归：

1. 初始把区间 [1,n] 放进栈里。
2. 每次弹出一个区间 [l,r]。
3. 如果长度小于 3，或者区间和是奇数，那么它一定无法继续切。
4. 否则计算目标前缀和值，并在 pre 中二分查找。
5. 若找到合法位置，就把这次切分计入答案，并把左右两个新区间继续压栈。

这样每个成功或失败的区间都会被处理一次，而每次查找只做一次二分。

时间复杂度是 ，空间复杂度是 。

参考代码

• Python

import sys
from bisect import bisect_left

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


def solve():
    n = int(input())
    a = list(map(int, input().split()))

    # pre[i] 表示前 i 个位置的前缀和，pre[0] = 0。
    pre = [0] * (n + 1)
    for i in range(1, n + 1):
        pre[i] = pre[i - 1] + a[i - 1]

    ans = 0
    stk = [(1, n)]

    while stk:
        l, r = stk.pop()

        # 长度不足 3 时，不可能再切成两个非空区间。
        if r - l + 1 < 3:
            continue

        seg_sum = pre[r] - pre[l - 1]
        if seg_sum & 1:
            continue

        target = pre[l - 1] + seg_sum // 2

        # 前缀和严格递增，可以直接二分。
        k = bisect_left(pre, target, l, r)
        if k >= r or pre[k] != target:
            continue

        ans += 1
        stk.append((l, k))
        stk.append((k + 1, r))

    print(ans)


if __name__ == "__main__":
    solve()

• Cpp

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

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

    int n;
    cin >> n;

    vector<int64> pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int64 x;
        cin >> x;
        pre[i] = pre[i - 1] + x;
    }

    int64 ans = 0;
    vector<pair<int, int>> stk;
    stk.push_back({1, n});

    while (!stk.empty()) {
        auto [l, r] = stk.back();
        stk.pop_back();

        // 至少要有 3 个位置，才有机会继续切分。
        if (r - l + 1 < 3) {
            continue;
        }

        int64 segSum = pre[r] - pre[l - 1];
        if (segSum & 1LL) {
            continue;
        }

        int64 target = pre[l - 1] + segSum / 2;

        // 只在当前区间对应的前缀和范围里寻找切点。
        auto it = lower_bound(pre.begin() + l, pre.begin() + r, target);
        if (it == pre.begin() + r || *it != target) {
            continue;
        }

        int k = (int)(it - pre.begin());
        ans++;
        stk.push_back({l, k});
        stk.push_back({k + 1, r});
    }

    cout << ans << '\n';
    return 0;
}

• Java

import java.io.BufferedInputStream;
import java.util.ArrayDeque;

public class Main {
    static class FastScanner {
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        private final BufferedInputStream in = new BufferedInputStream(System.in);

        private int read() throws Exception {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) {
                    return -1;
                }
            }
            return buffer[ptr++];
        }

        long nextLong() throws Exception {
            int c;
            do {
                c = read();
            } while (c <= 32);
            long sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            long val = 0;
            while (c > 32) {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner();
        int n = (int) fs.nextLong();

        long[] pre = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + fs.nextLong();
        }

        long ans = 0;
        ArrayDeque<int[]> stk = new ArrayDeque<>();
        stk.push(new int[]{1, n});

        while (!stk.isEmpty()) {
            int[] cur = stk.pop();
            int l = cur[0], r = cur[1];

            if (r - l + 1 < 3) {
                continue;
            }

            long segSum = pre[r] - pre[l - 1];
            if ((segSum & 1L) == 1L) {
                continue;
            }

            long target = pre[l - 1] + segSum / 2;

            int left = l, right = r - 1, pos = -1;
            while (left <= right) {
                int mid = (left + right) >>> 1;
                if (pre[mid] >= target) {
                    if (pre[mid] == target) {
                        pos = mid;
                    }
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            if (pos == -1) {
                continue;
            }

            ans++;
            stk.push(new int[]{l, pos});
            stk.push(new int[]{pos + 1, r});
        }

        System.out.println(ans);
    }
}

04. 子集口令求和

问题描述

在一套权限系统里，第 个功能模块带有一个权重 。

现在有很多次查询。每次给出一个整数 ，需要统计所有满足

的下标 对应权重之和。

这里 & 表示按位与运算。条件 (x & i) = i 的含义是：下标 i 的每个二进制 1 位，在 x 中也必须是 1。换句话说，i 是 x 的一个二进制子集。

请回答所有查询。

输入格式

第一行输入一个整数 ，表示测试数据组数。

对于每组数据：

• 第一行输入两个整数 ；
• 第二行输入 个整数 ；
• 第三行输入 个整数 。

输出格式

对于每个查询输出一行一个整数，表示答案。

样例输入

3
5 3
1 2 3 4 5
0 7 5
3 2
10 -5 7
3 2
6 3
0 1 2 3 4 5
6 4 7

样例输出

0
15
10
12
-5
9
3
15

数据范围

• 
• 
• 
• 
• 所有测试中 的总和不超过

样例	解释说明
样例1	x = 7 时，1,2,3,4,5 都是 7 的二进制子集，所以答案是 1+2+3+4+5=15。

题解

如果对每次查询都暴力枚举所有下标 i，复杂度会达到 ，肯定过不去。

观察条件：

这等价于说：i 是 x 的一个子集状态。

于是题目变成了经典的子集和预处理问题。

设 f[mask] 表示所有下标属于 mask 的子集时，对应权重之和。初始时：

• 如果 1 <= i <= n，就令 f[i] = a_i
• 其余位置初始化为 0

然后做一遍 SOS DP（子集和动态规划）：

对每一位 b，枚举所有 mask，如果这一位是 1，就执行：

这样处理完以后，f[x] 就正好等于所有 i \subseteq x 的权重和，也就是题目要求的答案。

为什么这样做是对的？

• 每次转移都在把“少一位”的子集贡献合并到当前状态。
• 所有位都处理完以后，mask 的全部子集都会被累计进来。
• 条件 (x & i) = i 恰好就是“i 是 x 的子集”。

设 M = max(n, max(x))，所需二进制位数约为 ，单组复杂度就是 。

参考代码

• Python

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


def solve():
    t = int(input())
    out = []

    for _ in range(t):
        n, q = map(int, input().split())
        a = [0] + list(map(int, input().split()))
        xs = list(map(int, input().split()))

        m = max(n, max(xs) if xs else 0)
        f = [0] * (m + 1)

        # 把下标对应的权重放进初始状态。
        for i in range(1, n + 1):
            f[i] = a[i]

        bit = 0
        while (1 << bit) <= m:
            step = 1 << bit
            for mask in range(m + 1):
                if mask & step:
                    f[mask] += f[mask ^ step]
            bit += 1

        for x in xs:
            out.append(str(f[x]))

    print("\n".join(out))


if __name__ == "__main__":
    solve()

• Cpp

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

int main() {
    ios::sy