企业官网建设流程全解析

网页设计的板式,南通 网站优化,dw 做静态网站,建设网站说只给前端源码是什么意思(新卷,100分)- 精准核酸检测#xff08;Java JS Python C#xff09;题目描述为了达到新冠疫情精准防控的需要#xff0c;为了避免全员核酸检测带来的浪费#xff0c;需要精准圈定可能被感染的人群。现在根据传染病流调以及大数据分析#xff0c;得到了…(新卷,100分)- 精准核酸检测Java JS Python C题目描述为了达到新冠疫情精准防控的需要为了避免全员核酸检测带来的浪费需要精准圈定可能被感染的人群。现在根据传染病流调以及大数据分析得到了每个人之间在时间、空间上是否存在轨迹交叉。现在给定一组确诊人员编号X1,X2,X3,...,Xn在所有人当中找出哪些人需要进行核酸检测输出需要进行核酸检测的人数。注意确诊病例自身不需要再做核酸检测需要进行核酸检测的人是病毒传播链条上的所有人员即有可能通过确诊病例所能传播到的所有人。例如A是确诊病例A和B有接触、B和C有接触、C和D有接触、D和E有接触那么B\C\D\E都是需要进行核酸检测的人。输入描述第一行为总人数 N第二行为确认病例人员编号确诊病例人员数量 N用逗号分割第三行开始为一个 N * N 的矩阵表示每个人员之间是否有接触0表示没有接触1表示有接触。输出描述整数需要做核酸检测的人数备注人员编号从0开始0 N 100用例输入51,21,1,0,1,01,1,0,0,00,0,1,0,11,0,0,1,00,0,1,0,1输出3说明编号为1、2号的人员为确诊病例。1号和0号有接触0号和3号有接触。2号和4号有接触。所以需要做核酸检测的人是0号、3号、4号总计3人需要进行核酸检测。题目解析本题可以用并查集解题。即将有接触的人进行合并操作纳入到同一个连通分量中。比如matrix[i]][j] 1即 i 和 j 就处于同一个连通分量中需要进行合并。另外本题的接触关系矩阵matrix是沿对角线对称的因此只需要遍历对角线一边即可。当遍历完所有接触关系后就可以求解每一个连通分量中的节点数即每个接触群体的人数求解原理如下并查集底层的fa数组fa数组索引代表每个节点fa数组元素代表对应索引的节点的根节点而同一个连通分量中的节点的根都是相同的因此我们需要对fa每一个数组索引找一下根这里可以使用并查集的find操作递归实现最后统计同一个根下的节点数量即为同一个接触群体的人数。当每个接触群体人数求解出来后我们只需要统计”确诊病例人员编号“对应的根连通分量下的人数即可。最后的统计的总人数需要减去确诊病例的数量因为题目说确诊病例自身不需要再做核酸检测本题需要注意的是有可能多个确诊病人在同一个连通分量重此时需要注意避免重复统计。JS算法源码const rl require(readline).createInterface({ input: process.stdin }); var iter rl[Symbol.asyncIterator](); const readline async () (await iter.next()).value; void (async function () { const n parseInt(await readline()); const confirmed (await readline()).split(,).map(Number); const matrix []; for (let i 0; i n; i) { matrix.push((await readline()).split(,).map(Number)); } console.log(getResult(n, confirmed, matrix)); })(); class UnionFindSet { constructor(n) { this.fa new Array(n).fill(true).map((_, idx) idx); } // 查x站点对应的顶级祖先站点 find(x) { while (x ! this.fa[x]) { x this.fa[x]; } return x; } // 合并两个站点其实就是合并两个站点对应的顶级祖先节点 union(x, y) { let x_fa this.find(x); let y_fa this.find(y); if (x_fa ! y_fa) { // 如果两个站点祖先相同则在一条链上不需要合并否则需要合并 this.fa[y_fa] x_fa; // 合并站点即让某条链的祖先指向另一条链的祖先 } } } function getResult(n, confirmed, matrix) { const ufs new UnionFindSet(n); for (let i 0; i n; i) { for (let j i; j n; j) { if (matrix[i][j] 1) { // 有过接触的人进行合并 ufs.union(i, j); } } } // 统计每个接触群体连通分量中的人数 const cnts new Array(n).fill(0); for (let i 0; i n; i) { const fa ufs.find(i); cnts[fa]; } // 记录已统计过的感染群体 const confirmed_fa new Set(); // 将有感染者的接触群体的人数统计出来 let ans 0; for (let i of confirmed) { const fa ufs.find(i); // 已统计过的感染群体不再统计 if (confirmed_fa.has(fa)) continue; confirmed_fa.add(fa); ans cnts[fa]; } // 最终需要做核酸的人数不包括已感染的人 return ans - confirmed.length; }Java算法源码import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n Integer.parseInt(sc.nextLine()); int[] confirmed Arrays.stream(sc.nextLine().split(,)).mapToInt(Integer::parseInt).toArray(); int[][] matrix new int[n][n]; for (int i 0; i n; i) { matrix[i] Arrays.stream(sc.nextLine().split(,)).mapToInt(Integer::parseInt).toArray(); } System.out.println(getResult(n, confirmed, matrix)); } public static int getResult(int n, int[] confirmed, int[][] matrix) { UnionFindSet ufs new UnionFindSet(n); for (int i 0; i n; i) { for (int j i; j n; j) { if (matrix[i][j] 1) { // 有过接触的人进行合并 ufs.union(i, j); } } } // 统计每个接触群体连通分量中的人数 int[] cnts new int[n]; for (int i 0; i n; i) { int fa ufs.find(i); cnts[fa]; } // 记录已统计过的感染群体 HashSetInteger confirmed_fa new HashSet(); // 将有感染者的接触群体的人数统计出来 int ans 0; for (int i : confirmed) { int fa ufs.find(i); // 如果该感染群体已统计过则不再统计 if (confirmed_fa.contains(fa)) continue; confirmed_fa.add(fa); ans cnts[fa]; } // 最终需要做核酸的人数不包括已感染的人 return ans - confirmed.length; } } // 并查集实现 class UnionFindSet { int[] fa; public UnionFindSet(int n) { this.fa new int[n]; for (int i 0; i n; i) fa[i] i; } public int find(int x) { if (x ! this.fa[x]) { this.fa[x] this.find(this.fa[x]); return this.fa[x]; } return x; } public void union(int x, int y) { int x_fa this.find(x); int y_fa this.find(y); if (x_fa ! y_fa) { this.fa[y_fa] x_fa; } } }Python算法源码# 并查集实现 class UnionFindSet: def __init__(self, n): self.fa [i for i in range(n)] def find(self, x): if x ! self.fa[x]: self.fa[x] self.find(self.fa[x]) return self.fa[x] return x def union(self, x, y): x_fa self.find(x) y_fa self.find(y) if x_fa ! y_fa: self.fa[y_fa] x_fa # 输入获取 n int(input()) confirmed list(map(int, input().split(,))) matrix [list(map(int, input().split(,))) for _ in range(n)] # 算法入口 def getResult(): ufs UnionFindSet(n) for i in range(n): for j in range(i, n): if matrix[i][j] 1: # 有过接触的人进行合并 ufs.union(i, j) # 统计每个接触群体连通分量中的人数 cnts [0] * n for i in range(n): fa ufs.find(i) cnts[fa] 1 # 记录已统计过的可能感染群体 confirmed_fa set() # 将有感染者的接触群体的人数统计出来 ans 0 for i in confirmed: fa ufs.find(i) # 已统计过的可能感染群体不再统计 if fa in confirmed_fa: continue confirmed_fa.add(fa) ans cnts[fa] # 最终需要做核酸的人数不包括已感染的人 return ans - len(confirmed) # 算法调用 print(getResult())C算法源码#include stdio.h #include stdlib.h #define MAX_SIZE 100 /** 并查集定义 **/ typedef struct { int *fa; } UFS; UFS *new_UFS(int n) { UFS *ufs (UFS *) malloc(sizeof(UFS)); ufs-fa (int *) malloc(sizeof(int) * n); for (int i 0; i n; i) { ufs-fa[i] i; } return ufs; } int find_UFS(UFS *ufs, int x) { if (x ! ufs-fa[x]) { ufs-fa[x] find_UFS(ufs, ufs-fa[x]); return ufs-fa[x]; } return x; } void union_UFS(UFS *ufs, int x, int y) { int x_fa find_UFS(ufs, x); int y_fa find_UFS(ufs, y); if (x_fa ! y_fa) { ufs-fa[y_fa] x_fa; } } int main() { int n; scanf(%d, n); int confirmed[MAX_SIZE]; int confirmed_size 0; while (scanf(%d, confirmed[confirmed_size])) { if (getchar() ! ,) break; } UFS *ufs new_UFS(n); for (int i 0; i n; i) { for (int j 0; j n; j) { int v; scanf(%d, v); // 有过接触的人进行合并 if (v 1) { union_UFS(ufs, i, j); } getchar(); } } // 统计每个接触群体连通分量中的人数 int cnts[MAX_SIZE] {0}; for (int i 0; i n; i) { int fa find_UFS(ufs, i); cnts[fa]; } // 记录已统计过的可能感染群体 int confirmed_fa[MAX_SIZE] {0}; // 将有感染者的接触群体的人数统计出来 int ans 0; for (int i 0; i confirmed_size; i) { int fa find_UFS(ufs, confirmed[i]); // 已统计过的可能感染群体不再统计 if(confirmed_fa[fa]) continue; confirmed_fa[fa] 1; ans cnts[fa]; } // 最终需要做核酸的人数不包括已感染的人 printf(%d\n, ans - confirmed_size); return 0; }