传染病防控

问题描述

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

两个人 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的距离定义为：$|x_1 - x_2| + |y_1 - y_2|$

输入描述

第一行：两个整数 n, k。表示有 n 个人以及距离阈值 k。
第二行：n 个整数，表示每个人的 x 坐标。
第三行：n 个整数，表示每个人的 y 坐标。

其中：

1 ≤ n ≤ 1000
1 ≤ k ≤ 1000
1 ≤ x, y ≤ 1000

输出描述

输出一个整数，表示最多的高风险人员数量。

示例输入

1
2
3

5 2
8 6 1 5 1
4 4 3 4 6

示例输出

提示

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

问题分析

正确的传染规则：

初始有一个高风险人员（未知）。
高风险人员可以传染他人：如果某个人与任意一个高风险人员的 曼哈顿距离 不超过 k，那么他也会成为高风险人员。
传染是可以传播的：新成为高风险的人员也可以继续传染他人。

由于传染是可传播的，我们需要找到在某个初始高风险人员的情况下，能够传染的最大人数。

然而，我们不知道初始高风险人员是谁，但我们需要找到能够形成 最大传染链 的情况。

解决方法：

构建图模型：
- 将每个人视为图中的一个节点。
- 如果两个人的曼哈顿距离不超过 k，就在他们之间建立一条边。
寻找最大连通子图（连通分量）：
- 由于传染可以通过边传播，连通子图中的所有节点都可能被感染。
- 因此，最大可能的高风险人员数量，就是图中 最大连通分量的大小。

算法

构建图：
- 遍历所有人员对，计算他们之间的距离，如果距离不超过 k，就在他们之间建立一条边。
- 由于人员数量最多为 1000，建立邻接列表或邻接矩阵都是可行的。
寻找最大连通分量：
- 使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历图，找出所有连通分量。
- 记录每个连通分量的大小，取其中最大值。

示例演示

1
2
3

5 2
8 6 1 5 1
4 4 3 4 6

人员列表：

编号 x y

0 8 4

1 6 4

2 1 3

3 5 4

4 1 6
构建图：
- 计算距离并建立边：
  - 人员 0 和人员 1：距离 2，建立边。
  - 人员 1 和人员 3：距离 1，建立边。
  - 人员 2 和人员 4：距离 2，建立边。
- 图中边的信息：
  - 边 (0, 1)
  - 边 (1, 3)
  - 边 (2, 4)
连通分量：
- 第一个连通分量：人员 0, 1, 3（大小为 3）
- 第二个连通分量：人员 2, 4（大小为 2）
- 孤立节点：无
最大连通分量的大小为 3，因此最多可能有 3 个高风险人员。

编号	x	y
0	8	4
1	6	4
2	1	3
3	5	4
4	1	6

import java.util.*;

public class Main {
    static int n, k;
    static int[] x, y;
    static boolean[] visited;
    static List<Integer>[] graph;

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

        // 读取 n 和 k
        n = sc.nextInt();
        k = sc.nextInt();

        x = new int[n];
        y = new int[n];

        // 读取 x 坐标
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
        }

        // 读取 y 坐标
        for (int i = 0; i < n; i++) {
            y[i] = sc.nextInt();
        }

        // 构建图
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 建立边
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int distance = Math.abs(x[i] - x[j]) + Math.abs(y[i] - y[j]);
                if (distance <= k) {
                    graph[i].add(j);
                    graph[j].add(i);
                }
            }
        }

        int maxCount = 0;
        visited = new boolean[n];

        // 寻找最大连通分量
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int count = dfs(i);
                if (count > maxCount) {
                    maxCount = count;
                }
            }
        }

        // 输出结果
        System.out.println(maxCount);
    }

    // 深度优先搜索，返回连通分量的大小
    static int dfs(int u) {
        visited[u] = true;
        int count = 1;
        for (int v : graph[u]) {
            if (!visited[v]) {
                count += dfs(v);
            }
        }
        return count;
    }
}

代码说明

图的构建：
- 使用邻接表 graph 来存储图。
- 对于每对人员 (i, j)，如果距离不超过 k，则在 graph[i] 和 graph[j] 中互相添加。
深度优先搜索（DFS）：
- 使用布尔数组 visited 标记访问过的节点。
- 函数 dfs(int u) 返回以节点 u 为起点的连通分量的大小。
寻找最大连通分量：
- 遍历所有节点，如果节点未被访问过，则从该节点出发进行 DFS，计算连通分量大小。
- 更新 maxCount，记录最大连通分量的大小。

注意事项

传染的传播性：
- 由于传染可以通过多次接触传播，需要使用 DFS 或 BFS 遍历图，确保所有可能被感染的人员都被计算在内。
图的连通分量：
- 最大的连通分量的大小就是可能的最多高风险人员数量。
复杂度分析：
- 构建图的复杂度：$O(n^2)$
- DFS 的复杂度：$O(n + m)$，其中 $m$ 是图的边数，最坏情况下 $O(n^2)$。
- 总体复杂度在 $n$ 较小的情况下（$n \leq 1000$）是可接受的。

扩展思考

如果需要处理更大的数据规模，可以考虑以下优化：

空间优化：
- 如果 $k$ 很小，可以使用坐标压缩或网格化的方法，将坐标映射到较小的范围内，以减少遍历的次数。
并查集（Union Find）：
- 使用并查集数据结构来维护连通分量，在构建图的过程中合并节点，可以提高效率。

