题目链接:https://www.patest.cn/contests/gplt/L2-005
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位的百分比数字。
输入样例:
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
输出样例:
50.00%
33.33%感谢:分析:
其实这道题只要把题意理解了就ok了,无论如何先将两个集合去重得到新集合,“两个集合都有的不相等整数的个数”意思是两个集合的
交集个数,“两个集合一共有的不相等整数的个数”意思是先将两个集合并起来再去重得到的集合元素个数,理解题意后发现用c++中的set可以
很好的解决这一问题。通过这一题我也对set用法有了更深的体会。(不相等整数的个数 去重)
1.求两集合交集
2.求两集合合并去重后 集合内 元素个数(并集)
集合的交并操作,直接利用set
进行处理,因为set
有去重的功能,而且set
是利用红黑树实现的,查找速度快O(logN)
C++ STL SET容器学习
http://www.cnblogs.com/BeyondAnyTime/archive/2012/08/13/2636375.html
http://www.cplusplus.com/reference/set/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<int> s1,s2;
map<int,locate> SetFlag;///集合定位
while(~scanf("%d",&n)&&n){
int flag=1,p=0,m=0;
for(int i=0;i<n;i++){
scanf("%d",&m);
locate_set.len=m;
locate_set.start=p;
SetFlag[flag++]=locate_set;
for(int j=0;j<m;j++){
scanf("%d",&Set[p++]);
}
}
///测试
int k=0,test1=0,test2=0;
scanf("%d",&k);
for(int i=0;i<k;i++){
s1.clear();s2.clear();
scanf("%d%d",&test1,&test2);
s1.insert(Set+SetFlag[test1].start,Set+SetFlag[test1].start+SetFlag[test1].len);
s2.insert(Set+SetFlag[test2].start,Set+SetFlag[test2].start+SetFlag[test2].len);
int Count1=0,Count2=0;///交集并集 元素个数
set<int>::iterator iter;
for(iter = s1.begin() ; iter != s1.end() ; ++iter)
{
if(s2.find(*iter)!=s2.end()){
Count1++;
}
}
//printf("%dn",Count1);
s1.insert(s2.begin(),s2.end());
Count2=s1.size();
printf("%.2lf%%n",(double)Count1/Count2*100);
}
}
}
悲哀的,最后一个,运行超时。。可能最后一个测试数据太多,而我的算法效率有问题!
学习学长学姐版本:
学长:http://www.cnblogs.com/yinzm/p/5498633.html
#include<cstdio>
#include<set>
#include<cstdlib>
using namespace std;
const int maxn = 55;
set<int> 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<int>::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数组。也不知道当时脑子抽的什么风。
但是没关系,我很弱,但在提升。
学姐:http://www.liuchuo.net/archives/2079
#include <set>
#include <vector>
#include <cstdio>
using namespace std;
int main() {
int n, m, k, temp, a, b;
scanf("%d", &n);
vector<set<int>> v(n);
for(int i = 0; i < n; i++) {
scanf("%d", &m);
set<int> 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<int> Set[55];
int n,m,temp,k;
while(~scanf("%d",&n)&&n){
for(int i=0;i<n;i++){
scanf("%d",&m);
for(int j=0;j<m;j++){
scanf("%d",&temp);
Set[i].insert(temp);
}
}
scanf("%d",&k);
int n=0,u=0,test01,test02;
for(int i=0;i<k;i++){
scanf("%d%d",&test01,&test02);
test01--;
test02--;
n=0;u=Set[test02].size();
for(__typeof(Set[test01].begin()) it=Set[test01].begin();it!=Set[test01].end();it++){
if(Set[test02].find(*it)==Set[test02].end()){
u++;
}else{
n++;
}
}
printf("%.2lf%%n",(double)n/u*100);
}
}
}
View Code
原文链接: https://www.cnblogs.com/kimsimple/p/6528599.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/250613
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!