L2-005. Set similarity

The time limit
400 ms
Memory limit
65536 kB
Code length limit
8000 B
The procedure of judging questions
Standard
author
Chen Yue

Given two sets of integers , Their similarity is defined as :Nc/Nt*100%. among Nc Is the number of unequal integers that both sets have ,Nt Is the number of unequal integers shared by two sets . Your task is to calculate the similarity of any pair of given sets .

Input format :

The first line of input gives a positive integer N(<=50), Is the number of sets . And then N That's ok , Each row corresponds to a set . Each set first gives a positive integer M(<=104), Is the number of elements in the set ; Then follow M individual [0, 109] An integer in an interval .

The next line gives a positive integer K(<=2000), And then K That's ok , Each row corresponds to the number of a pair of sets that need to calculate the similarity ( Set from 1 To N Number ). Numbers are separated by spaces .

Output format :

For each pair of sets that need to be calculated , Output their similarity in one line , To keep after the decimal point 2 The percentage number of bits .

sample input :

3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3

sample output :

50.00%
33.33%

Ideas : Let's think of it naturally stl Association containers in set, And then combined with its usage, it can perfectly solve this problem

 #include<bits/stdc++.h>
#include<set>
using namespace std;
int main(){
set<int> s[];
int n,m,x,k,y1,y2;
cin>>n;
for(int i=;i<=n;i++)
{
cin>>m;
for(int j=;j<m;j++){
cin>>x;
s[i].insert(x);
}
}
cin>>k;
for(int i=;i<k;i++){
cin>>y1>>y2;
int same=;
set<int>::iterator aa;
for(aa=s[y1].begin();aa!=s[y1].end();aa++){
if(s[y2].find(*aa)!=s[y2].end())
same++;
}
double ans=same*1.0/(s[y1].size()+s[y2].size()-same);
printf("%.2f%%\n",ans*);
}
return ;
}

Group programming ladder competition - Exercise set L2-005. More articles on set similarity

  1. PTA L2-001 Emergency rescue - shortest path (Dijkstra) Multiple shortest paths find the optimal solution and output path Group programming ladder competition - Exercise set

    L2-001  Emergency rescue  (25  branch )   As the leader of a city's emergency rescue team , You have a special national map . On the map, there are many scattered cities and some fast roads connecting the cities . The number of rescue teams in each city and the speed of each connecting two cities ...

  2. PTA L2-023 Graph coloring problem - Forward star mapping Group programming ladder competition - Exercise set

    L2-023  Graph coloring problem  (25  branch )   Graph coloring is a famous problem NP Problem completely . Given an undirected graph ,, Ask if you can use it K The colors are V Each vertex in is assigned a color , So that no two adjacent vertices have the same color ? But this problem is not for you to solve ...

  3. Group programming ladder competition - Exercise set L1-007 Read numbers

    - - -> Bloggers recommend , The student party . Programmers must , Click to see - - - >>>>> Popular articles recommend following 50 There are a lot of visits to the algorithm programming , Contains common Syntax , data structure , Solutions and so on , As C ...

  4. Group programming ladder competition - Exercise set L2-010. Row of seats

    L2-010. Row of seats The time limit 150 ms Memory limit 65536 kB Code length limit 8000 B The procedure of judging questions Standard author Chen Yue The most delicate thing is to set up a banquet , It is to arrange seats for the guests who come to the banquet . ...

  5. Group programming ladder competition - Exercise set L2-007. Family property

    L2-007. Family property The time limit 400 ms Memory limit 65536 kB Code length limit 8000 B The procedure of judging questions Standard author Chen Yue Give everyone's family members and their own properties , Please count out each ...

  6. PTA L2-002 The chain watch is weightless Group programming ladder competition - Exercise set

    L2-002  The chain watch is weightless (25  branch )   Given a linked list with integer keys  L, You need to delete the key node where the absolute value is repeated . For each key value  K, Only the first absolute value is equal to  K  The nodes of are reserved . meanwhile , All deleted nodes must be saved in another ...

  7. Group programming ladder competition - Exercise set -L1-045. The universe is invincible

    L1-045. The universe is invincible It is said that the first program learned by all programmers is to output a sentence on the screen “Hello World”, Say hello to the world . As a programmer in TIANTI game , You need to write more advanced programs , To be able to say hello to any designated planet ...

  8. Group programming ladder competition - Exercise set -*L1-043. Reading Room

    L1-043. Reading Room TIANTI book reading room, please write a simple book borrowing statistics program . When a reader borrows a Book , The administrator enters the book number and presses S key , The program starts timing : When the reader returns the book , The administrator enters the book number and presses E key , Program end timing . The book number is no more than 100 ...

  9. Group programming ladder competition - Exercise set L2-011. Play with binary trees

    L2-011. Play with binary trees The time limit 400 ms Memory limit 65536 kB Code length limit 8000 B The procedure of judging questions Standard author Chen Yue Given a binary tree in order to traverse and preorder traversal , Please make a mirror of the tree first ...

  10. Group programming ladder competition - Exercise set L2-009. Grab a red envelope

    L2-009. Grab a red envelope The time limit 300 ms Memory limit 65536 kB Code length limit 8000 B The procedure of judging questions Standard author Chen Yue No one hasn't grabbed the red envelope …… Here is given N Individuals give each other red envelopes . rob ...

