[编程题]Set Similarity (25)
- 热度指数：4855 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
Given two sets of integers, the similarity of the sets is defined to be
Nc/Nt*100%, where Nc is the number of distinct common numbers shared by
the two sets, and Nt is the total number of distinct numbers in the two
sets. Your job is to calculate the similarity of any given pair of sets.
输入描述:
Each input file contains one test case. Each case first gives a positive integer N (<=50) which is the total number of sets. Then N lines follow, each gives a set with a positive M (<=104) and followed by M integers in the range [0, 109]. After the input of sets, a positive integer K (<=2000) is given, followed by K lines of queries. Each query gives a pair of set numbers (the sets are numbered from 1 to N). All the numbers in a line are separated by a space.
输出描述:
For each query, print in one line the similarity of the sets, in the percentage form accurate up to 1 decimal place.
示例1
输入
3 3 99 87 101 4 87 101 5 87 7 99 101 18 5 135 18 99 2 1 2 1 3
输出
50.0% 33.3%
题目里把10^9写成109真是...天真地直接vis数组记录。还是得老实用集合才好
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
const int N = 50;
int n, k, m;
set<int> s[N];
void solve(int a, int b)
{
set<int>::iterator ia, ib;
int cnt = 0;
ia = s[a].begin();
ib = s[b].begin();
while(1) {
while(ia != s[a].end() && *ia < *ib)
ia++;
while(ib != s[b].end() && *ib < *ia)
ib++;
if(ia == s[a].end() || ib == s[b].end())
break;
if(*ib == *ia) {
cnt++;
ia++;
ib++;
}
}
int sum = s[a].size() + s[b].size() - cnt;
printf("%.1f%%\n", double(cnt*100) / sum);
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &m);
for(int j = 0; j < m; j++) {
int t;
scanf("%d", &t);
s[i].insert(t);
}
}
scanf("%d", &k);
for(int i = 0; i < k; i++) {
int a, b;
scanf("%d%d", &a, &b);
solve(a - 1, b - 1);
}
return 0;
}
编辑于 2017-07-06 20:37:44
回复(1)
import java.util.HashSet;
import java.util.Scanner;
public class No1021 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();// the total number of sets.
HashSet[] sets = new HashSet[n];
for(int i = 0;i<n;i++){
int m = in.nextInt();
sets[i] = new HashSet<Integer>(m);
String[] nums = in.nextLine().split(" ");
for(int j = 1;j<=m;j++)
sets[i].add(Integer.parseInt(nums[j]));
}
int k = in.nextInt();
for(int i = 0;i<k;i++){
int s = in.nextInt()-1;
int e = in.nextInt()-1;
HashSet<Integer> s1 = sets[s];
HashSet<Integer> s2 = sets[e];
int comm = 0;
for (Integer integer : s2) {
if(s1.contains(integer))
comm++;
}
double diff = s1.size()+s2.size()-comm;
System.out.printf("%.1f%%\n",(comm/diff)*100);
}
}
}
发表于 2016-07-19 22:07:35
回复(1)
#include <iostream>
#include <set>
using namespace std;
set<int> num[55];
int main(){
int n,m,x,k,n1,n2;
cin>>n;
for(int i=1;i<=n;i++){
cin>>m;
for(int j=0;j<m;j++){
cin>>x;
num[i].insert(x); //将元素x加入集合num[i]中
}
}
cin>>k; //k个查询
for(int i=0;i<k;i++){
cin>>n1>>n2; //比较集合num[n1]和num[n2]
int same=0,sum=num[n2].size(); //same为相同元素个数,sum为不同元素个数
for(set<int>::iterator it=num[n1].begin();it!=num[n1].end();it++){ //遍历集合num[n1]
if(num[n2].find(*it)!=num[n2].end()) same++; //若能在num[n2]中找到该元素
else sum++; //若在num[n2]中找不到该元素
}
printf("%.1f%%\n",same*100.0/sum);
}
return 0;
}
编辑于 2018-03-06 22:42:42
回复(0)
#pragma warning (disable:4996)
#include <cstdio>
#include <iostream>
#include <set>
using namespace std;
#define MAX 10000
int N, M, K, cnt = 0;
set<int> s[MAX]; double res[MAX];
int main() {
cin >> N; int tmp;
for (int i = 1; i <= N; ++i) {
cin >> M;
for (int j = 0; j < M; ++j) {
cin >> tmp; s[i].insert(tmp);
}
}
cin >> K; int a, b;
for (int i = 0; i < K; ++i) {
cin >> a >> b;
double nc = 0.0, nt = (double)(s[a].size()) + (double)s[b].size();
for (auto it = s[b].begin(); it != s[b].end(); ++it)
if (s[a].find(*it) != s[a].end())++nc;
res[cnt++] = nc / (nt - nc) * 100;
}
for (int i = 0; i < K; ++i) {
printf("%.1f%%", res[i]);
if (i < K - 1)cout << endl;
}
return 0;
}
发表于 2021-02-23 23:40:10
回复(0)
#include <iostream>
#include <set>
#include <stdio.h>
using namespace std;
int main() {
int set_amount;
cin>>set_amount;
set<int> set_container[set_amount];
for(int i=0; i<set_amount; i++) {
int amount;
cin>>amount;
for(int j=0; j<amount; j++) {
int num;
cin>>num;
set_container[i].insert(num);
}
}
int test;
cin>>test;
for(int i=0; i<test; i++) {
int set1,set2;
cin>>set1>>set2;
int repeat=0;
set<int>::iterator iter1;
for(iter1=set_container[set1-1].begin(); iter1!=set_container[set1-1].end(); iter1++) {
if(set_container[set2-1].count(*iter1)) {
repeat++;
}
}
printf("%.1f%%\n",(float)repeat/(float)(set_container[set1-1].size()+set_container[set2-1].size()-repeat)*100);
}
return 0;
} 多学stl真的是捷径
发表于 2018-02-25 22:19:48
回复(0)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
set<int> mySet[maxn];
int N, K;
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d", &N);
int M, read;
for(int i = 1; i <= N; i++) {
scanf("%d", &M);
for(int j = 0; j < M; j++) {
scanf("%d", &read);
mySet[i].insert(read);
}
}
scanf("%d", &K);
int x, y;
for(int i = 0; i < K; i++) {
scanf("%d%d", &x, &y);
int sameNum = 0;
for(set<int>::iterator it = mySet[x].begin(); it != mySet[x].end(); it++) {
if(mySet[y].find(*it) != mySet[y].end()) {
sameNum++;
}
}
int totalNum = mySet[x].size() + mySet[y].size() - sameNum;
printf("%.1f%\n", ((sameNum*1.0)/(totalNum))*100);
}
return 0;
}
import java.util.HashSet;
import java.util.Scanner;
public class SetSimilarity {
private static final int maxn = 55;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
HashSet mySet[] = new HashSet[N];
for(int i = 0; i < N; i++) {
mySet[i] = new HashSet<>();
}
for(int i = 0; i < N; i++) {
int M = scanner.nextInt();
int read;
for(int j = 0; j < M; j++) {
read = scanner.nextInt();
mySet[i].add(read);
}
}
int K = scanner.nextInt();
for(int i = 0; i < K; i++) {
int x = scanner.nextInt()-1;
int y = scanner.nextInt()-1;
int sameNum = 0;
HashSet<Integer> s1 = mySet[x];
HashSet<Integer> s2 = mySet[y];
for(Integer c : s1) {
if(s2.contains(c)) sameNum++;
}
int diff = s1.size() + s2.size() - sameNum;
System.out.printf("%.1f%%\n", (sameNum*1.0/diff)*100);
}
}
}
发表于 2017-08-24 17:05:17
回复(0)
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int MAXN = 55;
set<int> Set[MAXN];
int N,K;
int main()
{ cin>>N; int M,num; for(int i=1;i<=N;i++) { cin>>M; for(int j=0;j<M;j++) { cin>>num; Set[i].insert(num); } } cin>>K; int x,y; for(int i=0;i<K;i++) { cin>>x>>y; int sameNum = 0; for(set<int>::iterator it=Set[x].begin();it!=Set[x].end();it++) if(Set[y].find(*it) != Set[y].end()) sameNum++; int totalNum = Set[x].size() + Set[y].size() - sameNum; printf("%.1f%%\n",((sameNum*1.0)/totalNum)*100); } return 0;
}
发表于 2018-02-28 01:08:45
回复(0)
这种题都不敢用cin cout
set的set_intersection()、set_union()也会超时。
#include<bits/stdc++.h>
using namespace std;
set<int> s[51];
void cmp(int a,int b){
int x=s[b].size(),y=0;
for(auto it=s[a].begin();it!=s[a].end();it++){
if(s[b].find(*it)!=s[b].end()){
y++;
}
else x++;
}
printf("%.1f%\n",y*100.0/x);
}
int main() {
int n,m,x;
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d",&m);
for(int j=0; j<m; j++) {
scanf("%d",&x);
s[i].insert(x);
}
}
int k;
scanf("%d",&k);
for(int i=0;i<k;i++){
int a,b;
scanf("%d %d",&a,&b);
cmp(a,b);
}
return 0;
}
发表于 2022-11-19 15:51:19
回复(0)
真是的，C++11都不用，全用迭代器遍历了🤷♂️
更多PAT甲级题解--acking-you.github.io
题目
题目理解
这又是一场关于题目理解的博弈！！！
关键句意：
where Nc is the number of distinct common numbers shared by the two sets, and Nt is the total number of distinct numbers in the two sets.
翻译：
这里的Nc是两个不含相同数字集合的公共数字的数量，Nt是两个不含相同数字集合的数字总量。
- 没错，这个题意乍一看根本就翻译不准，得结合题目的示例进行翻译，其实也就是每个集合中不会含有相同的数字，然后Nc是两个集合的交集，Nt是两个集合的总数量。这样一说题目是不是就变得非常简单了。。。
所以很简单的直接用STL解决就行了，直接用unordered_set记录给定的集合数据。
解题代码
这次直接提交了，没啥可说的😂
无序容器这效率也是yyds！C++11的语法有用白不用！！auto&& : set yyds！！
#include <bits/stdc++.h>
using namespace std;
int N, K;
void solve() {
ios::sync_with_stdio(false);
cin >> N;
unordered_set<int> Set[N + 1];
for (int i = 1; i <= N; i++) {//创建集合
int m;
cin >> m;
while (m--) {
int d;
cin >> d;
Set[i].insert(d);
}
}
cin >> K;
while (K--) {//打印答案
int a, b;
cin >> a >> b;
int nc = 0, nt = Set[b].size();
for (auto &&it :Set[a]) {
if (Set[b].count(it))
nc++;
else
nt++;
}
double ans = (double) nc / nt * 100;
cout << fixed << setprecision(1) << ans << '%' << endl;
}
}
int main() {
solve();
return 0;
}
发表于 2021-10-04 15:03:52
回复(0)
主要是对set容器的使用，其实不难
//set_similarity
#include<iostream>
#include<set>
#include<vector>
#include<iomanip>
using namespace std;
vector<set<int> > list;
void check(int a,int b){
double similar=0;
double same,total;
if(list[b-1].size()<list[a-1].size()){
for(set<int>::iterator it=list[b-1].begin();it!=list[b-1].end();it++){
if(list[a-1].find(*it)!=list[a-1].end())same++;
}
}
else{
for(set<int>::iterator it=list[a-1].begin();it!=list[a-1].end();it++){
if(list[b-1].find(*it)!=list[b-1].end())same++;
}
}
total=list[a-1].size()+list[b-1].size();
similar=same/(total-same);
cout<<fixed<<setprecision(1)<<similar*100<<"%";
}
int main(){
int n;
cin>>n;
vector<set<int> > q(n);
int temp,temp2,temp3;
for(int i=0;i<n;i++){
cin>>temp;
for(int j=0;j<temp;j++){
cin>>temp2;
q[i].insert(temp2);
}
}
cin>>temp;
vector<int> pp1;
vector<int> pp2;
for(int i=0;i<temp;i++){
cin>>temp2>>temp3;
pp1.push_back(temp2);
pp2.push_back(temp3);
}
list=q;
for(int i=0;i<temp;i++){
temp2=pp1[i];temp3=pp2[i];
check(temp2,temp3);if(i!=temp-1)cout<<endl;
}
return 0;
}
发表于 2021-08-16 19:45:24
回复(1)
第一次用set。还是挺方便的。记录一下
#include<iostream>
(720)#include<vector>
#include<algorithm>
(831)#include<set>
/*
STL中有直接的集合库，set，其中的元素可用insert添加。
set中的元素默认是按升序排列的。
set不能用下标顺序访问，只能用迭代器遍历访问
求两个集合的交集大小可以直接同时遍历两个集合
求两个集合的并集大小可以用两个集合的大小之和再减去两个集合的交集大小
*/
using namespace std;
const int MAXN = 110;
const int MSET = 51;
int main() {
//freopen("C:\\Users\\47\\Desktop\\1.txt","r",stdin);
int numofSets;
cin >> numofSets;
set<int>Sets[MSET];
for (int i = 0; i < numofSets; i++) {
int numofEachSet, x;
cin >> numofEachSet;
for (int j = 0; j < numofEachSet; j++) {
cin >> x;
Sets[i].insert(x);
}
}
int numofQuery;
cin >> numofQuery;
while (numofQuery--) {
int a, b;//a,b为要查询的两个集合
cin >> a >> b;
int NC = 0, NT = 0;
set<int>::iterator ai = Sets[a - 1].begin();
set<int>::iterator bj = Sets[b - 1].begin();
while (ai!= Sets[a - 1].end()&& bj!=Sets[b - 1].end()) {
if (*ai == *bj) {
NC++;
ai++;
bj++;
}
else if (*ai < *bj) {
ai++;
}
else {
bj++;// 135 236
}
}
NT = Sets[a - 1].size() + Sets[b - 1].size()-NC;
printf("%.1lf%%\n", (NC*1.0/NT*1.0)*100);
}
}
发表于 2020-03-04 10:10:55
回复(0)
N=int(input())
sets=[]
sets=[list(map(int,input().split()))[1:] for i in range(0,N)]
K=int(input())
for i in range(0,K):
a,b=map(int,input().split())
res=len(set(sets[a-1])&set(sets[b-1]))/len(set(sets[a-1])|set(sets[b-1]))
print(format(res,'.1%'))
发表于 2020-02-07 11:43:18
回复(0)
#include<iostream>
#include<unordered_map>
#include<iomanip>
#include<vector>
using namespace std;
vector<int> arr[51];
unordered_map<int,int> S1[51]; // S1存每个数组单独的数
int T,num,element;
double compare(int num1, int num2) {
if(!S1[num1].size()) { // 没存过就存一下
for(int i = 0; i < arr[num1].size(); ++i) {
element = arr[num1][i];
S1[num1].insert({element,1});
}
}
if(!S1[num2].size()) {
for(int i = 0; i < arr[num2].size(); ++i) {
element = arr[num2][i];
S1[num2].insert({element,1});
}
}
int cnt = 0;
for(auto ite:S1[num1]){ // 找相同的数
if(S1[num2].count(ite.first)){
++cnt;
}
}
double Nt = S1[num1].size()+S1[num2].size()-cnt; // 简单的集合运算
double Nc = cnt;
return Nc/Nt*100;
}
int main() {
ios::sync_with_stdio(false);
cin >> T;
for(int i = 1; i <= T; ++i) {
cin >> num;
for(int j = 0; j < num; ++j) {
cin >> element;
arr[i].push_back(element);
}
}
cin >> T;
int num1,num2;
for(int i = 1; i <= T; ++i) {
cin >> num1 >> num2;
cout << fixed << setprecision(1) << compare(num1,num2) << "%\n";
}
}
发表于 2020-01-23 21:55:11
回复(0)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <map>
#include <iterator>
using namespace std;
//1063 Set Similarity
//set用1~n编号。
double get_simi(const set<int> &a, const set<int> &b) {
int diff = b.size(), common = 0;
for (set<int>::iterator it = a.begin(); it != a.end(); ++it) {
if (b.find(*it) != b.end()) {
//b中存在，说明是公共数
common++;
}
else {
//b中找不到
diff++;
}
}
double s = double(common) / diff *100.0;
return s;
}
/*
//原始方法，用原生函数，但是超时
double get_simi(const set<int> &a, const set<int> &b) {
double s;
// set<int> c(a.begin,a.end());
// c.insert(b.begin(),b.end());
set<int> c, d;
//并集
set_union(a.begin(), a.end(), b.begin(), b.end(), std::inserter(c,c.end()));
//交集
set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::inserter(d,d.end()));
s = double(d.size()) / double(c.size())*100.0;
return s;
};
*/
set<int> a[51];
int main() {
int n, m, k, l, r;
int num;//10^9
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &m);
//set<int>* ptr = new set<int>;
//a[i] = ptr;
for (int j = 0; j < m; ++j) {
scanf("%d", &num);
a[i].insert(num);
//ptr->insert(num);
}
}
scanf("%d", &k);
double s;
for (int i = 0; i < k; ++i) {
scanf("%d%d", &l, &r);
//double s = get_simi(*a[l], *a[r]);
s = get_simi(a[l], a[r]);
printf("%.1f%%\n", s);
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <map>
#include <iterator>
using namespace std;
//1063 Set Similarity
//set用1~n编号。
double get_simi(const set<int> &a, const set<int> &b) {
int diff = b.size(), common = 0;
for (set<int>::iterator it = a.begin(); it != a.end(); ++it) {
if (b.find(*it) != b.end()) {
//b中存在，说明是公共数
common++;
}
else {
//b中找不到
diff++;
}
}
double s = double(common) / diff *100.0;
return s;
}
/*
//原始方法，用原生函数，但是超时
double get_simi(const set<int> &a, const set<int> &b) {
double s;
// set<int> c(a.begin,a.end());
// c.insert(b.begin(),b.end());
set<int> c, d;
//并集
set_union(a.begin(), a.end(), b.begin(), b.end(), std::inserter(c,c.end()));
//交集
set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::inserter(d,d.end()));
s = double(d.size()) / double(c.size())*100.0;
return s;
};
*/
set<int> a[51];
int main() {
int n, m, k, l, r;
int num;//10^9
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &m);
//set<int>* ptr = new set<int>;
//a[i] = ptr;
for (int j = 0; j < m; ++j) {
scanf("%d", &num);
a[i].insert(num);
//ptr->insert(num);
}
}
scanf("%d", &k);
double s;
for (int i = 0; i < k; ++i) {
scanf("%d%d", &l, &r);
//double s = get_simi(*a[l], *a[r]);
s = get_simi(a[l], a[r]);
printf("%.1f%%\n", s);
}
return 0;
}
发表于 2019-08-24 15:13:00
回复(0)
n = input()
n = int(n)
lst = [None for i in range(n)]
for i in range(n):
tem = set(map(int,input().split()[1:]))
lst[i] = tem
m = input()
m = int(m)
for i in range(m):
a,b = map(int,input().split())
c = lst[a-1]|lst[b-1]
d = lst[a-1]&lst[b-1]
print("%.1f"%(len(d)/len(c)*100)+"%")
发表于 2018-12-11 20:56:51
回复(0)
思路：如果用set 那就用set的一套东西就好了
set_intersection
求交集合
set_union
求并集
但是排名400+，看来给的算法库不够酷
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
#ifndef debug
ifstream ifile("case.txt");
#define cin ifile
#endif
int main()
{
int n;
while (cin >> n)
{
int k;
set<int> mySet[500];
for (int i = 0; i < n; i++)
{
cin >> k;
for (int j = 0; j < k; j++)
{
int tmp;
cin >> tmp;
mySet[i].insert(tmp);
}
}
// 查询
cin >> n;
int a, b;
for (int i = 0; i < n; i++)
{
cin >> a >> b;
vector<int> plus(mySet[a-1].size() + mySet[b-1].size());
vector<int> minutes(mySet[a - 1].size() + mySet[b - 1].size());
auto it = set_union(mySet[a - 1].begin(), mySet[a - 1].end(), mySet[b - 1].begin(), mySet[b - 1].end(), plus.begin());
plus.resize(it - plus.begin());//重新确定ivec大小
auto iter = set_intersection(mySet[a - 1].begin(), mySet[a - 1].end(), mySet[b - 1].begin(), mySet[b - 1].end(), minutes.begin());
minutes.resize(iter - minutes.begin());//重新确定ivec大小
printf("%.1lf%%\n", minutes.size() * 100.0 / plus.size());
}
}
system("pause");
}
编辑于 2018-08-28 08:09:12
回复(0)
n = int(input())
a = []
for i in range(n):
m = set(map(int,input().split()[1:]))
a.append(m)
k = int(input())
for i in range(k):
q = list(map(int,input().split()))
x, y = q[0]-1, q[1]-1
top = 100.0*len(a[x]&a[y])
down = 1.0*len(a[x]|a[y])
print('%.1f%%' % (top/down))
发表于 2018-05-24 21:46:46
回复(0)
问题信息
难度：
24条回答
7收藏
9503浏览
通过挑战的用户
-
2023-03-06 10:56:34 -
2023-02-28 11:56:51
-
2023-02-24 14:39:48
-
2023-02-24 05:58:42 -
2023-02-23 22:17:52
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
