大厂真题 / 米哈游

米哈游 4.19 笔试真题 - 暑期实习

本场考试概述

考试时间：2026年4月19日 考试岗位：暑期实习（通用技术岗） 难度评级：中等偏难

考点分析：

第一题：象限计数（难度中等）
第二题：构造 + 同余拆分（难度中等偏难）
第三题：单调栈 + 配对计数（难度中等）

建议策略：

第一题理解”最短路径覆盖矩形区域”的几何含义后，按四个象限分类计数即可，优先拿满分
第二题关键是推导出最小和条件，构造时取前 k-1 个最小值、最后一个用余量补齐
第三题单调栈模型需要仔细分析弹栈时的配对条件，每个元素最多入栈出栈各一次，O(n) 解决

第一题：快递投递

题目描述

二维网格上有 n 个人，各自位于整数坐标点。你需要选一个整数坐标点放置快递站。每天从快递站走一条到原点 (0,0) 的最短路径送快递。从 (X,Y) 到 (0,0) 的最短路径会经过它们所确定的矩形区域中的所有点（每步只能沿 x 或 y 方向走一格）。经过多天选择不同的最短路径，可以覆盖到这个矩形中的所有整数点。

一个人被”投递到”当且仅当某天的路径经过他所在的点。请选择快递站位置，使得能投递到的不同人数最大化，输出这个最大值。

多组测试数据，第一行输入 T（所有测试数据的 n 之和不超过 200000），每组先输入 n，再输入 n 行坐标。

样例

输入

输出

5
5
3

思路分析

第一步：理解最短路径的覆盖范围

从点 (X, Y) 走到原点 (0, 0) 的最短路径，需要总共走

步。以 X >= 0, Y >= 0（第一象限）为例，每步要么向左走一格要么向下走一格。所有最短路径的集合，恰好覆盖矩形 [0, X] x [0, Y] 中所有可达的格点。

关键观察：如果快递站放在第一象限足够远的位置 (X, Y)，那么经过多天走不同的最短路径，可以覆盖 [0, X] x [0, Y] 中的所有整数点。因此，第一象限内的所有人都能被投递到。

第二步：推广到四个象限

同理：

快递站在第二象限 (x <= 0, y >= 0)：覆盖 [X, 0] x [0, Y]，即第二象限所有人
快递站在第三象限 (x <= 0, y <= 0)：覆盖 [X, 0] x [Y, 0]，即第三象限所有人
快递站在第四象限 (x >= 0, y <= 0)：覆盖 [0, X] x [Y, 0]，即第四象限所有人

只需将快递站放到选定象限的足够远处，就能覆盖该象限的所有人。

第三步：处理坐标轴上的点

在坐标轴上的点属于相邻的两个象限。例如：

x 轴正半轴上的点 (x > 0, y = 0)：同时属于第一象限和第四象限
y 轴正半轴上的点 (x = 0, y > 0)：同时属于第一象限和第二象限
原点 (0, 0)：属于所有四个象限

因此在计数时，每个人可以贡献给多个象限（用 if 而非 elif）。

第四步：求解

分别统计四个象限中的人数，取最大值即为答案。

以样例 1 为例：

第一象限 (x >= 0, y >= 0)：(5,5), (3,3), (2,1), (1,0), (4,4) 共 5 人（(1,0) 在 x 轴上也算），(-2,5) 不算
第二象限 (x <= 0, y >= 0)：(-2,5), (0,0) 方向无匹配… 实际 (-2,5) 满足 x<=0, y>=0 计 1 人，(1,0) 中 x>0 不算
答案 = max(5, …) = 5

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    # 四个象限计数：Q1(x>=0,y>=0), Q2(x<=0,y>=0), Q3(x<=0,y<=0), Q4(x>=0,y<=0)
    q1 = q2 = q3 = q4 = 0
    for _ in range(n):
        x, y = map(int, input().split())
        if x >= 0 and y >= 0:
            q1 += 1
        if x <= 0 and y >= 0:
            q2 += 1
        if x <= 0 and y <= 0:
            q3 += 1
        if x >= 0 and y <= 0:
            q4 += 1
    print(max(q1, q2, q3, q4))

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

复杂度分析

