米哈游笔试米哈游笔试题 0328

笔试时间：2025年03月28日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：数字凸包区间

米小游有 n 个整数 {a_1,a_2,...,a_n} ，他定义区间 [l,r] 的“数字凸包区间”为 [min{a_l,...,a_r},max{a_l,..,a_r}] 。现在，对于每一个 i=1,2,....,n ，直接输出不属于 [1,i] 这个区间的“数字凸包区间”的最小非负整数。

输入描述

第一行输入两个整数 n (1 <= n <= 10^5 ) 代表整数数量、询问次数。

第二行输入 n 个整数 a_1,a_2,...,a_n ( 0 <= a_i <=10^9) 代表元素。

输出描述

在一行上输出 n 个整数，代表对于每一个 i 的答案。

样例输入

5

1 0 4 5 1

样例输出

0 2 5 6 6

说明：

对于第一次询问，“数字凸包区间”为 [1,1] ，不属于这个“数字凸包区间”的最小非负整数为 0 。对于第二次询问，“数字凸包区间”为 [0,1] ，不属于这个“数字凸包区间”的最小非负整数为 2 。

参考题解

需要为每个前i个元素构成的区间找到不属于其“数字凸包区间”的最小非负整数。这里的“数字凸包区间”定义为区间内元素的最小值和最大值构成的闭区间。若当前区间的最小值 min > 0，则最小的缺失非负整数一定是 0（因为0不在闭区间内）。若当前区间的最小值 min = 0，则最小的缺失非负整数是 max + 1（因为闭区间覆盖了0到max的所有整数）。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), result(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int min_val = a[0];
    int max_val = a[0];

    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            min_val = min(min_val, a[i]);
            max_val = max(max_val, a[i]);
        }
        if (min_val > 0) {
            result[i] = 0;
        } else {
            result[i] = max_val + 1;
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << result[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        int[] result = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        int minVal = a[0];
        int maxVal = a[0];

        for (int i = 0; i < n; i++) {
            if (i > 0) {
                minVal = Math.min(minVal, a[i]);
                maxVal = Math.max(maxVal, a[i]);
            }
            if (minVal > 0) {
                result[i] = 0;
            } else {
                result[i] = maxVal + 1;
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.print(result[i]);
            if (i < n - 1) System.out.print(" ");
        }
        System.out.println();

        scanner.close();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

n = int(input())
a = [int(c) for c in input().split()]

min_val = a[0]
max_val = a[0]
result = []

for i in range(n):
    if i > 0:
        min_val = min(min_val, a[i])
        max_val = max(max_val, a[i])
    if min_val > 0:
        result.append(0)
    else:
        result.append(max_val + 1)

print(' '.join(map(str, result)))

第二题

题目：最大面积

给定一个长度为 n 的二进制字符串 s，由 0 和 1 字符组成。我们需要构建一个行数为 n，列数为 n 的方表，由 0 和 1 字符组成。第一行为原始字符串 s，第二行为字符串 s 向右循环移动一个，第三行为字符串 s 向右循环移动两个，以此类推。求表中所有由 0 组成的三角形或矩形的最大面积值。第一行是字符串 s。第二行是字符串 s 向右循环移动一个位置。第 i 行是字符串 s 向右循环移动 i-1 个位置。