大厂真题 / 携程

携程 4.12 笔试真题 - 算法岗

本场考试概述

考试时间：2026年4月12日 考试岗位：算法岗 难度评级：中等

考点分析：

1. 第一题：构造（难度简单）
2. 第二题：贪心（难度中等）
3. 第三题：NumPy 归一化梯度下降（难度中等）
4. 第四题：数学递推 + 快速幂（难度中等）

建议策略：

• 第一、四题为数学/构造型，找规律是关键，拿满分的重点
• 第二题贪心需要发现”翻转只影响两个边界”的关键观察
• 第三题 ML 题按公式实现即可，注意梯度归一化的数值稳定性

第一题：合数求解

题目描述

给定一个正整数 n，请找到两个正整数 x 和 y，使得 x + y = 2n，并且 x 与 y 都是合数（x 与 y 可以相等）。

若无法找到这样的 x 和 y，则输出 -1。

合数指大于 1 且不是质数的正整数；1 不是合数。

输入格式：第一行一个整数 T 表示数据组数，接下来 T 行每行一个整数 n。

输出格式：每组测试数据输出一行，若存在解，输出两个用空格分隔的正整数 x 和 y；若存在多组解可输出任意一组；若不存在则输出 -1。

样例

输入

3
1
4
7

输出

-1
4 4
6 8

思路分析

第一步：分析合数的最小值。最小的合数是 4（= 2 x 2）。两个合数之和最少是 4 + 4 = 8，也就是说 2n >= 8 即 n >= 4 时才可能有解。当 n < 4 时（即 2n < 8），无论怎么拆都凑不出两个合数，直接输出 -1。

第二步：构造 n >= 4 的解。当 n >= 4 时，令 x = 4，y = 2n - 4。y 是偶数且 y >= 4（因为 2n >= 8），任何大于等于 4 的偶数都能被 2 整除且大于 1，所以必定是合数。x = 4 本身也是合数。因此 (4, 2n - 4) 一定是一组合法解。

第三步：验证边界。当 n = 1, 2, 3 时，2n = 2, 4, 6，尝试所有拆法均无法让两边都是合数，确认输出 -1 即可。

这道题的关键在于发现构造法：固定一个最小合数 4，另一个数自然也是偶合数。

题解代码

import sys
input = sys.stdin.readline

def solve(n):
    # n<4 时 2n<8，无法拆成两个合数
    if n < 4:
        return "-1"
    # x=4(合数), y=2n-4(偶数且>=4，必为合数)
    return f"4 {2 * n - 4}"

T = int(input())
for _ in range(T):
    n = int(input())
    print(solve(n))

复杂度分析

时间复杂度：O(1)，每组查询常数时间完成。 空间复杂度：O(1)，无需额外空间。

第二题：灯带相融度最大化

题目描述

有一条由 n 个灯珠组成的灯带，每个灯珠有两种状态：0 或 1。灯带上相邻灯珠之间的焊点具有权重 w[i]（对应第 i 个灯珠与第 i+1 个灯珠之间的焊点）。定义灯带的”相融度”为所有相邻灯珠状态相同的焊点权重之和。

你可以进行至多一次翻转操作：选择一个连续段 [l, r]，将该段内的每个灯珠状态 0 与 1 互换。也可以不进行任何操作。请计算操作后灯带相融度的最大值。

输入格式：第一行输入整数 n 表示灯珠数量；第二行输入一个长度为 n 的二进制字符串，第 i 个字符表示第 i 个灯珠的初始状态；第三行输入 n-1 个整数，表示各相邻对之间的焊点权重。

输出格式：输出一个整数，表示至多一次翻转操作后相融度的最大值。

样例

输入

5
01010
2 1 3 4

输出

7

思路分析

第一步：理解翻转操作的本质。翻转连续段 [l, r] 时，段内的相邻对两边同时被翻转，同/异关系不变。真正发生变化的只有两个”边界缝隙”：位置 l-1 和 l 之间、位置 r 和 r+1 之间。因为边界处一侧被翻了、另一侧没翻，原来相同的变成不同，原来不同的变成相同。

第二步：定义翻转增益。对每个相邻位置 i（即第 i 个灯珠和第 i+1 个灯珠之间），定义增益 d[i]：

• 如果 s[i] != s[i+1]（当前状态不同），边界经过这里会把”不同”变”相同”，增益为 +w[i]
• 如果 s[i] == s[i+1]（当前状态相同），边界经过这里会把”相同”变”不同”，增益为 -w[i]

