🔗刷题网址: bishipass.com

携程-2026.03.12-算法岗

本套算法岗，第 1、2、4 题与研发岗一致，第 3 题替换成了无监督学习流程。整体覆盖规律观察、分类讨论、机器学习工程实现，以及位运算 SOS DP 四个方向。

题目1：吉祥物尾牌

问题描述

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

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

也就是常见的阶乘 。

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

输入格式

输入一行，一个整数 。

输出格式

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

样例输入

3

样例输出

6

数据范围

• >

题解

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

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

• >
  一个因子 
• >
  一个因子 

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

• >
  当  时，答案一定是 。

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

• >
• >
• >
• >
  ，个位是 

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

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

参考代码

• >
  Python

import sysinput = lambda: sys.stdin.readline().strip()defsolve():    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

#includeusingnamespacestd;intmain(){    ios::sync_with_stdio(false);cin.tie(nullptr);longlong n;cin >> n;// n >= 5 时，n! 一定包含因子 10，个位固定为 0。if (n >= 5) {cout << 0 << '\n';return0;    }// 记录小范围阶乘的个位数字。int last[5] = {0, 1, 2, 6, 4};cout << last[n] << '\n';return0;}

• >
  Java

import java.io.BufferedReader;import java.io.InputStreamReader;publicclassMain{publicstaticvoidmain(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]);    }}

题目2：盲盒素数组装

问题描述

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

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

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

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

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

输入格式

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

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

输出格式

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

样例输入

46 22 130 41000000000000 1

样例输出

2-113499999999999

数据范围

• >
• >
• >

题解

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

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

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

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

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

设奇素数个数是 odd。

因为：

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

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

于是：

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

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

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

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

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

总素数个数就是：

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

参考代码

• >
  Python

import sysinput = lambda: sys.stdin.readline().strip()defsolve():    t = int(input())    out = []for _ in range(t):        n, m = map(int, input().split())# odd 表示最少需要选多少个奇素数。if (n & 1) == (m & 1):            odd = melif m & 1:            odd = 2 * melse:            out.append("-1")continue# 每个奇素数最小只能取 3，先判断最小和是否超出。if3 * 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

#includeusingnamespacestd;using i64 = longlong;using i128 = __int128_t;intmain(){    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;        } elseif (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 << (longlong)ans << '\n';    }return0;}

• >
  Java

import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;publicclassMain{publicstaticvoidmain(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;            } elseif ((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);    }}

题目3：无监督学习流程

问题描述

在仅使用 numpy/pandas/scikit-learn 的前提下，完成如下无监督三步流程，并对测试集输出聚类标签。

1. 预处理：对训练集与测试集的所有列，先用训练集该列均值填充 NaN；如果某一行列数不足最大列数，则缺失位置也视为 NaN。随后用 StandardScaler 在训练集上 fit，并对训练集、测试集做同一变换。
2. 降维（PCA）：选择最小的 pca_dim，使得前 pca_dim 个主成分的累计解释方差不小于 0.95。若不需要降维，则保留原始标准化后的全部维度。
3. 选择 k：从候选集合 k_list 中枚举每个 k，在训练集上训练 KMeans(n_clusters=k, random_state=42, n_init=10)，并计算训练集的 silhouette_score。若 k=1、k 非法，或轮廓系数无法计算，则该 k 的得分记为 -1。取得分最高的 k_star；若并列，取较小的 k。
4. 输出测试标签：使用 k_star 在训练集上重新拟合 KMeans，并对测试集执行 predict。直接输出 KMeans 的原生标签，不再重排。

输入格式

输入为一行字典，包含以下三个键：

• >
  train：训练特征，形如二维数组；
• >
  test：测试特征，形如二维数组；
• >
  k_list：候选聚类数列表。

允许数组元素中出现 NaN。若不同样本的列数不一致，则按最大列数对较短样本右侧补 NaN 后再统一处理。

输出格式

输出一个字典，包含三个键：

• >
  pca_dim：最终选中的 PCA 维度；
• >
  k_star：最优聚类数；
• >
  test_pred：与测试集行顺序对应的整型标签列表。

样例输入

{"train":[[0.0,0.0],[0.2,0.1],[5.0,5.1],[4.9,4.8]],"test":[[0.1,NaN],[5.2,4.9]],"k_list":[2,3]}

样例输出

{"pca_dim":1,"k_star":2,"test_pred":[0,1]}

数据范围

• >
  2 <= len(train) <= 200
