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

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

第一题

题目：传染病防控

R市正在进行传染病防控。R市总共有n个人。具体的，每个人有一个位置(x,y)，现在已知有一个是高风险人员，但还未追踪到具体是谁。同时我们定义一个安全距离K。如果某个人和这个高风险人员的距离不超过K，那么这个人也将被列为高风险人员。为了减少防控对市民生活的影响，工作人员希望知道所有可能情况下最多的高风险人员数量。

两个人(x1, y1)(x2, y2)的距离定义为|x1-x2| + |y1-y2|。

输入描述

一行两个整数 n 和 k；

接下来一行包含 n 个整数 x1,x2,...xn；

再接下来一行包含 n 个整数 y1,y2,...yn；

约束条件: 1<=n<=1000, 1<=k,x,y<=1000。

输出描述

输出一个整数，表示感染人数的最大数量。

样例输入

5 2  

8 6 1 5 1  

4 4 3 4 6  

样例输出

3

说明：如果一开始一号人员高风险，则二号人员也会变成高风险，然后四号人员变成高风险，此时高风险人员数量最多为3。

参考题解

先把所有点的距离预处理出来，再用并查集合并距离小于等于k的节点，最后找出最大集合输出最大值即可。

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

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1100;

int a[N], b[N];
int dist[N][N];
int n, k;
int num[N];
int p[N];
int find(int x) 
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    
    cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= n; i ++ ) cin >> b[i];
    
    for(int i = 1; i <= n; i ++)
    {
        for(int j = i + 1; j <= n; j ++)
        {
            dist[i][j] = dist[j][i] = abs(a[i] - a[j]) + abs(b[i] - b[j]);
        }
    }
    
    for(int i = 1; i <= n; i ++) p[i] = i, num[i] = 1;
    
    for(int i = 1; i <= n; i ++)
    {
        for(int j = i + 1; j <= n; j ++)
        {
            int px = find(i), py = find(j);
            if(px != py && dist[i][j] <= k)
            {
                p[px] = py;
                num[py] += num[px];
            }
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i ++) res = max(res, num[i]);
    cout << res;
    return 0;
}

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

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static final int N = 1100;
    static int[] a = new int[N], b = new int[N];
    static int[][] dist = new int[N][N];
    static int[] num = new int[N];
    static int[] p = new int[N];
    static int n, k;

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

        n = scanner.nextInt();
        k = scanner.nextInt();

        for (int i = 1; i <= n; i++) a[i] = scanner.nextInt();
        for (int i = 1; i <= n; i++) b[i] = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                dist[i][j] = dist[j][i] = Math.abs(a[i] - a[j]) + Math.abs(b[i] - b[j]);
            }
        }

        for (int i = 1; i <= n; i++) {
            p[i] = i;
            num[i] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int px = find(i);
                int py = find(j);
                if (px != py && dist[i][j] <= k) {
                    p[px] = py;
                    num[py] += num[px];
                }
            }
        }

        int res = 0;
        for (int i = 1; i <= n; i++) res = Math.max(res, num[i]);

        System.out.println(res);
        scanner.close();
    }

    private static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

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

import sys
input = sys.stdin.read
from math import abs

N = 1100
a = [0] * N
b = [0] * N
dist = [[0] * N for _ in range(N)]
num = [0] * N
p = [0] * N

def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

def main():
    global n, k

    data = input().split()
    n = int(data[0])
    k = int(data[1])

    a[1:n+1] = map(int, data[2:n+2])
    b[1:n+1] = map(int, data[n+2:2*n+2])

    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            dist[i][j] = dist[j][i] = abs(a[i] - a[j]) + abs(b[i] - b[j])

    for i in range(1, n + 1):
        p[i] = i
        num[i] = 1

    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            px =