笔试时间：2024年03月23日

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

第一题

题目：访问

小明在玩一个游戏。这个游戏在二维平面上，有n座村庄，第i座村庄的坐标为(xi, yi)。小明会从某个村庄出发，走到另外一个目的地村庄。小明每秒可以选择上下左右一个方向并移动一单位距离，从一个村庄到另一个村庄的耗时是所有移动的方案里花费时间最少的方案耗时。显然两个村庄间的耗时即x坐标的差和y坐标的差的和，具体的，即|xi - xj| + |yi - yj|。现在小明想知道所有村庄两两间耗时中最大的耗时。

输入描述

第一行一个正整数n，表示村庄个数。

接下来两行每行n个整数，表示xi .. xn 和yi .. yn。

输出描述

输出一个整数表示所有情况中最大的耗时。

参考题解

将绝对值去掉，有四种情况，基于这四种情况进行排序即可。

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    int n; cin >> n;
    vector<vector<int> > arr(n, vector<int>(2));
    vector<vector<ll> > a(4, vector<ll>(n));
    for (int i = 0; i < n; ++i) {
        cin >> arr[i][0];
    }
    for (int i = 0; i < n; ++i) {
        cin >> arr[i][1];
    }
    for (int i = 0; i < n; ++i) {
        ll x = arr[i][0], y = arr[i][1];
        a[0][i] = x + y;
        a[1][i] = x - y;
        a[2][i] = -x + y;
        a[3][i] = -x - y;
    }
    for (int i = 0; i < 4; ++i) sort(a[i].begin(), a[i].end());
    ll ans = 0;
    for (int i = 0; i < 4; ++i) {
        ans = max(ans, a[i][n-1] - a[i][0]);
    }
    cout << ans;
}

第二题

题目

小丽的动手能力很强。一天，她仅靠自己造了一台计算器。不过，这台计算器的功能还不算很强大，仅仅可以计算n个数的极差。另外，由于内存和容量限制，如果数字太多的话会删掉一些数字再进行计算。具体来说，这台计算器有三种功能：

1.新存入一个数字x；

2.输入两个数m，x，之后计算器中删除m个数字x。如果当前计算器存入的x的个数不足m，则把x全部删完；

3. 计算目前计算器中存入的所有数字的极差（最大值减最小值）

现在，小丽执行了Q次操作，她想知道每次查询极差时的输出是多少。

输入描述

由于输入可能会很多，故本题采用随机数生成器的方式生成数据，具体如下：

输入仅一行两个正整数Q，seed。其中Q是操作次数，seed是一个32位无符号整型的随机种子，之后每次询问执行如下伪代码产生：

seed = seed ^ （seed << 15）；

seed = seed ^ (seed >> 5);

seed = seed ^ (seed << 1);

seed = seed % (1 << 15);

int op = （seed ^ （seed << 7） ^ （seed >> 5）） % 3+1；

int m = （seed ^ （seed << 6） ^ （seed >> 10）） % Q+1；

int x = (seed ^ (seed << 5) ^ (seed << 9) ^ (seed >> 6)) % 10 + 1