时间复杂度：O(n) 每组数据，遍历所有点统计四个象限的人数。 空间复杂度：O(1)，仅用常数个计数变量。

第二题：拆开

题目描述

给定四个整数 n, k, m, r（n >= k, m >= 2, 0 <= r < m）。将 n 拆分为 k 个互不相同的正整数，要求每个数对 m 取余等于 r。如果无法做到，输出 -1；否则输出任意一组合法方案。

多组测试数据，第一行输入 T（所有测试数据的 k 之和不超过 200000）。

样例

输入

输出

YES
1 5 9
NO
YES
6 12 18

思路分析

第一步：确定满足条件的最小元素序列

所有满足 x > 0 且 x ≡ r (mod m) 的正整数，按从小到大排列构成等差数列：

若 r > 0：首项为 r，公差为 m，即 r, r+m, r+2m, …
若 r = 0：首项为 m（因为必须是正整数，0 不算），公差为 m，即 m, 2m, 3m, …

设 first_val = r if r > 0 else m。则满足条件的最小 k 个不同正整数为：

first_val, first_val + m, first_val + 2m, …, first_val + (k-1) * m

第二步：计算最小和并判断可行性

这 k 个数的和为：

min_sum = k * first_val + m * k * (k - 1) / 2

如果 n < min_sum，则不可能拆分，输出 NO。

此外，还需要检查 n 与 min_sum 的奇偶性（即模 m 的一致性）。由于每个元素都 ≡ r (mod m)，k 个元素之和 ≡ k * r (mod m)。如果 n mod m 不等于 (k * r) mod m，也无解。等价条件是 (n - min_sum) % m != 0 时无解。

第三步：构造方案

当有解时，取前 k-1 个最小值不动，将所有”余量”加到第 k 个数上：

前 k-1 个数：first_val, first_val + m, …, first_val + (k-2) * m
第 k 个数：n - (前 k-1 个数的和)

第 k 个数一定最大（因为余量 >= 0 且余量是 m 的整数倍），所以所有 k 个数互不相同。

验证第 k 个数的余数：n - 前 k-1 个数之和 = n - ((k-1) * first_val + m * (k-1)(k-2)/2)。由于 n ≡ k * first_val (mod m)（我们已经验证过），减去 (k-1) 个 first_val 后仍满足 ≡ first_val ≡ r (mod m)。

第四步：边界情况

如果余量为 0，第 k 个数等于 first_val + (k-1) * m，正好与前面最大的那个相同。但此时 n = min_sum，第 k 个数 = first_val + (k-1)m，这恰好是序列中第 k 个元素。我们取前 k-1 个数之和 = min_sum - (first_val + (k-1)m)，所以 last = n - (min_sum - last) = last，不重复。实际上当 n = min_sum 时正好是最小序列本身，各不相同。

以样例 1（n=15, k=3, m=4, r=1）为例：

first_val = 1，最小序列 = [1, 5, 9]，min_sum = 15 = n
直接输出 [1, 5, 9]

以样例 2（n=18, k=3, m=5, r=3）为例：

first_val = 3，最小序列 = [3, 8, 13]，min_sum = 24 > 18
n < min_sum，输出 NO

以样例 3（n=36, k=3, m=6, r=0）为例：

first_val = 6，最小序列 = [6, 12, 18]，min_sum = 36 = n
直接输出 [6, 12, 18]

题解代码

import sys
input = sys.stdin.readline

def solve():
    n, k, m, r = map(int, input().split())
    first_val = r if r > 0 else m
    # 最小和：k 个等差数列前 k 项之和
    min_sum = k * first_val + m * k * (k - 1) // 2

    if n < min_sum or (n - min_sum) % m != 0:
        print("NO")
        return

    print("YES")
    # 构造：前 k-1 个取最小值，第 k 个取剩余
    arr = [first_val + i * m for i in range(k - 1)]
    prefix_sum = (k - 1) * first_val + m * (k - 1) * (k - 2) // 2
    last = n - prefix_sum
    arr.append(last)
    print(*arr)

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

复杂度分析

时间复杂度：O(k) 每组数据，构造并输出 k 个数。 空间复杂度：O(k)，存储结果数组。

第三题：数字间隔

题目描述

