大厂真题 / 美团

美团 4.11 笔试真题 - 算法岗

本场考试概述

考试时间：2026年4月11日 考试岗位：算法岗 难度评级：困难

考点分析：

第一题：分类讨论（难度中等）
第二题：IRLS 逻辑回归（难度中等，ML实现题）
第三题：组合数学 + 容斥原理（难度困难）
第四题：函数图环检测 + 前缀和（难度困难）

建议策略：

第一题先做，属于常规分类枚举
第二题考 ML 基础，需熟悉 IRLS 迭代公式和 NumPy 向量化实现
第三题和第四题难度较高，考场上能部分得分即可

第一题：两两成盒

题目描述

给定长度为 n 的整数数组 a。按顺序将相邻元素两两成”盒”。恰好选择 x 个盒，从每个被选的盒中选出一个数字，使得所有被选数字的和为奇数。判断是否可行。

样例

输入

输出

Yes
Yes
No

思路分析

总和的奇偶性只取决于选出的奇数个数的奇偶性。将盒子分为三类：仅含奇数（only_odd）、仅含偶数（only_even）、奇偶兼有（flexible）。枚举 only_odd 的选取数量，若用到 flexible 盒子可自由调整奇偶，否则需要 only_odd 选取数量为奇数。

题解代码

import sys
input = sys.stdin.readline

def solve(n, x, arr):
    only_odd = only_even = flexible = 0
    for i in range(0, n, 2):
        p1 = arr[i] % 2
        if i + 1 < n:
            p2 = arr[i + 1] % 2
            if p1 == 1 and p2 == 1:
                only_odd += 1
            elif p1 == 0 and p2 == 0:
                only_even += 1
            else:
                flexible += 1
        else:
            if p1 == 1:
                only_odd += 1
            else:
                only_even += 1

    total_boxes = only_odd + only_even + flexible
    if x > total_boxes:
        return "No"

    for a in range(min(only_odd, x) + 1):
        remain = x - a
        b_min = max(0, remain - flexible)
        b_max = min(only_even, remain)
        if b_min > b_max:
            continue
        c_max = remain - b_min
        if c_max >= 1:
            return "Yes"
        if a % 2 == 1:
            return "Yes"
    return "No"

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

复杂度分析

时间复杂度：O(n)。 空间复杂度：O(n)。

第二题：小美的优惠券预测模型

题目描述

使用 IRLS（迭代重加权最小二乘）实现逻辑回归，对测试样本给出类别预测。训练特征矩阵拼接截距列，收敛判据为权重变化量 < 10^-6 或迭代 30 次。

样例

输入

{"train":[[1,2,0],[2,1,8,0],[5,5,1],[4,5,5,2,1]],"test":[[1,5,1,9],[5,5,1]]}

输出

[0, 1]

思路分析

第一步：理解 IRLS

IRLS 是牛顿法的一种——每一步不仅看梯度方向，还利用 Hessian 矩阵的曲率信息决定步长，收敛比普通梯度下降快得多。

第二步：迭代公式

每轮计算预测概率 p = sigmoid(Xw)，梯度 g = X^T(p-y)，Hessian H = X^T W X + εI（W 为对角权重 p(1-p)），更新 δ = solve(H, g)，w = w - δ。

第三步：数据对齐

输入为不定长列表。关键：必须采用右对齐——短行从左侧补零，确保每行最后一个元素始终是标签。pd.DataFrame 默认左对齐会导致短行的标签被错放到中间列，最后一列变成填充的零。右对齐后，标签恒在最右列，缺失的是靠前的特征（补零合理）。

题解代码

import json
import numpy as np

line = input()
data = json.loads(line)

train_raw = data["train"]
test_raw = data["test"]

# 右对齐：短行左侧补零，保证最后一个元素恒为标签
max_len = max(len(r) for r in train_raw)
train_mat = np.zeros((len(train_raw), max_len))
for i, r in enumerate(train_raw):
    train_mat[i, max_len - len(r):] = r

