首页 > 数据结构 > Hash表 > POJ 2664 Prerequisites? [解题报告] Java
2013
11-11

POJ 2664 Prerequisites? [解题报告] Java

Prerequisites?

问题描述 :

Freddie the frosh has chosen to take k courses. To meet the degree requirements, he must take courses from each of several categories. Can you assure Freddie that he will graduate, based on his course selection?

输入:

Input consists of several test cases. For each case, the first line of input contains 1 <= k <= 100, the number of courses Freddie has chosen, and 0 <= m <= 100, the number of categories. One or more lines follow containing k 4-digit integers follow; each is the number of a course selected by Freddie. Each category is represented by a line containing 1 <= c <= 100, the number of courses in the category, 0 <= r <= c, the minimum number of courses from the category that must be taken, and the c course numbers in the category. Each course number is a 4-digit integer. The same course may fulfil several category requirements. Freddie's selections, and the course numbers in any particular category, are distinct. A line containing 0 follows the last test case.

输出:

For each test case, output a line containing “yes” if Freddie’s course selection meets the degree requirements; otherwise output “no”.

样例输入:

3 2
0123 9876 2222
2 1 8888 2222
3 2 9876 2222 7654 
3 2
0123 9876 2222
2 2 8888 2222
3 2 7654 9876 2222
0

样例输出:

yes
no

解题代码:

//* @author: [email protected]
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {
   int a=in.nextInt();
   if(a==0) break;
   boolean bb=true;
   int b=in.nextInt();
   HashSet< Integer> hs=new HashSet< Integer>();
   while((a--)!=0) hs.add(in.nextInt());
   while((b--)!=0)
   {
	int c=in.nextInt();
	int d=in.nextInt();
	int cnt=0;
	while((c--)!=0)
	{
          int u=in.nextInt();
	  if(hs.contains(u))cnt++;
	}
	if(cnt< d) bb=false;	
     }
     if(bb) System.out.println("yes");
     else System.out.println("no");	
    }
  }
}

  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”