给定长度为 n 的整数序列 a。统计满足以下条件的下标对 (i, j)（i < j）的数量：

a[i] - a[j] = 1（两端值相差恰好为 1）
对于所有 i < t < j 的位置 t，都有 a[t] > max(a[i], a[j])（中间所有元素严格大于两端的较大值）

多组测试数据，第一行输入 T（所有测试数据的 n 之和不超过 500000）。

样例

输入

输出

3
0

思路分析

第一步：理解合法对的结构

一个合法对 (i, j) 需要：

a[i] 和 a[j] 相差 1
i 和 j 之间的所有元素都严格大于 max(a[i], a[j])

这意味着 a[i] 和 a[j] 是区间 [i, j] 中的”谷底”两端，中间全是比它们更大的值。

以样例 1 [1, 3, 2, 4, 1] 为例：

(1, 3)：a[1]=1, a[3]=2， 1-2 =1，中间 a[2]=3 > max(1,2)=2 → 合法
(1, 5)：a[1]=1, a[5]=1， 1-1 =0 → 不合法
(3, 5)：a[3]=2, a[5]=1， 2-1 =1，中间 a[4]=4 > max(2,1)=2 → 合法
(1, 3) 对应下标 0,2（0-indexed）… 让我们用 1-indexed 重新列举

用 0-indexed：a = [1, 3, 2, 4, 1]

(0, 2)：a[0]=1, a[2]=2，差=1，中间 a[1]=3 > 2 → 合法
(0, 4)：a[0]=1, a[4]=1，差=0 → 不合法
(2, 4)：a[2]=2, a[4]=1，差=1，中间 a[3]=4 > 2 → 合法
(1, 2)：a[1]=3, a[2]=2，差=1，中间无元素 → 合法

共 3 对，符合输出。

第二步：单调栈思路

条件”中间所有元素严格大于两端较大值”暗示了单调栈模型。如果我们维护一个非递减单调栈（栈中元素从底到顶非递减），那么：

当处理到 a[j] 时，栈中所有大于 a[j] 的元素需要弹出
被弹出的元素恰好满足”在 j 之前且中间没有更小值阻隔”的条件

具体逻辑：遍历每个位置 j，维护非递减单调栈（存值）：

弹栈阶段：当栈顶 > a[j] 时弹出。弹出的值如果等于 a[j] + 1，说明可以和 j 配对（差为 1，中间全是更大值）。但同一轮弹出中，可能有多个相同值，我们只需要找最后一个弹出的等于 a[j]+1 的（即最靠近 j 的那个），因为中间如果有等值或更小值会破坏条件。实际上，在非递减栈中，弹出的元素是从栈顶开始递减/相等的序列，第一个弹出的 a[j]+1（如果有）就是最近的合法配对。
检查栈顶：弹栈结束后，如果栈顶值等于 a[j] - 1，说明栈顶与 j 配对（差为 1，中间弹出的全是大于 max(a[j]-1, a[j]) = a[j] 的值）。

第三步：详细分析弹栈过程中的配对

对于位置 j（值为 v = a[j]）：

在弹栈过程中，我们弹出所有栈顶值 > v 的元素。设弹出序列为 s1, s2, … (从先弹到后弹)，它们的值 >= 某个值。

如果弹出的元素中有值为 v+1 的：在非递减栈中，栈顶是最大值。弹出时先弹最大的，再弹较小的。值为 v+1 的如果存在，是在弹栈过程中最后被弹出的（因为 v+1 是最接近 v 的）。该元素对应的原始位置 i，满足 i 和 j 之间所有元素都在栈中且值 > v+1-1 = v… 不，更准确地说：它们之间的所有元素要么仍在栈中（值 > v），要么已经在之前被弹出。

让我们换一种更精确的理解：在非递减单调栈中，栈中任意相邻两元素 (bottom, top) 之间原序列中没有值 <= bottom 的元素。所以当我们弹出值为 v+1 的元素时，它与当前 j 之间的所有原序列元素值都 > v+1 > v = max(v, v+1)-… 等等，max(v, v+1) = v+1，需要中间严格大于 v+1。

重新审视：弹出元素的位置 i，值为 v+1。中间所有元素的值需要严格大于 max(v, v+1) = v+1。在非递减栈中，值为 v+1 的元素上方的所有元素（更后入栈的）都 >= v+1。但我们需要严格大于 v+1。

