题目链接：
L2-005. 集合相似度
时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
陈越
给定两个整数集合，它们的相似度定义为：Nc/Nt*100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。
输入格式：
输入第一行给出一个正整数N（<=50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（<=104），是集合中元素的个数；然后跟M个[0, 109]区间内的整数。
之后一行给出一个正整数K（<=2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。
输出格式：
对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。
输入样例：33 99 87 1014 87 101 5 877 99 101 18 5 135 18 9921 21 3输出样例：
50.00%33.33% 感谢： 分析：
其实这道题只要把题意理解了就ok了，无论如何先将两个集合去重得到新集合，“两个集合都有的不相等整数的个数”意思是两个集合的
交集个数，“两个集合一共有的不相等整数的个数”意思是先将两个集合并起来再去重得到的集合元素个数，理解题意后发现用c++中的set可以
很好的解决这一问题。通过这一题我也对set用法有了更深的体会。（不相等整数的个数 去重）
1.求两集合交集
2.求两集合合并去重后 集合内 元素个数（并集）
集合的交并操作，直接利用set进行处理，因为set有去重的功能，而且set是利用红黑树实现的，查找速度快O(logN)
C++ STL SET容器学习
#include "cstdio"#include "set"#include "map"using namespace std;int Set[500020];///存储所有集合struct locate{ int start;///集合开始下标 int len;///集合长度}locate_set;///每个集合定位int main(){ int n; set s1,s2; map SetFlag;///集合定位 while(~scanf("%d",&n)&&n){ int flag=1,p=0,m=0; for(int i=0;i
悲哀的，最后一个，运行超时。。可能最后一个测试数据太多，而我的算法效率有问题！
学习学长学姐版本：
#include#include #include using namespace std;const int maxn = 55;set s[maxn];int n;int main() { while(~scanf("%d", &n)) { int cnt; for(int i = 0; i < n; i++) { if(!s[i].empty())s[i].clear(); scanf("%d", &cnt); int x; for(int j = 0; j < cnt; j++) { scanf("%d", &x); s[i].insert(x); } } scanf("%d", &cnt); int u,v; for(int i = 0; i < cnt; i++) { scanf("%d%d", &u, &v); u--,v--; int same = 0; int size_s1 = s[u].size(); int size_s2 = s[v].size(); set ::iterator it; for(it = s[u].begin(); it != s[u].end(); it++) { if(s[v].find(*it) != s[v].end()) { same++; } } int nc = same; int nt = size_s1+size_s2-same; double ans = (nc*1.0)/(nt*1.0)*100; printf("%.2lf%%\n", ans); } } return 0;}
可已看出，我的代码明显复杂，我绕了一大圈，而人家直接定义一个set数组。也不知道当时脑子抽的什么风。
但是没关系，我很弱，但在提升。
#include#include #include using namespace std;int main() { int n, m, k, temp, a, b; scanf("%d", &n); vector > v(n); for(int i = 0; i < n; i++) { scanf("%d", &m); set s; for(int j = 0; j < m; j++) { scanf("%d", &temp); s.insert(temp); } v[i] = s; } scanf("%d", &k); for(int i = 0; i < k; i++) { scanf("%d %d", &a, &b); int nc = 0, nt = v[b-1].size(); for(auto it = v[a-1].begin(); it != v[a-1].end(); it++) { if(v[b-1].find(*it) == v[b-1].end()) {//同时计算并交集 nt++; } else { nc++; } } double ans = (double)nc / nt * 100; printf("%.2f%%\n", ans); } return 0;}
揭穿事实，不要逃避。
#include "cstdio"#include "set"using namespace std;int main(){ set Set[55]; int n,m,temp,k; while(~scanf("%d",&n)&&n){ for(int i=0;i