婚礼摄影网站源码,南昌网站建设渠道,网站模版化配置,天猫折扣店网站建设前言
今天学哈希表#xff0c;然后就第一节晚修赶快写完作业就上了做题了#xff0c;然后就做完了这道题get√。 正题 题目
给出两个集合#xff1a; A是B的一个真子集#xff0c;输出“A is a proper subset of B” B是A的一个真子集#xff0c;输出“B is a proper …前言
今天学哈希表然后就第一节晚修赶快写完作业就上了做题了然后就做完了这道题get√。 正题 题目
给出两个集合 A是B的一个真子集输出“A is a proper subset of B” B是A的一个真子集输出“B is a proper subset of A” A和B是同一个集合输出“A equals B” A和B的交集为空输出“A and B are disjoint” 上述情况都不是输出“I’m confused!” 然后集合大小小于10^5集合中的数大小小于10^9 输入输出建议无视
Input
输入有两行分别表示两个集合每行的第一个整数为这个集合的元素个数至少一个然后紧跟着这个集合的元素均为不同的正整数
Output
只有一行就是A、B的关系。
Sample Input
样例1 2 55 27 2 55 27 样例2 3 9 24 1995 2 9 24 样例3 3 1 2 3 4 1 2 3 4 样例4 3 1 2 3 3 4 5 6 样例5 2 1 2 2 2 3
Sample Output
样例1 A equals B 样例2 B is a proper subset of A 样例3 A is a proper subset of B 样例4 A and B are disjoint 样例5 I’m confused! 解题思路
二分查找快排
这就是用快排排好第一个集合然后用二分查找找另一个集合里的数。
正题哈希表
用哈希表储存第一个集合然后快速判断集合中有没有另一个集合中的数 代码
二分查找快排
#includecstdio
#includealgorithm//c算法库自带快排
using namespace std;
int n1,n2,a1[100001],a2[100001],l,r,ans,s,mid;
char c;
int main()
{scanf(%d,n1);for (int i1;in1;i){scanf(%d,a1[i]);}scanf(%d,n2);for (int i1;in2;i){scanf(%d,a2[i]);}sort(a11,a11n1);//快排for (int i1;in2;i){ansa2[i];//查找对象l1;rn1;//范围while (lr){mid(lr)/2;//取中间值if (a1[mid]ans) break;//找到就退出if (a1[mid]ans) lmid1;else rmid-1;//缩小范围}if (a1[mid]ans) s;//统计相同数}//以下输出不解释if (sn1 sn2) printf(A equals B);else if (sn1) printf(A is a proper subset of B);else if (sn2) printf(B is a proper subset of A);else if (s0) printf(A and B are disjoint);else printf(Im confused!);
}
哈希表
#includecstdio
#includealgorithm
using namespace std;
const int maxn149993;//开个大一些的素数减少冲突
int n1,n2,hash[maxn],x,s;
int hashmath(int x)
{return x%maxn;
}//哈希函数
int locate(int x)//寻找位置
{int i0,whashmath(x);while (imaxn hash[(wi)%maxn]!0 hash[(wi)%maxn]!x)//找到空位相同的或没有空位数组开大已经避免了i;//下一个return (wi)%maxn;//返回值
}
void ins(int x)//插入函数
{int wlocate(x);//寻找位置hash[w]x;//插入
}
bool find(int x)//查找
{int wlocate(x);//寻找位置if (hash[w]x) return true;//是否存在else return false;
}
int main()
{scanf(%d,n1);for (int i1;in1;i){scanf(%d,x);ins(x);//插入}scanf(%d,n2);for (int i1;in2;i){scanf(%d,x);if (find(x)) s;//统计次数}//以下输出if (sn1 sn2) printf(A equals B);else if (sn1) printf(A is a proper subset of B);else if (sn2) printf(B is a proper subset of A);else if (s0) printf(A and B are disjoint);else printf(Im confused!);
}
