本文共 2160 字，大约阅读时间需要 7 分钟。
叉姐初级魔法训练赛A题
1000个集合,每个集合有10000个数每个数不大于10000...
200000个询问是否存在i,j属于同一个set
集合很少...我们就暴力一下就行了...
暴力开10000*1000的bool数组存 数字i在j集合中是否出现...
每次O(n)...
/********************* Template ************************/#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define EPS 1e-8#define DINF 1e15#define MAXN 10050#define LINF 1LL << 60#define MOD 1000000007#define INF 0x7fffffff#define PI 3.14159265358979323846#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define BUG cout<<" BUG! "< inline T L(T a) { return (a << 1);}template inline T R(T a) { return (a << 1 | 1);}template inline T lowbit(T a) { return (a & -a);}template inline T Mid(T a,T b) { return ((a + b) >> 1);}template inline T gcd(T a,T b) { return b ? gcd(b,a%b) : a;}template inline T lcm(T a,T b) { return a / gcd(a,b) * b;}template inline T Min(T a,T b) { return a < b ? a : b;}template inline T Max(T a,T b) { return a > b ? a : b;}template inline T Min(T a,T b,T c) { return min(min(a,b),c);}template inline T Max(T a,T b,T c) { return max(max(a,b),c);}template inline T Min(T a,T b,T c,T d) { return min(min(a,b),min(c,d));}template inline T Max(T a,T b,T c,T d) { return max(max(a,b),max(c,d));}template inline T exGCD(T a, T b, T &x, T &y){ if(!b) return x = 1,y = 0,a; T res = exGCD(b,a%b,x,y),tmp = x; x = y,y = tmp - (a / b) * y; return res;}typedef long long LL; typedef unsigned long long ULL;//typedef __int64 LL; typedef unsigned __int64 ULL;/********************* By F *********************/bool pos[MAXN][1005];int n,m,p;bool query(int a,int b) for(int i = 0 ; i < 1005 ; i++){ if(pos[a][i] && pos[b][i]) return true; return false;}int main(){ //FIN; //FOUT; while(~read(n)){ int i,j,x; mem(pos,false); for(i = 0 ; i < n ; i++){ read(p); while(p--){ read(x); pos[x][i] = 1; } } read(m); while(m--){ read2(i,j); printf("%s\n",query(i,j)?"Yes":"No"); } } return 0;}
转载于:https://www.cnblogs.com/Felix-F/p/3341529.html