大厂真题 / 美团

美团 4.11 笔试真题 - 研发岗

本场考试概述

考试时间：2026年4月11日 考试岗位：研发岗 难度评级：中等偏难

考点分析：

第一题：分类讨论（难度中等）
第二题：字符串构造（难度简单）
第三题：函数图环检测 + 前缀和（难度困难）

建议策略：

第一题分类枚举，仔细分析三类盒子的奇偶性贡献
第二题直接构造，掌握”交替段 + 填充段”思路即可
第三题是难点，需要掌握 ρ 形函数图的环检测技巧和取模运算的逆元写法

第一题：两两成盒

题目描述

给定长度为 n 的整数数组 a。按顺序将相邻元素两两成”盒”：盒 1 为 (a[1], a[2])，盒 2 为 (a[3], a[4])，以此类推；若 n 为奇数，最后一个盒为单元素盒。

恰好选择 x 个盒，从每个被选的盒中选出一个数字，使得所有被选数字的和为奇数。判断是否可行。

样例

输入

输出

Yes
Yes
No

思路分析

第一步：观察题目性质

总和的奇偶性只取决于选出的奇数个数的奇偶性——需要选出奇数个奇数。每个盒子能贡献的奇偶性由其内部元素决定。

第二步：分类讨论

将每个盒子分为三类：仅含奇数（only_odd）、仅含偶数（only_even）、奇偶兼有（flexible）。对于双元素盒，两个元素奇偶性相同则归入对应 only 类，不同则归入 flexible 类。

第三步：枚举判断

枚举从 only_odd 中选 a 个盒子，剩余从 only_even 和 flexible 中选取。若用到了 flexible 盒子，可以自由调整奇偶贡献，直接可行；若没有 flexible 盒子，奇数个数固定为 a，a 必须为奇数。

题解代码

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
        # 有 flexible 盒子就能调整奇偶
        if c_max >= 1:
            return "Yes"
        # 没有 flexible，奇数个数固定为 a
        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)，存储输入数组。

第二题：最长非重复子串

题目描述

定义字符串的”奇怪度”为其最长非重复子串的数量（按起止位置计数）。给定整数 n 和 k，构造长度为 n、仅由小写字母组成的字符串，使其奇怪度恰好为 k。

非重复子串：每个字符出现次数不超过 1 的子串。

样例

输入

5 3

输出

abaab

思路分析

第一步：分析极端情况

若所有字符相同（如 “aaa…a”），最长非重复子串长度为 1，数量等于 n。若使用交替模式（如 “abab…“），最长非重复子串长度为 2，每对相邻不同字符都是一个。

第二步：构造策略

当 k == n 时，输出全同字符串。当 k < n 时，令前 k+1 个字符按 “ababab…” 交替排列，剩余字符填充为与交替段末尾相同的字符。只用了 a 和 b 两种字符，任何长度 >= 3 的子串必然包含重复字母（鸽巢原理），因此最长非重复子串长度为 2。交替段中恰好有 k 个这样的子串。

题解代码

def solve(n, k):
    if k == n:
        return 'a' * n
    s = []
    length = min(k + 1, n)
    for i in range(length):
        s.append('a' if i % 2 == 0 else 'b')
    # 剩余填充最后一个字符
    pad = s[-1]
    s.extend([pad] * (n - length))
    return ''.join(s)

n, k = map(int, input().split())
print(solve(n, k))

复杂度分析

时间复杂度：O(n)，构造字符串需遍历 n 个位置。 空间复杂度：O(n)，存储结果字符串。

第三题：我即唯一

题目描述

n 个城市，每个城市有唯一后继 a[i]。从城市 p 出发，共”来到城市” k 次（含起点）。第 t 次来到城市 v 获得 v * t 的价值。对 q 个询问 (p, k)，计算总价值对 10^9+7 取模的结果。

样例

输入

输出

1
12
18

思路分析

第一步：观察题目性质

每个城市只有一个后继（出度为 1 的函数图），从任意起点出发一直走，最终一定会进入一个环。路径形状像希腊字母 ρ：一条链（尾部）接一个圆圈（环）。

第二步：问题转化

预处理所有环结构和环上前缀和。每次查询将路径拆分为尾部（进入环前的链）和环部分，分别计算贡献。

第三步：贡献计算

城市 v 被访问 c 次，第 t1, t2, …, tc 次访问的总贡献为 v * (t1 + t2 + … + tc) = v * c*(c+1)/2（等差数列求和）。环上前 rem 个城市各被访问 full+1 次，其余城市各被访问 full 次。除以 2 在取模下通过乘 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)，每次查询 O(尾部长度)。 空间复杂度：O(n)，存储图、环信息和前缀和数组。

小结

第一题分类讨论，将盒子分为仅奇、仅偶、灵活三类，枚举固定奇数盒数量判断可行性
第二题字符串构造，交替段控制最长非重复子串数量，填充段补齐长度
第三题函数图环检测 + 前缀和是本场难点，三色标记法找环后利用等差数列求和公式和模逆元高效计算贡献

这篇文章有帮助吗？

| GitHub 留言