• >
  1 <= len(test) <= 200
• >
  1 <= 最大列数 <= 20
• >
  2 <= k <= 8

题解

这题的难点不在某个单点算法，而在于三个步骤必须严格按题意衔接，否则答案很容易和标答不一致。

第一步是统一数据形状与缺失值处理。由于输入可能出现“某些样本列数更短”的情况，所以应先把所有样本补到相同列数，缺失位置都视为 NaN。接着只用训练集统计每一列的均值，并同时填充训练集和测试集。之后再用训练集 fit 一个 StandardScaler，把同一套标准化参数应用到训练集和测试集上。

第二步是确定 pca_dim。我们可以先在训练集标准化结果上做一次完整 PCA，拿到每个主成分的解释方差比，然后找到累计解释方差第一次达到 0.95 的位置。若这个位置已经等于原维度，就说明无需降维，后续直接使用标准化后的特征；否则再按该维度重新构造 PCA 并对训练集和测试集做同一投影。

第三步是从 k_list 中挑选 k_star。对每个候选 k：

• >
  若 k=1，轮廓系数无定义，直接记 -1；
• >
  若 k 大于样本数或 K-Means 训练失败，也记 -1；
• >
  否则在 PCA 后的训练集上训练 KMeans(k, random_state=42, n_init=10)；
• >
  如果最终只得到一个簇，或 silhouette_score 无法计算，同样记 -1；
• >
  能正常计算时，就用该轮廓系数作为分数。

最后选分数最高的 k，若分数相同取更小的 k。再用这个 k_star 重新拟合一次 KMeans，对测试集执行 predict 即可。

设训练集样本数为 n，测试集样本数为 m，维度为 d，候选个数为 s。由于这里的数据范围不大，整体复杂度主要来自：

• >
  预处理和标准化：O((n + m) d)
• >
  PCA：O(nd^2) 或 O(d^3) 量级（由库内部实现决定）
• >
  枚举 k：大约为 s 次 KMeans + silhouette_score

在本题给定规模下可以顺利通过。

参考代码

• >
  Python

import jsonimport sysimport numpy as npfrom sklearn.cluster import KMeansfrom sklearn.decomposition import PCAfrom sklearn.metrics import silhouette_scorefrom sklearn.preprocessing import StandardScalerinput = lambda: sys.stdin.readline().strip()defparse_payload(text):try:return json.loads(text)except Exception:        env = {"__builtins__": {},"NaN": float("nan"),"nan": float("nan"),"null": None,"None": None,"true": True,"false": False,        }return eval(text, env, {})defnormalize_matrix(rows):    rows = rows or []    width = 0for row in rows:        width = max(width, len(row))    matrix = []for row in rows:        cur = []for x in row:if x isNone:                cur.append(float("nan"))else:                cur.append(float(x))        cur.extend([float("nan")] * (width - len(cur)))        matrix.append(cur)return matrix, widthdefbuild_arrays(train_rows, test_rows):    train_norm, w1 = normalize_matrix(train_rows)    test_norm, w2 = normalize_matrix(test_rows)    width = max(w1, w2)defpad(rows):        result = []for row in rows:            cur = list(row)            cur.extend([float("nan")] * (width - len(cur)))            result.append(cur)return np.array(result, dtype=float)return pad(train_norm), pad(test_norm)defsolve():    payload = parse_payload(input())    train_raw = payload["train"]    test_raw = payload["test"]    k_list = [int(x) for x in payload["k_list"]]    train, test = build_arrays(train_raw, test_raw)# 仅用训练集均值填充缺失值；若整列都是 NaN，则回退为 0。    col_mean = np.nanmean(train, axis=0)    col_mean = np.where(np.isnan(col_mean), 0.0, col_mean)    train = np.where(np.isnan(train), col_mean, train)    test = np.where(np.isnan(test), col_mean, test)    scaler = StandardScaler()    train_scaled = scaler.fit_transform(train)    test_scaled = scaler.transform(test)    dim = train_scaled.shape[1]if dim == 0:        ans = {"pca_dim": 0,"k_star": min(k_list),"test_pred": [0] * len(test_scaled),        }        print(json.dumps(ans, separators=(",", ":")))return# 先完整拟合一次 PCA，用累计解释方差决定最终维度。    full_pca = PCA()    full_pca.fit(train_scaled)    ratio = np.nan_to_num(full_pca.explained_variance_ratio_, nan=0.0)    cum = np.cumsum(ratio)    pca_dim = dimfor i, val in enumerate(cum, start=1):if val >= 0.95:            pca_dim = ibreakif pca_dim < dim:        pca = PCA(n_components=pca_dim)        train_feat = pca.fit_transform(train_scaled)        test_feat = pca.transform(test_scaled)else:        train_feat = train_scaled        test_feat = test_scaled    best_score = -2.0    k_star = None    n = len(train_feat)for k in sorted(k_list):        score = -1.0if2 <= k <= n:try:                model = KMeans(n_clusters=k, random_state=42, n_init=10)                labels = model.fit_predict(train_feat)                unique_cnt = len(set(int(x) for x in labels))if2 <= unique_cnt < n:                    score = float(silhouette_score(train_feat, labels))except Exception:                score = -1.0if score > best_score or (abs(score - best_score) <= 1e-12and (k_star isNoneor k < k_star)):            best_score = score            k_star = k    model = KMeans(n_clusters=k_star, random_state=42, n_init=10)    test_pred = model.fit(train_feat).predict(test_feat)    ans = {"pca_dim": int(pca_dim),"k_star": int(k_star),"test_pred": [int(x) for x in test_pred.tolist()],    }    print(json.dumps(ans, separators=(",", ":")))if __name__ == "__main__":    solve()

