笔试时间：2024年08月17日 秋招

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

第一题

题目：米小游的原石计划

为了抽到心爱的五星角色，米小游需要至少 n 颗原石。 目前米小游手里没有任何的原石，距离卡池结束还有 m 天。 原石有两种获取方式，一种是充小月卡，另一种是直接买。 1.充一次月卡需要 30 块钱，可以增加 30 天的祝福次数，每天只能领一次祝福（90原石），购买当天可额外领取 300原石。 2.直接买则是 1 块钱 10 原石。 为了尽可能省钱，他希望你帮他求出最少的花费。

输入描述

第一行有两个整数 n(1<=n<=2.10^5) 和m(1<=m<=240) 。

输出描述

输出一个整数，代表最少的花费 。

样例输入

3200 35

样例输出

50

说明

充一次小月卡，然后额外充20块钱。

参考题解

由于月卡可以一次性获得300，那我们可以得出以下结论：除非我们仍然需要的数量不足300，否则一定是买月卡划算。接下来按照n的余量进行循环即可。

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

#include <iostream>

int main() {
    int n, m;
    std::cin >> n >> m;
    int cnt = 0;

    while (n > 0) {
        if (n >= 300) {
            // 月卡
            cnt += 30;
            if (m >= 30) {
                m -= 30;
                n -= 300 + 90 * 30;
            } else {
                n -= 300 + 90 * m;
                m = 0;
                cnt += n / 10;
                n = 0;
            }
        } else {
            cnt += n / 10;
            n = 0;
        }
    }

    std::cout << cnt << std::endl;
    return 0;
}

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

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int cnt = 0;

        while (n > 0) {
            if (n >= 300) {
                // 月卡
                cnt += 30;
                if (m >= 30) {
                    m -= 30;
                    n -= 300 + 90 * 30;
                } else {
                    n -= 300 + 90 * m;
                    m = 0;
                    cnt += n / 10;
                    n = 0;
                }
            } else {
                cnt += n / 10;
                n = 0;
            }
        }

        System.out.println(cnt);
    }
}

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

n,m = map(int, input().split())
cnt = 0
while n > 0:
    if n>= 300:
        #月卡
        cnt += 30
        if m >= 30:
            m-=30
            n -= 300 + 90 * 30
        else:
            n -= 300 + 90 * m
            m = 0
            cnt += n//10
            n = 0
    else:
        cnt += n//10
        n = 0

print(cnt)

第二题

题目：米小游种树（一）

一条长度为 n 的公路上，米小游雇佣了 m 名植树工，其中第 i 位工人会给 [li,ri] 这一段区间中的每个点都种上一棵树。图片但由于每个点最多种一棵树，因此如果某位工人发现自己要种的地方已经有树，自己就会跳过这个点不管。图片米小游为了节约成本，现在要恰好少雇佣一名工人，但同时他不希望少了此人会影响最终种树的结果，现在请你帮他算算有多少名工人都可以成为恰好少雇佣的这一名呢。

输入描述

第一行输入两个正整数 n,m (1<=n<=2*10^5;1<=m<=10^5 ) 代表公路长度和植树工人数量。

接下来 m 行，每行输入两个正整数 li,ri (1<=li<=ri<=n) 代表第 i 位工人负责种树的区域。

输出描述

在一行上输出一个整数，代表有多少名工人可以被解雇。

样例输入一

5 3

1 4

1 2

3 4

样例输出一

3

说明

三名工人都可以成为被解雇的那一个。

最终的种树结果为： [1,1,1,1,0]（1 表示有树，0 表示没有。）

解雇第一位工人，种树结果依然为 [1,1,1,1,0]：不会影响结果。

解雇第二位工人，依然不会影响结果。

解雇第三位工人，依然不会影响结果。

样例输入二

4 2

1 2

3 4

样例输出二

0

说明

每名工人都不可或缺。

最终种树结果为：[1,1,1,1]。

如果解雇第一位工人，则结果变为：[0,0,1,1]，影响了结果。

如果解雇第二位工人，则结果变为：[1,1,0,0]，影响了结果。

参考题解

首先使用差分数组处理出所有的工人操作后的结果。那么对于某一个工人（区间）来讲，如何判断是否可以裁员呢？那么就是他负责的这个区间内的最小值大于1，那么说明他走了以后区间的所有位置仍然有其他工人顶上的，那么这里就可以使用ST表来快速查询。

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

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

vector<vector<int>> f;
vector<int> Logn;

void precompute(const vector<int>& arr) {
    int n = arr.size();
    int logn = floor(log2(n)) + 1;

    f.assign(n, vector<int>(logn));
    Logn.assign(n + 1, 0);

    // Calculate Log values
    for (int i = 2; i <= n; i++) {
        Logn[i] = Logn[i / 2] + 1;
    }

    // Initialize the first column of the sparse table
    for (int i = 0; i < n; i++) {
        f[i][0] = arr[i];
    }

    // Fill the sparse table
    int j = 1;
    while ((1 << j) <= n) {
        int i = 0;
        while (i + (1 << j) - 1 < n) {
            f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            i++;
        }
        j++;
    }
}

int query(int L, int R) {
    int s = Logn[R - L + 1];
    return min(f[L][s], f[R - (1 << s) + 1][s]);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> diff(n);

    vector<pair<int, int>> itvs(m);
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        itvs[i] = {l, r};
        diff[l]++;
        if (r + 1 < n) diff[r + 1]--;
    }

    vector<int> res(n);
    res[0] = diff[0];
    for (int i = 1; i < n; i++) {
        res[i] = res[i - 1] + diff[i];
    }
    precompute(res);

    int cnt = 0;
    for (const auto& itv : itvs) {
        if (query(itv.first, itv.second) > 1) {
            cnt++;
        }
    }

    cout << cnt << endl;
    return 0;
}

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

import java.util.Scanner;

public class Main {
    privat