| ||||||||||
| 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