题目4：子集口令求和

问题描述

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

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

的下标  对应权重之和。

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

请回答所有查询。

输入格式

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

对于每组数据：

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

输出格式

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

样例输入

35 31 2 3 4 50 7 53 210 -5 73 26 30 1 2 3 4 56 4 7

样例输出

0151012-59315

数据范围

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

题解

如果对每次查询都暴力枚举所有下标 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 sysinput = lambda: sys.stdin.readline().strip()defsolve():    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 else0)        f = [0] * (m + 1)# 把下标对应的权重放进初始状态。for i in range(1, n + 1):            f[i] = a[i]        bit = 0while (1 << bit) <= m:            step = 1 << bitfor mask in range(m + 1):if mask & step:                    f[mask] += f[mask ^ step]            bit += 1for x in xs:            out.append(str(f[x]))    print("\n".join(out))if __name__ == "__main__":    solve()

• >
  Cpp

#includeusingnamespacestd;using int64 = longlong;intmain(){    ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--) {int n, q;cin >> n >> q;vectora(n + 1);for (int i = 1; i <= n; i++) {cin >> a[i];        }vectorxs(q);int mx = n;for (int i = 0; i < q; i++) {cin >> xs[i];            mx = max(mx, xs[i]);        }vectorf(mx + 1, 0);for (int i = 1; i <= n; i++) {            f[i] = a[i];        }for (int bit = 0; (1 << bit) <= mx; bit++) {int step = 1 << bit;for (int mask = 0; mask <= mx; mask++) {if (mask & step) {                    f[mask] += f[mask ^ step];                }            }        }for (int x : xs) {cout << f[x] << '\n';        }    }return0;}

• >
  Java

import java.io.BufferedInputStream;publicclassMain{staticclassFastScanner{privatefinalbyte[] buffer = newbyte[1 << 16];privateint ptr = 0, len = 0;privatefinal BufferedInputStream in = new BufferedInputStream(System.in);privateintread()throws Exception {if (ptr >= len) {                len = in.read(buffer);                ptr = 0;if (len <= 0) {return -1;                }            }return buffer[ptr++];        }longnextLong()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;        }    }publicstaticvoidmain(String[] args)throws Exception {        FastScanner fs = new FastScanner();int T = (int) fs.nextLong();        StringBuilder out = new StringBuilder();while (T-- > 0) {int n = (int) fs.nextLong();int q = (int) fs.nextLong();long[] a = newlong[n + 1];for (int i = 1; i <= n; i++) {                a[i] = fs.nextLong();            }int[] xs = newint[q];int mx = n;for (int i = 0; i < q; i++) {                xs[i] = (int) fs.nextLong();if (xs[i] > mx) {                    mx = xs[i];                }            }long[] f = newlong[mx + 1];for (int i = 1; i <= n; i++) {                f[i] = a[i];            }for (int bit = 0; (1 << bit) <= mx; bit++) {int step = 1 << bit;for (int mask = 0; mask <= mx; mask++) {if ((mask & step) != 0) {                        f[mask] += f[mask ^ step];                    }                }            }for (int x : xs) {                out.append(f[x]).append('\n');            }        }        System.out.print(out);    }}