第三步：贪心选择。一次翻转操作最多改变两个边界位置，总增益就是选出的两个 d 值之和。如果翻转区间从头开始或到尾结束，只影响一个边界。因此答案为初始相融度 + max(0, top1, top1 + top2)，其中 top1 和 top2 是增益数组的最大值和次大值。

第四步：一趟遍历完成。遍历所有 n-1 个相邻位置，同时累加初始相融度、计算增益、维护最大和次大增益值。

题解代码

import sys
input = sys.stdin.readline

def solve(n, s, w):
    base = 0
    top1 = top2 = float('-inf')
    for i in range(n - 1):
        if s[i] != s[i + 1]:
            d = w[i]           # 不同→翻转后变相同，增益为正
        else:
            base += w[i]       # 相同→计入初始相融度
            d = -w[i]          # 翻转后变不同，增益为负
        # 维护最大和次大增益值
        if d >= top1:
            top2 = top1
            top1 = d
        elif d > top2:
            top2 = d
    best = 0
    if top1 != float('-inf'):
        best = max(best, top1)
    if top2 != float('-inf'):
        best = max(best, top1 + top2)
    return base + best

n = int(input())
s = input().strip()
w = list(map(int, input().split()))
print(solve(n, s, w))

复杂度分析

时间复杂度：O(n)，只需一次遍历。 空间复杂度：O(n)，存储权重数组。

第三题：NGD 优化器实现

题目描述

仅使用 NumPy，手写实现一种简化变体优化器 NGD（Normalized Gradient Descent）。

与标准梯度下降不同，NGD 先把梯度归一化为单位 L2 向量，再按衰减学习率更新。具体公式为：

• 梯度归一化：g_hat = grad /

  grad

• 学习率衰减：eta_t = eta0 / sqrt(t)
• 参数更新：w = w - eta_t * g_hat

其中 eta0 = 0.2，正则系数 lambda = 0.01，迭代次数 T = 60。

输入格式：单行 JSON，包含 train_X（n x d 矩阵）、train_y（长度 n 的实数向量）、test_X（m x d 矩阵）。

输出格式：仅一行 JSON，包含 weights（长度 d，保留 6 位小数）和 test_pred（长度 m，值为 0 或 1）。

样例

输入

{"train_X":[[0,0],[0.2,0.1],[0.1,-0.1],[4,4],[4.1,3.9]],"train_y":[0,0,0,1,1],"test_X":[[0.05,0.05],[4.05,4.05]]}

输出

{"weights":[0.075281,0.138912],"test_pred":[1,1]}

思路分析

第一步：理解 NGD 与普通梯度下降的区别。普通 GD 直接用梯度乘学习率更新参数，梯度大时步长大、梯度小时步长小。NGD 先把梯度归一化为长度为 1 的单位向量，再乘学习率更新。这意味着不管原始梯度有多大，每步走的距离只取决于学习率。好处是对梯度爆炸/消失更鲁棒。

第二步：梯度计算。使用带 L2 正则项的线性回归损失。残差 r = Xw - y，梯度 grad = X^T @ r + 2 * lambda * w。X^T @ r 把 n 个样本的残差”汇总”到 d 个维度上，正则项 2 * lambda * w 防止权重过大。

第三步：归一化与数值稳定性。将梯度除以其 L2 范数得到单位向量 g_hat。如果梯度范数接近零（小于 1e-10）或出现 NaN/Inf，直接跳过本轮更新，避免除以零导致数值爆炸。

第四步：学习率衰减与预测。第 t 步的学习率 eta_t = 0.2 / sqrt(t)，随迭代次数递减。迭代 60 步后，对测试集做线性预测：test_X @ w >= 0 判为 1，否则判为 0。

题解代码

import json
import numpy as np

data = json.loads(input())
X = np.array(data["train_X"])       # (n, d)
y = np.array(data["train_y"])       # (n,)
X_test = np.array(data["test_X"])   # (m, d)

n, d = X.shape
eta0, lam, T, eps = 0.2, 0.01, 60, 1e-10
w = np.zeros(d)                     # 初始权重全零

for t in range(1, T + 1):
    # 梯度: X^T(Xw - y) + 2*lambda*w
    grad = X.T @ (X @ w - y) + 2 * lam * w
    grad_norm = np.linalg.norm(grad)
    # 梯度范数过小或含非有限值时跳过更新
    if grad_norm < eps or not np.all(np.isfinite(grad)):
        continue
    g_hat = grad / max(grad_norm, eps)  # 归一化为单位向量
    w = w - (eta0 / np.sqrt(t)) * g_hat