Random recommendation

  1. iOS And UILabel Word wrap for

    Ideas : obtain UILabel Of frame size obtain UILabel Font size of obtain UILabel Text content of According to the above 3 Part of the data , Calculate the size of the text display area according to 4 The calculated size , Real time change UILabel Of frame ...

  2. Java In dealing with Linux Semaphore

    In order to prevent unscrupulous web crawlers from grabbing articles , This is to mark , Reprint please indicate the source of the article .LaplaceDemon/ShiJiaqi. http://www.cnblogs.com/shijiaqi1066/p/5976361. ...

  3. VS Shortcut key ( turn )

    Believe in .Net Developers want to be able to memorize all kinds of VS Shortcut key to improve the efficiency of normal development , But the memory ability is too poor and there are many shortcut keys , Very annoying , So stop ! Now I'll give a brief introduction to my memory VS Some methods of shortcut keys , I hope that's helpful . 1. window ...

  4. A set of open source HTML5 Apps

    One group uses " draw app Well " Developed HTML5 Apps, By default FirefoxOS equipment , In fact, they can be like Android/IPhone/WindowsPhone8/BlackBerry/ ...

  5. elasticsearch REST API Method batch insert data

    elasticsearch REST API Method batch insert data 1:ES Service address of  http://127.0.0.1:9600/_bulk 2: Requested data body , Pay attention to the last line of the data, and remember to add a new line { &quo ...

  6. Linux File permissions and directory configuration

    One . File authority : Linux One of the best places , It's his multitasking environment . And in order to let each user have more confidential file data , Therefore, the authority management of archives becomes very important . Linux Generally, the accessible identities of files are divided into three categories , , respectively, ...

  7. python adopt js Control scroll bar to pull full text adopt psutil obtain pid Window handle , adopt win32gui Bring the program window forward adopt autopy Right click menu and save as operation

    1. Reference resources utilize Python + Selenium Automated quick screenshots utilize Python + Selenium Achieve the specified elements of the page screenshot ( Truncated graph elements ) Use python Get all the processes in the system PID And the process name ...

  8. Django And Static template rendering

    It can be simple django.http.HttpResponse To display the content on the web page , You can also use rendering templates to display content . explain : The code is based on Django 1.8, but Django 1.4 - Dja ...

  9. Linux Partition knowledge and enterprise scene partition 76

    File system is the same as decoration . Here's the hard drive , The division is over , No formatting . No formatting is equivalent to no decoration .[ Partition ] It's not necessary . You can't put data without a file system , A file system can be understood as a piece of software , It's implemented in the form of software , this ...

  10. Python Remote connection module -Telnet

    Python Remote connection module -Telnet author : Yin Zhengjie Copyright notice : Original works , Declined reprint ! Otherwise, the legal liability will be investigated . Although now the mainstream python Version or 2.7, Believe in 2020 year python Programmers tend to Python ...