因此正确做法是：弹出的第一个值为 v+1 的元素（离 j 最近的）与 j 配对时，它们之间不会有值 <= v+1 的元素（因为栈是非递减的，上方全部 >= v+1 且已被弹出，它们的值 > v 才被弹出，但可能等于 v+1）。如果中间有等于 v+1 的元素，就不满足”严格大于”。

所以需要更精确的处理：使用非递减栈，当弹出值 > a[j] 时，检查第一个弹出的 v+1 是否是直接相邻于 j（中间已弹出的全 > v+1）。在非递减栈中，弹出顺序是从大到小（栈顶最大），所以先弹出的值更大。第一个遇到的 v+1 值就是最靠近栈顶的，也就是最靠近 j 的那个 v+1。此时它和 j 之间弹出的值全部 > v+1（因为先弹出的都比它大），满足”严格大于”条件。

弹栈后检查栈顶：栈顶如果等于 v-1，则栈顶位置 i 与 j 配对。中间的所有元素（已被弹出的）值 > v > v-1，且 max(v-1, v) = v，中间需要严格大于 v。但弹出的值 > v（弹出条件），满足。栈中 v-1 上方直到弹出前是那些被弹出的值（全 > v），满足条件。

第四步：实现总结

ans = 0
stack = []  # 存值
for j in range(n):
    v = a[j]
    found_plus1 = False
    while stack and stack[-1] > v:
        if stack[-1] == v + 1:
            found_plus1 = True
        stack.pop()
    if found_plus1:
        ans += 1
    if stack and stack[-1] == v - 1:
        ans += 1
    stack.append(v)

每个元素最多入栈一次、出栈一次，总时间 O(n)。

以样例 1 [1, 3, 2, 4, 1] 模拟：

j=0, v=1: stack=[], append → stack=[1]
j=1, v=3: stack=[1], 1 < 3 不弹。栈顶 1 != 3-1=2。append → stack=[1,3]
j=2, v=2: stack=[1,3], 3 > 2 弹出 3, 3==2+1 → found=True。栈顶 1==2-1 → ans+=1。总 ans=2。append → stack=[1,2]
j=3, v=4: stack=[1,2], 不弹。栈顶 2!=4-1=3。append → stack=[1,2,4]
j=4, v=1: stack=[1,2,4], 4>1 弹出 4 (!=2), 2>1 弹出 2 (2==1+1 → found=True)。栈顶 1==1-1=0? 不。栈顶 1!=0。ans+=1(found)。总 ans=3。append → stack=[1,1]

最终 ans = 3，正确。

样例 2 [2, 2, 2, 2]：所有值相同，差为 0，不满足

差

=1，ans = 0。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    stack = []  # 非递减单调栈，存值

    for j in range(n):
        v = a[j]
        found_plus1 = False
        while stack and stack[-1] > v:
            if stack[-1] == v + 1:
                found_plus1 = True
            stack.pop()
        if found_plus1:
            ans += 1
        if stack and stack[-1] == v - 1:
            ans += 1
        stack.append(v)

    print(ans)

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

复杂度分析

时间复杂度：O(n) 每组数据，每个元素至多入栈和出栈各一次。 空间复杂度：O(n)，单调栈最多存 n 个元素。

小结

第一题是几何直觉题，核心观察是从 (X,Y) 到原点的所有最短路径覆盖整个矩形区域，因此将快递站放在某个象限的极远处可以覆盖该象限所有人。注意坐标轴上的点属于两个象限，用 if 而非 elif 进行计数
第二题是构造题，关键是确定同余条件下最小的 k 个不同正整数，算出最小和后判断可行性（总和够且余量是 m 的倍数），构造时让前 k-1 个取最小值、最后一个吸收全部余量即可保证互不相同
第三题利用单调栈高效找到所有满足”中间全部严格更大”的配对。维护非递减栈，弹栈时检查是否有值恰好等于当前值 +1，弹栈后检查栈顶是否等于当前值 -1，各贡献一个合法对。每个元素只入栈出栈一次，O(n) 解决

这篇文章有帮助吗？

| GitHub 留言