目录

4791. 死或生 - 简单模拟ac

4792. 最大价值 - 简单构造ac

4793. 危险程度 - dfs / 并查集

1、dfs

 2、并查集

4791. 死或生 - 简单模拟ac

import java.util.*;class Main
{public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();int s1l=0,s1d=0,s2l=0,s2d=0;while(n-->0){int t=sc.nextInt(),x=sc.nextInt(),y=sc.nextInt();if(t==1) {s1l+=x;s1d+=y;}else{s2l+=x;s2d+=y;}}if(s1l>=s1d) System.out.println("LIVE");else System.out.println("DEAD");if(s2l>=s2d) System.out.println("LIVE");else System.out.println("DEAD");}
}

4792. 最大价值 - 简单构造ac

4792. 最大价值 - AcWing题库

import java.util.*;class Main
{public static void main(String[] args){Scanner sc=new Scanner(System.in);String s=sc.next();int n=sc.nextInt();int[] ck=new int[27];int max=-1;for(int i=0;i<26;i++){ck[i]=sc.nextInt();max=Math.max(max,ck[i]);}int res=0;for(int i=0;i0) res+=max*(++x);System.out.print(res);}
}

4793. 危险程度 - dfs / 并查集

4793. 危险程度 - AcWing题库

1、dfs

思路：

先将能发生反应的化学物质连接起来（无向图）

要使危险程度最大，则要把能发生反应的试剂全部丢在一起

所以答案就是2^(每个连通块内点数-1）

import java.util.*;class Main
{static int[][] g=new int[100][100];static boolean[] st=new boolean[100];static long res=1;public static void dfs(int u){st[u]=true;for(int i=1;i0){int x=sc.nextInt(),y=sc.nextInt();g[x][y]=1;g[y][x]=1;}for(int i=1;i<=n;i++)if(st[i]==false) dfs(i); System.out.print(res);}
}

 2、并查集

思路：

将能反应的试剂分成集合

如果该试剂不是这个集合的父节点 则res*=2

import java.util.*;class Main
{static int[] f=new int[100];static long res=1;public static int find(int x){if(x!=f[x]) f[x]=find(f[x]);return f[x];}public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();for(int i=1;i<=n;i++) f[i]=i;while(m-->0){int x=sc.nextInt(),y=sc.nextInt();f[find(x)]=find(y);}for(int i=1;i<=n;i++)if(f[i]!=i) res*=2; System.out.print(res);}
}