笔试时间：2024年09月19日 秋招

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

第一题

题目

一个nxm 的网格图a，左上角为(0,0)，右下角为(n-1,m-1)，格子(i,j) 价值为 i * m + j。游游从左上角 (0,0)为起点，每一步可以走到上下左右四个方向的相邻格子。每到达一个格子，就能获取相应格子的奖励。需要注意的是，在到达某个格子获取宝物后，这个格子的宝物会在游游离开格子后再次刷新。现在给出一个整数k，表示游游最多走k步。问:游游最多能获得多少价值的宝物

输入描述

第一行输入q(1 <= q <= 10 ^ 5)，表示询问个数。

接下来q行，每行输入n，m，k(1 <= n, m, k <= 10^4, n + m > 2)，表示矩阵大小和限制步数。

输出描述

输出q行分别表示每组数据答案。

样例输入

1

2 2 5

样例输出

12

参考题解

模拟。

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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    ll ans = 0;
    if (k >= n - 1) {
        k -= n - 1;
        ans += 1LL * (n - 1) * m * n / 2;
    }else {
        ans += 1LL * k * m * (k + 1) / 2;
        k = 0;
    }

    int last = (n - 1) * m;
    if (k >= m - 1) {
        ans += 1LL * (last + 1 + last + m - 1) * (m - 1) / 2;
        k -= m - 1;
    }else {
        ans += 1LL * (last + 1 + last + k) * k / 2;
        k = 0;
    }

    last = n * m - 1;
    int prev = last - 1;
    if (k > 0) {
        ans += 1LL * (k + 1) / 2 * prev;
        ans += 1LL * k / 2 * last;
    }

    cout << ans << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

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

import java.util.Scanner;

public class Solution {
    
    public static void solve() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        
        long ans = 0;
        
        if (k >= n - 1) {
            k -= n - 1;
            ans += 1L * (n - 1) * m * n / 2;
        } else {
            ans += 1L * k * m * (k + 1) / 2;
            k = 0;
        }

        int last = (n - 1) * m;
        if (k >= m - 1) {
            ans += 1L * (last + 1 + last + m - 1) * (m - 1) / 2;
            k -= m - 1;
        } else {
            ans += 1L * (last + 1 + last + k) * k / 2;
            k = 0;
        }

        last = n * m - 1;
        int prev = last - 1;
        if (k > 0) {
            ans += 1L * (k + 1) / 2 * prev;
            ans += 1L * k / 2 * last;
        }

        System.out.println(ans);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }
}

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

def solve():
    n, m, k = map(int, input().split())
    
    ans = 0
    
    if k >= n - 1:
        k -= n - 1
        ans += (n - 1) * m * n // 2
    else:
        ans += k * m * (k + 1) // 2
        k = 0

    last = (n - 1) * m
    if k >= m - 1:
        ans += (last + 1 + last + m - 1) * (m - 1) // 2
        k -= m - 1
    else:
        ans += (last + 1 + last + k) * k // 2
        k = 0

    last = n * m - 1
    prev = last - 1
    if k > 0:
        ans += (k + 1) // 2 * prev
        ans += k // 2 * last

    print(ans)

def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

第二题

题目

游游在黑板上写下了n个数字，构成了一个可重集合。游游请你参与一个游戏:每轮操作你可以任选集合中最大值和最小值的差不超过k的 m 个数字，然后删去这 m 个数字中的最小值（删除一个），并把其他的数字放回集合中。若无法选出符合条件的m个数，则无法继续操作。你可以无限次进行这个操作，直到没法操作为止。要使得最后留下的数最少，请你求出操作后留下的最少的数字数量。

输入描述

第一行三个整数n，m，k(2 <= m <= 10^6, 0 <= k <= 10^9)

第二行输入n个整数。

输出描述

输出答案。

样例输入一

4 3 3

1 2 3 6

样例输出一

3

样例输入二

5 3 2

5 4 4 2 1

样例输出二

3

样例输入三

7 2 0

3 3 3 3 4 4 4

样例输出三

2

参考题解

对数组进行排序然后维护一个长度为m的窗口即可。

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

#include <bits/stdc++.h>
using namespace std;

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

    sort(a.begin(), a.end());
    int ans = n;
    for (int l = 0, r = 0; r < n; r++) {
        if (r - l + 1 == m) {
            if (a[r] - a[l] <= k) {
                ans--;
            }
            l++;
        }
    }

    cout << ans << "\n";
}

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

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        Arrays.sor