分数约分判断

题目描述

有一种十分奇妙的约分：并非是分子分母同时除以一个数，而是上下同时删除相同的数字。例如，114514/1919810 -> 14514/919810 -> 1454/91980这样。

当然我们知道这样的约分的结果可能和正常约分的结果并不一致，因此我们才称这一过程为奇妙的约分。

在奇妙的约分过程中，一个数字可能会出现多个 0，此时，我们会尽量保留 0 原有的位置，只要保证数字没有完全删除，以及分母不等于 0 即可。

现在，给出两个分数，你需要判断第二个分数是否能够由第一个分数经过上述 “奇妙的约分” 得到。

输入格式

第一行一个正整数 T，表示有 T 组数据。
对于每一组数据，输入一行两个形如 a/b 的分数，中间用空格隔开。
1≤T≤10, 1≤a,b≤10^10000, 保证输入的数字无前导零。

输出格式

对于每一组数据，如果第二个分数能够由第一个分数经过上述 “奇妙的约分” 得到，输出 Yes；否则，输出 No。

特别地，当第二个分数不需要进行任何约分就等于第一个分数时，也输出 yes。

样例输入

4
114514/1919810 1454/91980
114514/1919810 454/9980
114514/1919810 114514/1919810
21/42 1/2

样例输出

Yes
Yes
Yes
No

提示

前三组样例都符合奇妙约分的规则。第四组虽然最终结果相同，但 21/42 无法通过删除数字得到 1/2。

解题思路：

统计数字出现次数：
- 对于第一个分数的分子和分母，以及第二个分数的分子和分母，分别统计每个数字（0-9）的出现次数。
计算需要删除的数字：
- 对于分子，计算需要删除的数字及其次数，即第一个分数的分子数字次数减去第二个分数的分子数字次数。
- 对于分母，计算需要删除的数字及其次数，即第一个分数的分母数字次数减去第二个分数的分母数字次数。
验证删除的数字是否相同：
- 检查分子和分母中需要删除的数字及其次数是否完全相同。
- 如果两者删除的数字和次数完全一致，则第二个分数可以通过奇妙的约分得到。
特殊情况处理：
- 如果第二个分数与第一个分数相同，不需要删除任何数字，也是符合条件的。

具体步骤：

读取并解析输入：
- 读取两个分数，分割得到分子和分母的字符串表示。
统计数字次数：
- 对于每个分子和分母，用大小为 10 的数组统计数字 0-9 出现的次数。
计算需要删除的数字：
- 对于每个数字，计算需要从分子和分母中删除的次数，即：
  1
  删除次数 = 第一个分数数字次数 - 第二个分数数字次数
- 如果需要删除的次数为负数，说明第二个分数中包含了第一个分数中没有的数字，直接判定为不符合。
比较删除的数字：
- 检查分子和分母中需要删除的数字及其次数是否相同。
- 如果不相同，判定为不符合。
输出结果：
- 如果上述判断都通过，则输出 “Yes”；
- 否则，输出 “No”。

注意事项：

输入数据范围较大：
- 数字可能长达 10000 位，因此不能直接将数字转换为整数来处理，必须以字符串方式处理。
边界条件：
- 删除后分子和分母不能同时为空，分母不能为零。
- 确保删除的数字不超过原数字中对应数字的次数。

package com.bishi.san60;

import java.util.Scanner;

public class Main2 {
    private static int[] countDigits(String num) {
        int[] counts = new int[10];
        for (char c : num.toCharArray()) {
            counts[c - '0']++;
        }
        return counts;
    }

    private static boolean canReduce(String n1, String d1, String n2, String d2) {
        int[] n1Counts = countDigits(n1);
        int[] n2Counts = countDigits(n2);
        int[] d1Counts = countDigits(d1);
        int[] d2Counts = countDigits(d2);

        int[] deletedNumCounts = new int[10];
        int[] deletedDenCounts = new int[10];

        for (int i = 0; i < 10; i++) {
            if (n1Counts[i] < n2Counts[i]) {
                return false;
            }
            if (d1Counts[i] < d2Counts[i]) {
                return false;
            }
            deletedNumCounts[i] = n1Counts[i] - n2Counts[i];
            deletedDenCounts[i] = d1Counts[i] - d2Counts[i];
        }

        for (int i = 0; i < 10; i++) {
            if (deletedNumCounts[i] != deletedDenCounts[i]) {
                return false;
            }
        }

        return true;
    }

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

        int T = Integer.parseInt(sc.nextLine().trim());

        while (T-- > 0) {
            if (sc.hasNextLine()) {
                String line = sc.nextLine().trim();
                String[] parts = line.split("\\s+");
                if (parts.length >= 2) {
                    String[] frac1 = parts[0].split("/");
                    String[] frac2 = parts[1].split("/");

                    if (frac1.length == 2 && frac2.length == 2) {
                        String n1 = frac1[0];
                        String d1 = frac1[1];
                        String n2 = frac2[0];
                        String d2 = frac2[1];

                        if (canReduce(n1, d1, n2, d2)) {
                            System.out.println("Yes");
                        } else {
                            System.out.println("No");
                        }
                    } else {
                        System.out.println("Invalid");
                    }
                } else {
                    System.out.println("Invalid");
                }
            }
        }
    }
}

Moye活着的记录

360校招笔试编程题