X_train = train_mat[:, :-1]
y = train_mat[:, -1]
n, d = X_train.shape

# 测试集同样右对齐到 d 维特征
X_test = np.zeros((len(test_raw), d))
for i, r in enumerate(test_raw):
    L = min(len(r), d)
    X_test[i, d - L:] = r[-L:]

# 拼接截距列
X = np.hstack([np.ones((n, 1)), X_train])
m = d + 1
X_test_aug = np.hstack([np.ones((X_test.shape[0], 1)), X_test])

# IRLS 迭代
w = np.zeros(m)
eps = 1e-8

for _ in range(30):
    z = np.clip(X @ w, -500, 500)
    p = 1.0 / (1.0 + np.exp(-z))
    W_diag = p * (1.0 - p)
    H = (X.T * W_diag) @ X + eps * np.eye(m)
    g = X.T @ (p - y)
    delta = np.linalg.solve(H, g)
    w_new = w - delta
    if np.linalg.norm(w_new - w) < 1e-6:
        w = w_new
        break
    w = w_new

z_test = np.clip(X_test_aug @ w, -500, 500)
p_test = 1.0 / (1.0 + np.exp(-z_test))
y_pred = (p_test >= 0.5).astype(int).tolist()
print(json.dumps(y_pred))

复杂度分析

时间复杂度：O(iter * (m * n + m^3))，每轮矩阵乘法 O(mn) 和线性系统求解 O(m^3)。 空间复杂度：O(m * n)。

第三题：数序列(二)

题目描述

给定 n, v, m, k，统计长度为 n、值域 [1,v] 的序列中，存在至少一个长度为 m 的子段和不等于 k 的个数，对 10^9+7 取模。

样例

输入

输出

思路分析

第一步：补集转化

正面计数困难，反面简单。答案 = 总数 - bad，其中 bad 为”所有长 m 子段和恒等于 k”的序列数。

第二步：bad 的结构分析

若所有相邻长 m 窗口和都为 k，相邻窗口差分得 a[i] = a[i+m]，即序列以 m 为周期。因此 bad 序列完全由前 m 个元素决定，且要求 a[1]+…+a[m] = k，每个 a[i] 在 [1,v]。

第三步：容斥计数

令变量 b[i] = a[i]-1，问题化为 b[1]+…+b[m] = k-m 的非负整数解数（每个 b[i] <= v-1）。用容斥原理扣掉超出上界的方案，结合组合数公式和模逆元计算。

题解代码

import sys
input_data = sys.stdin.read().split()
idx = 0

MOD = 10**9 + 7

def power(base, exp):
    result = 1
    base %= MOD
    while exp > 0:
        if exp & 1:
            result = result * base % MOD
        base = base * base % MOD
        exp >>= 1
    return result

