Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:有没有做出来的呀?,能不能贴一下代码In Reply To:有没有做出来的呀?,能不能贴一下代码 Posted by:kuroto at 2018-04-21 21:08:17 import java.util.*; public class Main { static int n,m,count,max=350; static Node[] nodes; static class Node implements Comparable<Node>{ int len; int[] arr; @Override public int compareTo(Node o) { return this.len - o.len; } } // 用类似归并排序的方式检查a[]是否包含b[],如果包含,将a[]的相应judge[]置为true static void merge(int[] a,int[] b,boolean[] judge){ int i=0,j=0; boolean[] temp = new boolean[a.length]; while (i<b.length && j<a.length){ if(b[i]==a[j]){ temp[j] = true; i++; j++; }else if(b[i]<a[j]){ return; }else { j++; } } if(i<b.length) return; for(i=0;i<a.length;i++){ if(temp[i]){ judge[i] = true; } } } // 判断judge[]是否全true static boolean is_full(boolean[] judge){ for(int i=0;i<judge.length;i++){ if(!judge[i]) return false; } return true; } static void work(){ count=0; // 对每组试剂,枚举包含疾病长度小于等于它的试剂,看能否由它们组成 for(int i=1;i<m;i++){ boolean[] judge = new boolean[nodes[i].len]; for(int j=0;j<i;j++){ merge(nodes[i].arr,nodes[j].arr,judge); if(is_full(judge)){ count++; break; } } } } // 对每组试剂包含的疾病编号排序,再对所有试剂按包含的疾病数量排序 public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); while (n!=0){ nodes = new Node[m]; for(int i=0;i<m;i++){ nodes[i] = new Node(); int len = sc.nextInt(); nodes[i].len = len; nodes[i].arr = new int[len]; for(int j=0;j<len;j++){ nodes[i].arr[j] = sc.nextInt(); } Arrays.sort(nodes[i].arr); } Arrays.sort(nodes); work(); System.out.println(count); n = sc.nextInt(); m = sc.nextInt(); } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator