最新华为OD机试真题-LYA的生日聚会(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🍏 LYA的生日聚会
问题描述
LYA要举办一个生日聚会,邀请了 位朋友参加。但是,由于最近流感病毒正在肆虐,LYA希望找出可能被感染的人群,以便及时采取防控措施。根据流行病学调查和大数据分析,得到了每个人之间是否有过密切接触的信息。现在已知一组确诊病例的编号
,请你帮助LYA找出哪些人需要进行病毒检测,并输出需要检测的人数。注意,确诊病例本身不需要再做检测。
需要进行病毒检测的人,是指在病毒传播链条上的所有人员,即所有可能被确诊病例直接或间接传染的人。例如,如果A是确诊病例,A和B有过接触,B和C有过接触,C和D有过接触,那么B、C、D都需要进行病毒检测。
输入格式
第一行包含一个正整数 ,表示总人数。
第二行包含若干个用逗号隔开的正整数,表示确诊病例的编号。
接下来 行,每行包含
个用逗号隔开的数字,其中第
行的第
个数字表示编号为
的人是否与编号为
的人有过密切接触。数字为1表示有过接触,为0表示没有接触。
输出格式
输出一个整数,表示需要进行病毒检测的人数。
样例输入
5
1,2
1,1,0,1,0
1,1,0,0,0
0,0,1,0,1
1,0,0,1,0
0,0,1,0,1
样例输出
3
样例解释
在这个样例中,总共有5个人,编号分别为0到4。其中,编号为1和2的人是确诊病例。根据接触信息,我们可以发现:
- 编号为1的人和编号为0的人有过接触;
- 编号为0的人和编号为3的人有过接触;
- 编号为2的人和编号为4的人有过接触。
因此,编号为0、3、4的人都可能被感染,需要进行病毒检测。所以输出3,表示总共有3个人需要检测。
数据范围
- 人员编号从0开始
题解
我们可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来找出所有可能被感染的人。首先,将所有确诊病例加入到一个集合中,作为初始的感染者集合。然后,遍历每个人,如果这个人与任何一个已经在感染者集合中的人有过接触,就将其加入到感染者集合中。重复这个过程,直到感染者集合不再扩大为止。最后,感染者集合的大小减去初始确诊病例的数量,就是需要进行病毒检测的人数。
参考代码
- Python
n = int(input())
confirmed = set(map(int, input().split(',')))
contact = [list(map(int, input().split(','))) for _ in range(n)]
def num_to_test(n, confirmed, contact):
infected = confirmed.copy()
for i in range(n):
for j in range(n):
if contact[i][j] == 1 or contact[j][i] == 1:
if i in infected:
infected.add(j)
if j in infected:
infected.add(i)
return len(infected) - len(confirmed)
print(num_to_test(n, confirmed, contact))
- Java
import java.util.*;
public class Main {
public st
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测