def solve(n, v, m, k):
    if n < m:
        return 0
    total = power(v, n)
    if v == 1:
        bad = 1 if k == m else 0
        return (total - bad + MOD) % MOD

    S = k - m
    if S < 0 or S > (v - 1) * m:
        return total

    r = m - 1
    fact_r = 1
    for i in range(1, r + 1):
        fact_r = fact_r * i % MOD
    inv_fact_r = power(fact_r, MOD - 2)

    J = min(m, S // v)
    bad = 0
    c_m_j = 1

    for j in range(J + 1):
        N = k - 1 - j * v
        if N < r:
            break
        ff = 1
        for i in range(r):
            ff = ff * ((N - i) % MOD) % MOD
        c_n_r = ff * inv_fact_r % MOD

        term = c_m_j * c_n_r % MOD
        if j % 2 == 0:
            bad = (bad + term) % MOD
        else:
            bad = (bad - term + MOD) % MOD

        c_m_j = c_m_j * ((m - j) % MOD) % MOD * power(j + 1, MOD - 2) % MOD

    return (total - bad + MOD) % MOD

T = int(input_data[idx]); idx += 1
out = []
for _ in range(T):
    n = int(input_data[idx]); idx += 1
    v = int(input_data[idx]); idx += 1
    m = int(input_data[idx]); idx += 1
    k = int(input_data[idx]); idx += 1
    out.append(str(solve(n, v, m, k)))
print('\n'.join(out))

复杂度分析

时间复杂度：O(m)，每组数据容斥枚举最多 m 项。 空间复杂度：O(1)。

第四题：我即唯一

题目描述

n 个城市，每个城市有唯一后继。从城市 p 出发共”来到城市” k 次，第 t 次来到城市 v 获得 v*t 的价值。对 q 个询问计算总价值对 10^9+7 取模。

样例

输入

输出

1
12
18

思路分析

每个城市出度为 1 的函数图形成 ρ 形结构：一条尾部链接一个环。预处理所有环结构和环上前缀和，每次查询将路径拆分为尾部和环部分。环上前 rem 个城市被访问 full+1 次，其余被访问 full 次，利用等差数列求和公式和 2 的模逆元计算贡献。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    MOD = 10**9 + 7
    inv2 = pow(2, MOD - 2, MOD)

    color = [0] * (n + 1)
    on_cycle = [False] * (n + 1)
    cycles = []
    node_cycle = {}

    for start in range(1, n + 1):
        if color[start] != 0:
            continue
        path = []
        node = start
        while color[node] == 0:
            color[node] = 1
            path.append(node)
            node = a[node - 1]
        if color[node] == 1:
            idx = next(i for i, v in enumerate(path) if v == node)
            cycle = path[idx:]
            cid = len(cycles)
            cycles.append(cycle)
            for j, v in enumerate(cycle):
                on_cycle[v] = True
                node_cycle[v] = (cid, j)
                color[v] = 2
            for v in path[:idx]:
                color[v] = 2
        else:
            for v in path:
                color[v] = 2

    cycle_prefix = []
    cycle_total = []
    for cycle in cycles:
        L = len(cycle)
        prefix = [0] * (L + 1)
        for j in range(L):
            prefix[j + 1] = (prefix[j] + cycle[j]) % MOD
        cycle_prefix.append(prefix)
        cycle_total.append(prefix[L])

    def cycle_range_sum(cid, sp, length):
        if length == 0:
            return 0
        L = len(cycles[cid])
        ep = sp + length
        if ep <= L:
            return (cycle_prefix[cid][ep] - cycle_prefix[cid][sp]) % MOD
        return (cycle_prefix[cid][L] - cycle_prefix[cid][sp] + cycle_prefix[cid][ep - L]) % MOD

    out = []
    for _ in range(q):
        p, k = map(int, input().split())
        tail_sum = 0
        tail_len = 0
        node = p
        while not on_cycle[node]:
            tail_sum += node
            tail_len += 1
            if tail_len == k:
                break
            node = a[node - 1]

        if tail_len >= k:
            out.append(str(tail_sum % MOD))
            continue

        remaining = k - tail_len
        cid, sp = node_cycle[node]
        L = len(cycles[cid])
        full = remaining // L
        rem = remaining % L
        S = cycle_total[cid]
        S_r = cycle_range_sum(cid, sp, rem)
        f = full % MOD
        cf = S_r * ((f + 1) % MOD) % MOD * ((f + 2) % MOD) % MOD * inv2 % MOD
        S_rest = (S - S_r) % MOD
        cb = S_rest * (f % MOD) % MOD * ((f + 1) % MOD) % MOD * inv2 % MOD
        ans = (tail_sum + cf + cb) % MOD
        out.append(str(ans))

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

solve()

复杂度分析

时间复杂度：O(n + q * tail_length)。 空间复杂度：O(n)。

小结

第一题分类讨论，将盒子分为仅奇、仅偶、灵活三类判断可行性
第二题 IRLS 逻辑回归是 ML 实现题，牛顿法迭代配合 NumPy 向量化高效求解
第三题容斥原理，补集转化后利用周期性结构将 bad 计数归结为带上界的组合数问题
第四题函数图环检测 + 前缀和，三色标记法找环后利用等差数列求和公式计算贡献

这篇文章有帮助吗？

| GitHub 留言