2013
11-11

# 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);

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才能知道答案。