# 预测: Xw >= 0 判为1，否则判为0
pred = (X_test @ w >= 0).astype(int).tolist()
weights = [round(float(v), 6) for v in w]
print(json.dumps({"weights": weights, "test_pred": pred}), end='')

复杂度分析

时间复杂度：O(T * n * d)，每步一次矩阵向量乘法，T = 60。 空间复杂度：O(n * d)，存储训练矩阵。

第四题：数字分裂求和

题目描述

给定一个初始值为 n 的数字。每一秒，当前所有的数字都会同时执行分裂操作：记分裂的数字为 x，它会分裂成两个数字 floor(x/2) + 1 和 floor(x/2) + 1（即两个相同的值）；此外，如果 x 为奇数，它还会额外分裂出一个数字 1。

操作结束后，原数字 x 被移除，仅保留新生成的数字。求经过 m 秒后，所有数字的总和。由于答案可能很大，请将结果对 10^9 + 7 取模后输出。

输入格式：第一行一个整数 T 代表数据组数，每组测试数据一行输入两个整数 n 和 m。

输出格式：每组数据输出一行，表示最终结果对 10^9 + 7 取模后的值。

样例

输入

2
1 3
11 2

输出

32
20

思路分析

第一步：建立递推关系。设 S(x, t) 为从单个数字 x 出发，经过 t 步后所有数字的总和。每个 x 分裂成两个 floor(x/2) + 1，如果 x 是奇数还多出一个 1。因此：

• 偶数 x：S(x, t) = 2 * S(x/2 + 1, t-1)
• 奇数 x：S(x, t) = 2 * S((x-1)/2 + 1, t-1) + S(1, t-1)

其中 S(1, t-1) 就是从 1 出发经过 t-1 步的总和。

第二步：发现不动点。观察 x = 2 时：floor(2/2) + 1 = 2，分裂成两个 2，总和翻倍。所以 S(2, t) = 2^t * 2。对于 x = 1（奇数）：分裂成两个 1 和一个额外的 1，共三个 1，但实际 floor(1/2) + 1 = 1，分裂成两个 1 加一个额外的 1。即 S(1, t) = 3 * S(1, t-1) = 3^t？不对，需要更仔细分析。

实际上关键发现是：对任何 x，反复做 x -> floor(x/2) + 1 这个变换，在 O(log n) 步内就会收敛到不动点 2。

第三步：链式追踪。从 n 出发，追踪变换链 x -> floor(x/2) + 1，记录路上遇到多少个奇数（记为 count_odd）。每遇到一个奇数就会多分裂出一个 1，而每个 1 经过剩余步数后贡献 S(1, 剩余步数)。

展开递推式可以证明：如果链在 steps 步内到达不动点 2，答案为 (count_odd + 2) * 2^m。如果 m 步内还没到达 2，当前值为 x，答案为 (x + count_odd) * 2^m。用快速幂 pow(2, m, MOD) 计算大幂次。

第四步：验证样例。以 n=11, m=2 为例：

• 第 1 步：11 是奇数，count_odd=1，x = 11//2 + 1 = 6
• 第 2 步：6 是偶数，x = 6//2 + 1 = 4
• 用完 m=2 步，未到达 2，答案 = (4 + 1) * 2^2 = 5 * 4 = 20

题解代码

import sys
input = sys.stdin.readline

def solve(n, m):
    MOD = 10**9 + 7
    x = n
    count_odd = 0
    steps = 0
    # 链长 O(log n)，最多约60步就会到达不动点2
    while x != 2 and steps < m:
        if x % 2 == 1:
            count_odd += 1
        x = x // 2 + 1
        steps += 1
    pow2m = pow(2, m, MOD)
    if x == 2:
        # 已到达不动点，答案 = (count_odd + 2) * 2^m
        return (count_odd + 2) % MOD * pow2m % MOD
    else:
        # 未到达不动点，答案 = (x + count_odd) * 2^m
        return (x % MOD + count_odd % MOD) % MOD * pow2m % MOD

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

复杂度分析

时间复杂度：O(log n)，每组查询链追踪最多 O(log n) 步，快速幂 O(log m)。 空间复杂度：O(1)，只用常数变量。

小结

• 第一题是纯构造签到题，关键在于发现最小合数为 4，令 x=4 则 y=2n-4 必为合数
• 第二题贪心的核心观察是：翻转连续段只改变两个边界位置的贡献，取增益最大的两个边界即可
• 第三题是 ML 实现题，按 NGD 公式迭代即可，注意梯度为零时跳过更新保证数值稳定
• 第四题数学递推：利用 x -> floor(x/2) + 1 在 O(log n) 步内收敛到不动点 2 的性质，将问题转化为链式追踪 + 快速幂