首页 > 专题系列 > Java解POJ > POJ 2443 Set Operation [解题报告] Java
2013
11-11

POJ 2443 Set Operation [解题报告] Java

Set Operation

问题描述 :

You are given N sets, the i-th set (represent by S(i)) have C(i) element (Here “set” isn’t entirely the same as the “set” defined in mathematics, and a set may contain two same element). Every element in a set is represented by a positive number from 1 to 10000. Now there are some queries need to answer. A query is to determine whether two given elements i and j belong to at least one set at the same time. In another word, you should determine if there exist a number k (1 <= k <= N) such that element i belongs to S(k) and element j also belong to S(k).

输入:

First line of input contains an integer N (1 <= N <= 1000), which represents the amount of sets. Then follow N lines. Each starts with a number C(i) (1 <= C(i) <= 10000), and then C(i) numbers, which are separated with a space, follow to give the element in the set (these C(i) numbers needn't be different from each other). The N + 2 line contains a number Q (1 <= Q <= 200000), representing the number of queries. Then follow Q lines. Each contains a pair of number i and j (1 <= i, j <= 10000, and i may equal to j), which describe the elements need to be answer.

输出:

For each query, in a single line, if there exist such a number k, print “Yes”; otherwise print “No”.

样例输入:

3
3 1 2 3
3 1 2 5
1 10
4
1 3
1 5
3 5
1 10

样例输出:

Yes
Yes
No
No

温馨提示:

The input may be large, and the I/O functions (cin/cout) of C++ language may be a little too slow for this problem.

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Set{
	void init(){
		for(int i=0;i< 35;++i) state[i] = 0;
	}
	void get_int(int cnt){
		int k = cnt/30;
		int posi = cnt%30;
		state[k]|=dir[posi];
	}
	int dir[] = {1,1<<1,1<<2,1<<3,1<<4,1<<5,1<<6,1<<7,1<<8,1<<9,1<<10,1<<11,1<<12,1<<13,1<<14,
1<<15,1<<16,1<<17,1<<18,1<<19,1<<20,1<<21,1<<22,1<<23,1<<24,1<<25,1<<26,1<<27,
1<<28,1<<29,1<<30,1<<31};
	int state[] = new int[35];
}

public class Main {
	
  static final int N = 10000+2;
  public static int get_num(StreamTokenizer in) throws Exception{
		
   in.nextToken();
   return (int) in.nval;
  }

  public static void main(String []args) throws Exception{
		
   int i,j,n,m,u,v;
   Set set[] = new Set[N];
   for(i=0;i< N;++i){
	set[i] = new Set();
	set[i].init();
   }
   //Scanner cin = new Scanner(new FileInputStream("input.txt"));
   //Scanner cin = new Scanner(System.in);
   StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
				
   n = get_num(in);
   //n = cin.nextInt();
   for(i=1;i<=n;++i){
	//m = cin.nextInt();
	m = get_num(in);
	for(j=0;j< m;++j){
		//set[cin.nextInt()].get_int(i);
		set[get_num(in)].get_int(i);
	}
    }
	//m = cin.nextInt();
	m = get_num(in);
	for(i=1;i<=m;++i){
		//u = cin.nextInt();
		//v = cin.nextInt();
		u = get_num(in);
		v = get_num(in);
		for(j=0;j< 35;++j){
			if((set[u].state[j]&set[v].state[j])>0){
				System.out.println("Yes");
				break;
			}
		}
		if(j>=35) System.out.println("No");
	}
		
   }

}

  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。