米哈游筆試米哈游筆試題 0328

筆試時(shí)間：2025年03月28日

歷史筆試傳送門：

2023春招秋招筆試合集

2024春招秋招筆試合集

第一題

題目：數(shù)字凸包區(qū)間

米小游有 n 個(gè)整數(shù) {a_1,a_2,...,a_n} ，他定義區(qū)間 [l,r] 的“數(shù)字凸包區(qū)間”為 [min{a_l,...,a_r},max{a_l,..,a_r}] 。現(xiàn)在，對于每一個(gè) i=1,2,....,n ，直接輸出不屬于 [1,i] 這個(gè)區(qū)間的“數(shù)字凸包區(qū)間”的最小非負(fù)整數(shù)。

輸入描述

第一行輸入兩個(gè)整數(shù) n (1 <= n <= 10^5 ) 代表整數(shù)數(shù)量、詢問次數(shù)。

第二行輸入 n 個(gè)整數(shù) a_1,a_2,...,a_n ( 0 <= a_i <=10^9) 代表元素。

輸出描述

在一行上輸出 n 個(gè)整數(shù)，代表對于每一個(gè) i 的答案。

樣例輸入

5

1 0 4 5 1

樣例輸出

0 2 5 6 6

說明：

對于第一次詢問，“數(shù)字凸包區(qū)間”為 [1,1] ，不屬于這個(gè)“數(shù)字凸包區(qū)間”的最小非負(fù)整數(shù)為 0 。對于第二次詢問，“數(shù)字凸包區(qū)間”為 [0,1] ，不屬于這個(gè)“數(shù)字凸包區(qū)間”的最小非負(fù)整數(shù)為 2 。

參考題解

需要為每個(gè)前i個(gè)元素構(gòu)成的區(qū)間找到不屬于其“數(shù)字凸包區(qū)間”的最小非負(fù)整數(shù)。這里的“數(shù)字凸包區(qū)間”定義為區(qū)間內(nèi)元素的最小值和最大值構(gòu)成的閉區(qū)間。若當(dāng)前區(qū)間的最小值 min > 0，則最小的缺失非負(fù)整數(shù)一定是 0（因?yàn)?不在閉區(qū)間內(nèi)）。若當(dāng)前區(qū)間的最小值 min = 0，則最小的缺失非負(fù)整數(shù)是 max + 1（因?yàn)殚]區(qū)間覆蓋了0到max的所有整數(shù)）。

C++：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

#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：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

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：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

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)))

第二題

題目：最大面積

給定一個(gè)長度為 n 的二進(jìn)制字符串 s，由 0 和 1 字符組成。我們需要構(gòu)建一個(gè)行數(shù)為 n，列數(shù)為 n 的方表，由 0 和 1 字符組成。第一行為原始字符串 s，第二行為字符串 s 向右循環(huán)移動(dòng)一個(gè)，第三行為字符串 s 向右循環(huán)移動(dòng)兩個(gè)，以此類推。求表中所有由 0 組成的三角形或矩形的最大面積值。第一行是字符串 s。第二行是字符串 s 向右循環(huán)移動(dòng)一個(gè)位置。第 i 行是字符串 s 向右循環(huán)移動(dòng) i-1 個(gè)位置。