米哈游笔试米哈游笔试题 0310

笔试时间：2024年03月10日

历史笔试传送门：2023秋招笔试合集

第一题

题目：米小游和蹦蹦史莱姆

地图上有 n 个格子排成一排，最左边的格子为1，最右边的格子为n。第0 秒时，每个格子都有一只史莱姆。第i 只史莱姆的跳跃方向用数组a 表示。ai=0 表示史莱姆跳跃的方向是往左。若第 i 秒史莱姆位于格子 x，那么第i+1 秒史莱姆会跳到格子x-1 。如果当前史莱姆在格子1，则下一秒史莱姆将跳出地图。ai=1 表示史莱姆跳跃的方向是往右。若第 i 秒史莱姆位于格子x，那么第 i+1 秒史莱姆会跳到格子x+1 。如果当前史莱姆在格子 n，则下一秒史莱姆将跳出地图。米小游想知道第 1-n 秒，地图上有多少个格子没有史莱姆。

输入描述

第一行包含一个整数n，n∈[1,3000]，表示地图上的格子数量。

第二行包含n 个整数ai，ai∈[0,1]，表示每只史莱姆的跳跃方向。

输出描述

输出包含一行n 个整数，用空格隔开，第i 个数表示第i 秒没有史莱姆的格子数量。

样例输入

3

1 0 1

样例输出

1 2 3

说明：史莱姆1-3 的跳跃方向分别为，往右，往左，往右。第 1 秒，史莱姆1 跳到格子 2，史莱姆2 跳到格子1，史莱姆3 跳出地图，格子3 没有史莱姆。第 2 秒，史莱姆 1 跳到格子3，史莱姆 2 跳出地图，格子 1,2 没有史莱姆。第 3 秒，史莱姆1 跳出地图，格子1,2,3 没有史莱姆。

参考题解

直接模拟即可。

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

#include <iostream>
#include <vector>

using namespace std;

string optimize_solution(int n, vector<int>& dirs) {
    vector<int> ans(n, 1);
    vector<vector<int>> positions(n, vector<int>(2, 0));

    for (int i = 0; i < n; ++i) {
        positions[i][dirs[i]]++;
    }

    vector<int> res(n, 0);
    for (int i = 0; i < n; ++i) {
        vector<vector<int>> new_positions(n, vector<int>(2, 0));
        for (int k = 0; k < n; ++k) {
            int l = positions[k][0];
            int r = positions[k][1];
            ans[k] -= (l + r);
            if (k - 1 >= 0) {
                ans[k - 1] += l;
            }
            if (k + 1 < n) {
                ans[k + 1] += r;
            }
            if (k - 1 >= 0) {
                new_positions[k - 1][0] += l;
            }
            if (k + 1 < n) {
                new_positions[k + 1][1] += r;
            }
        }
        positions = new_positions;
        res[i] = count(ans.begin(), ans.end(), 0);
    }

    string result;
    for (int num : res) {
        result += to_string(num) + " ";
    }
    return result;
}

int main() {
    int n;
    cin >> n;
    vector<int> dirs(n);
    for (int i = 0; i < n; ++i) {
        cin >> dirs[i];
    }
    string result = optimize_solution(n, dirs);
    cout << result << endl;
    return 0;
}

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

import java.util.*;

public class Main {

    public static String optimizeSolution(int n, int[] dirs) {
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
        int[][] positions = new int[n][2];

        for (int i = 0; i < n; i++) {
            positions[i][dirs[i]]++;
        }

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int[][] newPositions = new int[n][2];
            for (int k = 0; k < n; k++) {
                int l = positions[k][0];
                int r = positions[k][1];
                ans[k] -= (l + r);
                if (k - 1 >= 0) {
                    ans[k - 1] += l;
                }
                if (k + 1 < n) {
                    ans[k + 1] += r;
                }
                if (k - 1 >= 0) {
                    newPositions[k - 1][0] += l;
                }
                if (k + 1 < n) {
                    newPositions[k + 1][1] += r;
                }
            }
            positions = newPositions;
            res[i] = countZeros(ans);
        }

        StringBuilder result = new StringBuilder();
        for (int num : res) {
            result.append(num).append(" ");
        }
        return result.toString();
    }

    public static int countZeros(int[] array) {
        int count = 0;
        for (int num : array) {
            if (num == 0) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] dirs = new int[n];
        for (int i = 0; i < n; i++) {
            dirs[i] = scanner.nextInt();
        }
        String result = optimizeSolution(n, dirs);
        System.out.println(result);
    }
}

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

from collections import defaultdict

def optimize_solution(n, dirs):
    ans = [1]*n
    dic = {i: [0, 0] for i in range(n)}
    for i, d in enumerate(dirs):
        dic[i][d] += 1

    res = [0]*n
    for i in range(n):
        new_dic = {i: [0, 0] for i in range(n)}
        for k, v in dic.items():
            l, r = v
            ans[k] -= l+r
            if k-1 >= 0:
                ans[k-1] += l
            if k+1 < n:
                ans[k+1] += r
            if k-1 >= 0:
                new_dic[k-1][0] += l
            if k+1 < n:
                new_dic[k+1][1] += r
        dic = new_dic
        res[i] = ans.count(0)

    return ' '.join(map(str, res))

if __name__ == "__main__":
    n = int(input())
    dirs = [int(c) for c in input().split()]
    result = optimize_solution(n, dirs)
    print(result)