Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:有没有做出来的呀?,能不能贴一下代码

Posted by niewei1986 at 2020-07-02 15:39:44 on Problem 2943
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator